【题目描述】
假设一个表达式有英文字母(小写)和数字、运算符(+,—,*,/)和左右小(圆)括号构成,以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配,若匹配,则返回“YES”;否则返回“NO”。表达式长度小于255,左圆括号少于20个。
【输入格式】
输入文件包括一行数据,即表达式,
【输出格式】
输出文件包括一行,即“YES” 或“NO”。
【样例输入】
2*(x+y)/(1-x)@
【样例输出】
YES
分析:此题只需判断括号是否匹配,其他的都不需要考虑,这样可以把题简化成只对括号的操作,那让我们看看,不合法的括号有哪些
1:当出现')'后前面没有相应的'('对应。
2:当整个表达式都判断完了还有'('没有相应的')'与之配对
所以算法可以这样设计
1.对整个表达式进行遍历,当为非括号或括回时不做任何处理直接判断下一字符
2.如果当前字符为'('直接把它入栈
3.如果当前字符为')'时,首先判断栈是否为空,如果为空直接可以判定不匹配,如果非空,直接把栈顶元素出栈
4.当整个表达式遍历完毕,如果当前栈为空则表明是匹配,非空表明还有'('没有相应的')' 相匹配
c++代码
#include<iostream> #include<cstring> #include<cstdio> #include<stack> using namespace std; string s; stack<char> a; bool my_judge(string); int main() { cin>>s; if(my_judge(s))cout<<"YES"<<endl; else cout<<"NO"<<endl; return 0; } bool my_judge(string s) { int i=0; while(s[i]!='@') { if(s[i]=='(')a.push(s[i]); if(s[i]==')') { if(a.empty()) return false; a.pop(); } i++; } if(a.empty())return true; else return false; }