判断算术表达式中的括号是否匹配

梦里梦外; 2021-12-18 23:59 258阅读 0赞

问题描述：假设一个算术表达式中包含圆括号、方括号和花括号3种类型的括号，编写一个算法来判断表达式中的括号是否匹配，以字符“\#”作为算术表达式的结束符。

解决问题思想：遇见左括号就进栈，遇见右括号就出栈。当括号匹配时上一次进栈和本次出栈的括号肯定配对，所以不需要循环依次出栈判断括号是否配对(此处之前没有想到，导致在出栈时还用了依次循环来判断是否配对，这样做会导致算法时间复杂度增加)；如果不配对，则算术表达式的括号肯定不配对。

代码:

#include<stdio.h>
    #include<stdlib.h>
    #include<iostream>
    using namespace std;
    typedef char Element;
    typedef struct stack{
    	Element *data; // 建立栈的空间
    	int top = -1;  //栈顶指针
    }stack;
    bool isEmpty(stack s){//判断栈是否为空
    	if (s.top == -1)
    		return true;
    	else
    		return false;
    }
    void push(stack &s,Element data){ //进栈操作
    	++s.top;
    	s.data = (Element*)malloc(sizeof(Element));//先开辟一个Element大小的空间用于进栈
    	s.data[s.top] = data;
    }
    void pop(stack &s,Element &data){//出栈操作
    	if (isEmpty(s) != true){
    		data = s.data[s.top];
    		s.top--;
    	}
    }
    int judge_bracket(Element *str){
    	int count = 0;
    	Element data;
    	stack s;
    	while (str[count]!='#')
    	{
    	  switch (str[count]){
    		case '(':
    			push(s,str[count]);
    			break;
    		case '[':
    			push(s, str[count]);
    			break;
    		case '{':
    			push(s, str[count]);
    			break;
    		case ')':
    			pop(s, data);
    			if (data != '(')
    				return 0;
    			break;
    		case ']':
    			if (data != '[') 
    				return 0;
    			break;
    		case '}':
    			if (data != '{') 
    				return 0;
    			break;
    		}
    		count++;
    	}
    	if (isEmpty(s) != true)
    		return 0;
    	else
    		return 1;
    }
    int main(){
    	Element *str;
    	int length,result;
    	printf_s("算术表达式长度:");
    	scanf_s("%d", &length);
    	str = (Element*)malloc(sizeof(Element)*length);
    	printf_s("输入算法表达式以'#'结束:");
    	for (int i = 0; i < length; i++)
    		cin >> str[i];
    	result=judge_bracket(str);
    	switch (result)
    	{
    	case 0:
    		printf_s("算术表达式中的括号不匹配");
    		break;
    	case 1:
    		printf_s("算术表达式中的括号匹配");
    	}
    	system("pause");
    	return 0;
    }

运行结果：

![20190701232010478.png][]

![20190701232039307.png][]

[20190701232010478.png]: /images/20211219/2deef7e92312428f9637698aae352faa.png
[20190701232039307.png]: /images/20211219/1df500b21132406281b3ab51aeed10dc.png