参考文献
作者:Hasity
链接:https://www.acwing.com/solution/content/40978/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
C++ 代码
#include<iostream>
#include<cstring>
#include<stack>
#include<unordered_map>
using namespace std;
stack<int> num;
stack<char> op;
unordered_map<char,int> heap{{'+',1},{'-',1},{'*',2},{'/',2}};//优先级表
void cal()//计算
{
char p;
int first,second,result;
second=num.top();//因为栈先进后出,所以栈顶是第二个计算数
num.pop();
first=num.top();
num.pop();
p=op.top();
op.pop();
if(p=='+')
{
result=first+second;
}
else if(p=='-')
{
result=first-second;
}
else if(p=='*')
{
result=first*second;
}
else if(p=='/')
{
result=first/second;
}
num.push(result);//将结果重新推入栈进行之后的运算
}
int main()
{
string s;
cin>>s;
int x;
for(int i=0;i<s.size();i++)
{
int j=i;//j用于记录当前读取位置,因为数字不止一位
x=0;//x用于记录数字
if(s[j]>='0'&&s[j]<='9')
{
while(j<s.size()&&s[j]>='0'&&s[j]<='9')
{
x=x*10+s[j++]-'0';
}
num.push(x);
i=j-1;//因为i会++,但是当前j位置还未读取
}
else if(s[i]=='(')
{
op.push(s[i]);//左括号无需操作
}
else if(s[i]==')')
{
while(op.top()!='(')//一直计算直到遇到的第一个左括号出栈
{
cal();
}
op.pop();
}
else //只有当前运算符优先级小于栈顶时才计算,否则入栈(栈为空也入栈)
{
while(op.size()&&heap[op.top()]>=heap[s[i]])//栈不为空且当前优先级大于栈顶优先级
{
cal();
}
op.push(s[i]);
}
}
//当全部读取完时计算不一定结束,一直计算直至操作数栈为空
while(op.size())
{
cal();
}
cout<<num.top()<<endl;//最终结果存在了num的栈顶,也是当前num中唯一的元素
return 0;
}