P1739 表达式括号匹配

括号匹配问题： 一说到这个问题，自然而然想到栈，左括号入栈，右括号出栈，最后判断栈是否为空。

注意： 当遇到右括号时，出栈时要判断当前栈是不是空，若已经为空，则无法继续出栈，输出NO,结束程序；若不为空，则直接出栈（原因：若右括号大于左括号，多出来的右括号是肯定不能再匹配成一个完整括号）；

参考代码1.0： 不用栈也可以，直接定义一个变量res来存储左括号个数，遇到右括号就减1，注意点和栈一样；

#include <stack> #include <cstdio> #include <string> #include <cstring> #include <iostream> #include <algorithm> #define INF 0x3f3f3f3f #define MAX 5010 using namespace std; int main() { int res = 0; char c; while(cin >> c) { if(c == '@') break; if(c == '(') res++; if(c == ')') { if(res <= 0) {cout << "NO" << endl; return 0;} res--; } } if(res == 0) cout << "YES" << endl; else cout << "NO" << endl; return 0; }

参考代码2.0：

#include <stack> #include <cstdio> #include <string> #include <cstring> #include <iostream> #include <algorithm> #define INF 0x3f3f3f3f #define MAX 5010 using namespace std; int main() { stack<char> s; char c; while(cin >> c) { if(c == '@') break; if(c == '(') s.push(c); if(c == ')') { if(s.empty()) {cout << "NO" << endl; return 0;} s.pop(); } } if(s.empty()) cout << "YES" << endl; else cout << "NO" << endl; return 0; }