保研机试备考五:表达式求值
AcWing 3302. 表达式求值
题目
https://www.acwing.com/problem/content/3305/
思路
代码
#include<iostream>
#include<cstring>
#include<unordered_map>
#include<stack>
using namespace std;
stack<char> op; //符号栈
stack<int> num; //数字栈
unordered_map<char,int> pr={{'+',1},{'-',1},{'*',2},{'/',2}}; //定义符号优先级
void eval() //进行一次运算
{
int b=num.top(); num.pop();
int a=num.top(); num.pop();
char oper=op.top(); op.pop();
int temp;
if(oper=='+') temp=a+b;
else if(oper=='-') temp=a-b;
else if(oper=='*') temp=a*b;
else temp=a/b;
num.push(temp);
}
int main()
{
string s;
cin>>s;
int i=0;
while(i<s.size())
{
if(isdigit(s[i])) //如果是数字,压入数字栈
{
int j=i,x=0;
while(j<s.size()&&isdigit(s[j])) //取出完整的数字
{
x=x*10+s[j]-'0';
j++;
}
num.push(x); //记得把数字压栈
i=j-1; //j得减1,防止与下面的i++重合,而多加了1
}
else if(s[i]=='(') op.push(s[i]); //如果是左括号,直接压栈
else if(s[i]==')') //如果是右括号,一直处理,知道碰到左括号
{
while(op.top()!='(') eval();
op.pop(); //记得把左括号弹栈
}
else //碰到+、-、*、/
{ //注意不要让符号栈都没了还在处理
while(op.size()&&op.top()!='('&&pr[op.top()]>=pr[s[i]]) //一直处理直到碰到左括号或者栈顶部的优先级比它小
eval();
op.push(s[i]); //符号入栈
}
i++;
}
while(op.size()) //遍历完一遍字符串,最后可能遍历完了,符号栈里还有运算没处理,最后收尾处理一下
eval();
printf("%d",num.top()); //最后两个栈,只有数字栈里有值,即为最终答案
return 0;
}