1353：表达式括号匹配(stack)

算法思想：

1.用string存储字符串，遍历字符串

2.遇到左括号就入栈

3.遇到右括号就匹配出栈，但是再出栈之前要判断栈是否为空

a.如果栈为空，说明没有与右括号匹配的左括号，右括号多了，不匹配！！

b.否则，说明左括号与右括号匹配上了，将左括号出栈

4.循环结束之后，判断栈是否为空

a.如果栈为空，说明左括号与右括号完全匹配上了

b.否则，说明左括号多了，不匹配！！！

#include <iostream>
#include <stack>
using namespace std;int main() {string s;stack<char> stk;getline(cin,s);for(auto c:s){//遍历字符串if(c=='('){//遇到左括号入栈stk.push(c);}else if(c==')'){//遇到右括号，先判断栈是否为空if(!stk.empty()){//如果不为空，则左括号与右括号匹配要出栈stk.pop();}else{//如果为空，说明已经没有与左括号匹配的右括号了，输出NOcout<<"NO"<<endl;return 0;}}}//遍历完之后，如果栈里面还有左括号说明不匹配if(!stk.empty()) cout<<"NO"<<endl;else             cout<<"YES"<<endl;return 0;
}

P1981 [NOIP2013 普及组] 中缀表达式求值

算法思想：

1.如果在1前面加个括号的话，就符合一个运算符一个数组的模式

2.遇到+后面数组就入栈

3.遇到*栈顶元素就计算

4.最后循环出栈，计算sum和

本题要保留后4为，必须边计算边求余，利用模运算的性质

#include <iostream>#include <stack>using namespace std;const int M = 1e4;int main() {stack<int> stk;char ch;int num, sum = 0;cin >> num;stk.push(num % M);while (cin >> ch >> num) {//一个字符一个数字的输入规律，开始循环if (ch == '+')//遇到+就入栈stk.push(num % M);else if (ch == '*') {//遇到*就计算stk.top() = (stk.top() % M * num % M) % M;}}while (!stk.empty()) {//最后栈里面的累加求和sum = (sum % M + stk.top() % M) % M;stk.pop();}cout << sum << endl;return 0;

1354：括弧匹配检验

算法思想：遇到左类型的括号就入栈，遇到右类型的括号就要出栈，但是出栈前要判断是否栈空和是否匹配，与1353类似省略

#include <iostream>
#include <stack>
#include <string>
using namespace std;
string s;
int main() {stack<char> stk;cin>>s;for(auto c:s){if(c=='['||c=='(')stk.push(c);else if(c==']'){if(stk.empty()){cout<<"Wrong"<<endl;return 0;}else{if(stk.top()=='[') stk.pop();else{cout<<"Wrong"<<endl;return 0;}}}else if(c==')'){if(stk.empty()){cout<<"Wrong"<<endl;return 0;}else{if(stk.top()=='(') stk.pop();else{cout<<"Wrong"<<endl;return 0;}}}}if(!stk.empty()) cout<<"Wrong"<<endl;else             cout<<"OK"<<endl;return 0;
}

1358中缀表达式值(expr)

#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {stack<int> stk;char ch='+';int num,sum=0;cin>>num;stk.push(num);while(cin>>ch>>num){if(ch=='@') break;if(ch=='+') stk.push(num);else if(ch=='-') stk.push(-num);else if(ch=='*') stk.top()*=num;else if(ch=='/') stk.top()/=num;}while(!stk.empty()){sum+=stk.top();stk.pop();}cout<<sum<<endl;return 0;
}

1355：字符串匹配问题(strs)优先级问题

#include<iostream>
#include<map>
#include<stack>
using namespace std;
map<char,int> mp;
void check(string s){stack<char> stk;for(int i=0;i<s.size();i++){if(mp[s[i]]>0){if(stk.empty()) stk.push(s[i]);else{if(mp[stk.top()]>=mp[s[i]]){stk.push(s[i]);}else{cout<<"NO"<<endl;return ;}}}else{if(stk.empty()){cout<<"NO"<<endl;return ;}else if(mp[stk.top()]+mp[s[i]]==0){stk.pop();}else if(mp[stk.top()]+mp[s[i]]!=0){cout<<"NO"<<endl;return ;}}}if(!stk.empty()) cout<<"NO"<<endl;else             cout<<"YES"<<endl;
}int main(){int n;cin>>n;//把所有左 右 括号都用map映射一下mp['<']=1;mp['(']=2;mp['[']=3;mp['{']=4;mp['>']=-1;mp[')']=-2;mp[']']=-3;mp['}']=-4;while(n--){string s;cin>>s;check(s);}return 0;
}