Posted on 2012-09-13 15:11
hoshelly 阅读(1882)
评论(0) 编辑 收藏 引用 所属分类:
Programming
在处理表达式过程中需要对括号匹配进行检验，括号匹配包括三种：“(”和“)”，“[”和“]”，“{”和“}”。例如表达式中包含括号如下：
( ) [ ( ) ( [ ] ) ] { }
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、 若到最后，括号不能完全匹配，则说明输入的表达式有错
Input
第一行输入一个t，表示下面将有t组测试数据。接下来的t行的每行输入一个表达式，表达式只考虑英文半角状态输入，无需考虑中文全角输入
Output
对于每一行的表达式，检查括号是否匹配，匹配则输入ok，不匹配则输出error
Sample Input
2
(a+b)[4*5+(-6)]
[5*8]/{(a+b)-6
Sample Output
ok
error
代码：
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
int main()
{
int t,len;
stack<char> mystack;
cin>>t;
while(t--)
{
int ok=0;
char str[100];
cin>>str;
len=strlen(str);
for(int i=0;i<len;i++)
{
switch(str[i])
{
case '(':
case '[':
case '{':
mystack.push(str[i]);
break;
case ')':
if(mystack.top() == '(')
{
mystack.pop();
ok=1;
}
break;
case ']':
if(mystack.top() == '[')
{
mystack.pop();
ok=1;
}
break;
case '}':
if(mystack.top() == '{')
{
mystack.pop();
ok=1;
}
break;
default: break;
}
}
if(ok && mystack.empty())
cout<<"ok"<<endl;
else
cout<<"error"<<endl;
}
return 0;
}