编写算法，判断一个表达式中的括号是否正确匹配。
给一个表达式，用目测的方法怎么做呢。从左往右看这个表达式中的括号，看到一个“（”，就记住它（这里理解为入栈），如果下一个括号是“）”，则划掉这两个括号（这里可以理解为出栈），表示一对括号处理完毕，继续往后看。如果前面所有的括号都被划掉了，二下一个括号却是“）”，则括号一定不匹配，因为“）”之前已经没有括号和它匹配了。如果下一个括号是“（”，则暂时不管，先把它放在那里，等后边的“（”处以后看到的哭哦哈哦啊要么是“（”要么是“）”，就用前边说的方法来处理。如果到最后所有的括号都被划掉则匹配，否则就不匹配。由此可以看到，一个问题中如果出现这种情况，即在解决问题的过程中出现一个状态，但凭现在的条件不能判断当前的状况是否可以解决，需要记下，等待以后出现可以解决当前状态的条件后返回再解决之。这种问题需要用栈来解决，栈具有记忆功能，这就是栈的FILOO特性延伸出来的一种特性。
#include<iostream>
#define maxSize 50
using namespace std;
int match(
char a[],
int n)
{
char stack[maxSize];
int top=-1;
for(
int i=0;i<n;i++)
if(a[i]=='(')
stack[++top]='(';
else if(a[i]==')')
{
if(top==-1)
return 0;
top--;
}
if(top==-1)
return 1;
else return 0;
}
int main()
{
char a[maxSize];
cout<<"请输入算术表达式，以#结束： ";
int i=0;
while(cin>>a[i],a[i]!='#')
{
i++;
}
for(
int j=0;j<i;j++)
cout<<a[j];
cout<<endl;
if(match(a,i)==1)
cout<<"匹配成功";
else cout<<"不能匹配";
return 1;
}
posted on 2012-08-22 08:52
yyj 阅读(200)
评论(0) 编辑 收藏 引用