3.1 模拟栈+表达式求值

模拟栈

题目链接

栈的数组模拟非常简单，不详细描述
设置一个指针指向栈顶第一个元素即可

STL中stack实现已经更新在STL_Stack

#include<iostream>
#include<string>using namespace std;const int N=1e5+1;
int m;
string s;
int stack[N];
int p;//指针,指向栈顶元素 int main(){cin>>m;p=0;//刚开始p=0说明栈内为空 while(m--){cin>>s;if(s=="push"){int x;cin>>x;stack[++p]=x;}else if(s=="pop"){p--;}else if(s=="empty"){if(p==0)cout<<"YES"<<"\n";elsecout<<"NO"<<"\n";}else if(s=="query"){cout<<stack[p]<<"\n";}}return 0;
}

表达式求值

思路：
关于表达式求值详解可见bilibili视频讲解
需要设置一个符号栈、一个数字栈
其中数字栈比较简单，只要扫描到数字直接入栈即可
对于符号栈，要注意若是空栈或者当前是左括号，符号直接可以进
每次扫描到符号想入栈时，如果扫描的符号优先级大于当前栈顶的元素，那么可以直接入栈（想象成优先级高的可以压住优先级低的），但是如果平级，即+和+、-和-这样的，那么就不能入栈，需要将符号栈中元素不断pop出直到能压住或者栈空（毕竟符号优先级相同，谁都不服谁，那么先入栈的先出去吧）
如果有符号出栈，那么就立即将其和数字栈中的数字组合，求得的值再次压入数字栈中
直到所有元素都被扫描完，然后把符号栈中的元素清理干净即可

实现代码

具体思路在代码中写的很清楚了

#include<iostream>
#include<string>
#include<algorithm>
#include<stack>
#include<unordered_map>using namespace std;stack <int> num_s;//数字栈 
stack <char> ope_s;//运算符栈 
unordered_map <char,int> h {{'+',1},{'-',1},{'*',2},{'/',2}};//定义优先级映射集 void eval(){//计算、当有符号出栈时将其和数字栈中的元素结合计算//此时注意元素在栈中的顺序，因为对于除法来说a/b和b/a不一样 int a,b;//两个需要被运算的数字 char ope;//运算符 //第二个数字 b=num_s.top();num_s.pop();//第一个数字 a=num_s.top();num_s.pop();//运算符ope=ope_s.top();ope_s.pop(); //进行运算int result;if(ope=='+')result=a+b;if(ope=='-')result=a-b;if(ope=='*')result=a*b;if(ope=='/')result=a/b;//将计算结果压入栈中 num_s.push(result); }int main(){string s;cin>>s;//读取表达式 for(int i=0;i<s.size();i++){//从头扫描表达式 if(isdigit(s[i])){//isdigit()用于判断该元素是否为数字int j=i,x=0;//因为数字可能为多位数，因此需要用while读取，并且将字符串中的字符转为int以此用于计算 while(j<s.size()&&isdigit(s[j])){x=x*10+s[j]-'0';j++;}//读取完就将其放入栈中num_s.push(x);//此时j指向一个操作符，由于循环结束时i会++,因此这里需要将i的值设为j-1，//这样在i++后，下一次循环扫描的就是操作符了 i=j-1;}else if(s[i]=='('){//如果是左括号可以直接压入栈ope_s.push(s[i]); }else if(s[i]==')'){//如果是右括号那么就要将左右括号中间所有的操作符弹出并计算while(ope_s.top()!='('&&!ope_s.empty()){//当栈顶不为'('且不为空 eval();//计算，计算的时候会自动pop符号 } //最后要把'(' pop出去ope_s.pop(); }else{//如果是操作符，那么就要判断操作符和栈顶元素优先级while(!ope_s.empty()&&h[ope_s.top()]>=h[s[i]]){//如果当前扫描的元素不比栈顶元素大，那么就要eval（弹出栈顶元素）直到s[i]能压住栈顶元素 eval();} //如果扫描元素能够压住栈顶元素，那么直接入栈ope_s.push(s[i]); }}	//扫描完了，处理符号栈中剩余元素while(!ope_s.empty()){eval();} cout<<num_s.top()<<endl;return 0;
}