题目描述
处理表达式过程中需要对括号匹配进行检验，括号匹配包括三种：“(”和“)”，“[”和“]”，“{”和“}”。例如表达式中包含括号如下：
( ) [ ( ) ( [ ] ) ] { }
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对象来实现
stack类使用的参考代码
n包含头文件<stack> ： #include <stack>
n判断堆栈是否空： s.empty()，如果为空则函数返回true，如果不空则返回false
输入
第一行输入一个t，表示下面将有t组测试数据。接下来的t行的每行输入一个表达式，表达式只考虑英文半角状态输入，无需考虑中文全角输入
输出
对于每一行的表达式，检查括号是否匹配，匹配则输入ok，不匹配则输出error
样例输入
样例输出
提示
算法流程
1、初始化，i=0，建立堆栈，栈为空
2、输入表达式，建立指针指向表达式的头部
3、读入表达式的第i个字符
4、如果第i个字符是左括号，入栈
5、如果第i个字符是右括号，检查栈顶元素是否匹配
A.如果匹配，弹出栈顶元素
B.如果不匹配，报错退出
6、i++，指向下一个字符，是否已经表达式末尾
A. 未到末尾，重复步骤3
B. 已到达末尾
a. 堆栈为空，输出ok
b. 堆栈不为空，输出error
#include<iostream> #include<stack> using namespace std; int main() { int T; cin>>T; while(T--) { string str; cin>>str; int flag=1; stack<char>s; for(int i=0;i<(int)str.length();i++) { char c=str[i]; if(c=='('||c=='['||c=='{') s.push(c); else if(c==')') { if(s.top()=='(') s.pop(); else { flag=0; break; } } else if(c==']') { if(s.top()=='[') s.pop(); else { flag=0; break; } } else if(c=='}') { if(s.top()=='{') s.pop(); else { flag=0; break; } } } if(!s.empty()) flag=0; if(flag==1) cout<<"ok"<<endl; else cout<<"error"<<endl; } return 0; }
原文链接: https://www.cnblogs.com/SZU-DS-wys/p/12177964.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/324238
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
