Posted on 2012-09-13 15:11
hoshelly 閱讀(1894)
評論(0) 編輯 收藏 引用 所屬分類:
Programming
在處理表達(dá)式過程中需要對括號匹配進(jìn)行檢驗(yàn)，括號匹配包括三種：“(”和“)”，“[”和“]”，“{”和“}”。例如表達(dá)式中包含括號如下：
( ) [ ( ) ( [ ] ) ] { }
1 2 3 4 5 6 7 8 9 10 11 12
從上例可以看出第1和第2個括號匹配，第3和第10個括號匹配，4和5匹配，6和9匹配，7和8匹配，11和12匹配。從中可以看到括號嵌套的的情況是比較復(fù)雜的，使用堆棧可以很方便的處理這種括號匹配檢驗(yàn)，可以遵循以下規(guī)則：
1、 當(dāng)接收第1個左括號，表示新的一組匹配檢查開始；隨后如果連續(xù)接收到左括號，則不斷進(jìn)堆棧。
2、 當(dāng)接受第1個右括號，則和最新進(jìn)棧的左括號進(jìn)行匹配，表示嵌套中1組括號已經(jīng)匹配消除
3、 若到最后，括號不能完全匹配，則說明輸入的表達(dá)式有錯
Input
第一行輸入一個t，表示下面將有t組測試數(shù)據(jù)。接下來的t行的每行輸入一個表達(dá)式，表達(dá)式只考慮英文半角狀態(tài)輸入，無需考慮中文全角輸入
Output
對于每一行的表達(dá)式，檢查括號是否匹配，匹配則輸入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;
}