C++代码实现中缀表达式求值（基于中缀表达式转后缀表达式）
样例输入：3*(2+5)
样例输出：21
代码：#include <bits/stdc++.h>
using namespace std;
string change(string s)
{
stack<char> st;
string ans;
st.push('#');//防止数据溢出!!
int pri[350];
pri['+']=1;
pri['-']=1;
pri['*']=2;
pri['/']=2;
pri['(']=0;
pri[')']=0;
pri['#']=-1;//定义优先级
for(int i=0;i<s.size();i++)
{
bool isnum=false;
while(s[i]>='0'&& s[i]<='9')
{
ans=ans+s[i];
i++;
isnum=true;
}
if(isnum) ans=ans+' ';//运算符，直接输出
if(i>=s.size()) break;
if(s[i]=='(') st.push(s[i]);
else if(s[i]==')')
{
while(st.top()!='(')
{
ans=ans+st.top()+' ';
st.pop();
}
st.pop();
}
else
{
if(pri[s[i]]>pri[st.top()]) st.push(s[i]);
else
{
while(pri[s[i]]<=pri[st.top()])//直到优先级>栈顶运算符
{
ans=ans+st.top()+' ';
st.pop();//将栈顶运算符弹出并输出
}
st.push(s[i]);//再将该运算符s[i]入栈
}
}
}
while(st.size()>1)
{
ans=ans+st.top()+' ';
st.pop();
}//对象处理完毕，按顺序弹出并输出栈中所有运算符
return ans;
}
int value(string s)
{
stack<int> st;
for(int i=0;i<s.size();i++)
{
int t=0;
bool isnum=false;
while(s[i]>='0'&& s[i]<='9')
{
t=t*10+s[i]-'0';
i++;
isnum=true;
}
if(isnum) st.push(t);
if(s[i]=='+')
{
int t1=st.top();
st.pop();
int t2=st.top();
st.pop();
st.push(t2+t1);
}
if(s[i]=='-')
{
int t1=st.top();
st.pop();
int t2=st.top();
st.pop();
st.push(t2-t1);
}
if(s[i]=='*')
{
int t1=st.top();
st.pop();
int t2=st.top();
st.pop();
st.push(t2*t1);
}
if(s[i]=='/')
{
int t1=st.top();
st.pop();
int t2=st.top();
st.pop();
st.push(t2/t1);
}
}
return st.top();
}
int main()
{
string s,ans;
getline(cin,s);
ans=change(s);
cout<<value(ans);
return 0;
}
