题目描述
假设一个表达式有英文字母(小写)、运算符(+，-，*，/ )和左右小(圆)括号构成， 以@作为表达式的结束符。
请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回YES；否则返回NO。
输入
包括一行数据，即表达式。
输出
包括一行，即YES或NO。
样例输入 Copy
【样例1】 2*(x+y)/(1-x)@ 【样例2】 (25+x)*(a*(a+b+b)@
样例输出 Copy
【样例1】 YES 【样例2】 NO
栈的应用
大体思路：
如果遇见了左括号，就将左括号放到栈里面，如果遇到右括号，查看栈顶元素是不是左括号，如果是左括号，就将左括号pop()
最后检查栈的大小是不是0，如果是，就是YES，不是的话，就是NO
其实可以优化一下，如果当当前的栈是空的的时候，如果当前的符号是右括号的情况一定是NO
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math") #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma comment(linker, "/stack:200000000") #pragma GCC optimize (2) #pragma G++ optimize (2) #include <bits/stdc++.h> #include <algorithm> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; #define wuyt main typedef long long ll; #define HEAP(...) priority_queue<__VA_ARGS__ > #define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > > template<class T> inline T min(T &x,const T &y){return x>y?y:x;} template<class T> inline T max(T &x,const T &y){return x<y?y:x;} //#define getchar()(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++) //char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf; ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar(); if(c == '-')Nig = -1,c = getchar(); while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar(); return Nig*x;} #define read read() const ll mod=1e9+7; const ll inf=0x3f3f3f3f; const int maxn=1e6+9; char ss[maxn]; int main() { int ans=0; int length; cin>>ss; length=strlen(ss); stack<int> s; for(int i=0;i<length;i++) { if(ss[i]=='(') s.push(ss[i]); else if(!s.empty()) { if(ss[i]==')'&&s.top()=='(') s.pop(); } } if (s.empty()) printf("YES\n"); else printf("NO\n"); return 0; }
Main_Code2:
stack <int> st; string t; int main() { getline(cin,t); int len = t.size(); int flag = 0; for(int i=0;i<len;i++){ ///cout<<t[i]<<endl; if((t[i] == '[') || (t[i] == '(') || (t[i] == '{')){ ///cout<<t[i] <<endl; st.push(t[i]); } else if((t[i] == ']') || (t[i] == ')') || (t[i] == '}')){ if(st.empty()){ flag = 1;break; } else{ if(t[i] == '}' && st.top() == '{') st.pop(); if(t[i] == ')' && st.top() == '(') st.pop(); if(t[i] == ']' && st.top() == '[') st.pop(); } } } if(st.size() || flag) puts("no"); else puts("yes"); return 0; }
