1.模拟栈
题目
输入输出样例
输入样例：
10 push 5 query push 6 pop query pop empty push 4 query empty
输出样例：
5 5 YES 4 NO
代码
很简单的题，代码奉上
#include <bits/stdc++.h> using namespace std; const int N = 100010; int arr[N]; int main() { int k = 0,m; cin>>m; while(m--) { int a; string op; cin>>op; if(op=="push") { cin>>a; arr[++k]=a; } else if(op=="pop") k--; else if(op=="empty") if(k==0) printf("YES\n"); else printf("NO\n"); else printf("%d\n",arr[k]); } return 0; }
2.表达式求值
输入样例：
(2+2)*(1+1)
输出样例：
8
思路
输入长度为n的字符串，例如：1+2+3*4*5
输出表达式的值，即：63
应该用什么数据结构：当然是栈。
应该先计算哪一步？实际应该先计算1+2。
“表达式求值”问题，两个核心关键点：
双栈，一个操作数栈，一个运算符栈；
运算符优先级，栈顶运算符和即将入栈的运算符的优先级比较：
如果栈顶的运算符优先级低，新运算符直接入栈
如果栈顶的运算符优先级高，先出栈计算，新运算符再入栈
以1+2+3*4*5举例：
1.一开始，初始化好输入的字符串，以及操作数栈，运算符栈。
2.一步步，扫描字符串，操作数一个个入栈，运算符也入栈。
3.下一个操作符要入栈时，需要先比较优先级。栈内的优先级高，必须先计算，才能入栈。
4.接下来，运算符和操作数才能继续入栈。下一个操作符要入栈时，继续比较与栈顶的优先级。栈内的优先级低，可以直接入栈。
5.字符串继续移动。
6.又要比较优先级了。栈内的优先级高，还是先计算（3*4=12），再入栈。
7.不断入栈，直到字符串扫描完毕。
8.不断出栈，直到得到最终结果3+60=63，算法完成。
代码
#include <bits/stdc++.h> using namespace std; stack<int> num; stack<char> op; unordered_map<char,int> h{{'+',1},{'-',1},{'*',2},{'/',2}}; void eval() { int a=num.top(); num.pop(); int b=num.top(); num.pop(); char c=op.top(); op.pop(); int res=0; if(c=='+') res=b+a; if(c=='-') res=b-a; if(c=='*') res=b*a; if(c=='/') res=b/a; num.push(res); } int main() { string str; cin>>str; for(int i=0;i<str.size();i++) { if(isdigit(str[i]))//数字入栈 { int x=0,j=i; while(j<str.size()&&isdigit(str[j])) { x=x*10+(str[j]-'0'); j++; } num.push(x); i=j-1; } else if(str[i]=='(')//左括号无优先级，直接入栈 { op.push(str[i]); } //括号特殊，遇到左括号直接入栈，遇到右括号计算括号里面的 else if(str[i]==')') { while(op.top()!='(') eval(); op.pop(); //删除左括号 } else { //待入栈运算符优先级低，则先计算 while(op.size()&&h[op.top()]>=h[str[i]]) eval(); op.push(str[i]); } } while(op.size()) eval();//剩余的进行计算 cout<<num.top(); return 0; }
