3-4 D. DS堆栈--括号匹配

题目描述

处理表达式过程中需要对括号匹配进行检验，括号匹配包括三种：“(”和“)”，“[”和“]”，“{”和“}”。例如表达式中包含括号如下：

(	)	[	(	)	(	[	]	)	]	{	}
1	2	3	4	5	6	7	8	9	10	11	12

从上例可以看出第1和第2个括号匹配，第3和第10个括号匹配，4和5匹配，6和9匹配，7和8匹配，11和12匹配。从中可以看到括号嵌套的的情况是比较复杂的，使用堆栈可以很方便的处理这种括号匹配检验，可以遵循以下规则：

1、 当接收第1个左括号，表示新的一组匹配检查开始；随后如果连续接收到左括号，则不断进堆栈。

2、 当接受第1个右括号，则和最新进栈的左括号进行匹配，表示嵌套中1组括号已经匹配消除

3、 若到最后，括号不能完全匹配，则说明输入的表达式有错

建议使用C++自带的stack对象来实现

输入?

第一行输入一个t，表示下面将有t组测试数据。接下来的t行的每行输入一个表达式，表达式只考虑英文半角状态输入，无需考虑中文全角输入

输入样例1：

2
(a+b)[4*5+(-6)]
[5*8]/{(a+b)-6

输入样例2：

4
{1+1}[3+3](5+5)
((({{{}}})))
((({{{}}})))([[]])
((({{{5+5}}})))([[]])(1+1)

输出?

对于每一行的表达式，检查括号是否匹配，匹配则输入ok，不匹配则输出error

输出样例1：

ok
error

输出样例2：

ok
ok
ok
ok

代码?

#include <iostream>
#include <stack>
using namespace std;

int main()
{
    int t,len;
    string s;
    cin >> t;
    while(t--){
        stack<char> sta;
        int flag = 1;  //标志是否匹配 
        cin >> s;
        len = s.length();
        for(int i = 0; i < len; i++){
            if(s[i] == '(' || s[i] == '[' || s[i] == '{'){  //左括号入栈
                sta.push(s[i]);
            }else if(s[i] == ')' || s[i] == ']' || s[i] == '}'){  //右括号判断
                if(sta.empty()){  //如果栈空即前面无左括号则不匹配
                    flag = 0;
                }else{
                    char c = sta.top();  //右括号与栈顶元素比较是否匹配
                    if((c == '(' && s[i] == ')') || (c == '[' && s[i] == ']') || (c == '{' && s[i] == '}')){
                        sta.pop();  //若匹配则这一对括号判断完成，出栈，继续比较后面的
                    }else{
                        flag = 0;
                    }
                }
            }
        }
        
        if(!sta.empty()){  //若右括号都匹配完成，栈中还有剩余的左括号，则不匹配
            flag = 0;
        }
        
        if(flag == 1){
            cout << "ok" << endl;
        }else{
            cout << "error" << endl;
        }
    }
    return 0;
}