题目链接
思路：
将中缀表达式转化为后缀表达式，完成表达式求值。
这里采用辅助栈的方法，将中缀表达式转化为后缀表达式：
给操作符设置优先级：
map<char,int>mp; mp['#']=0; mp['(']=mp[')']=1; mp['+']=mp['-']=2; mp['*']=mp['/']=3;这里设置了操作符#，并把优先级设为最低。将#放置在辅助栈的栈底，作用与链表中的头节点的作用类似。
在辅助栈中，从 栈底 到 ' ( ' 之前 和 ' ( ' 到 栈顶，每个操作符的优先级是严格递增的
开一个辅助栈，用来存放操作符。
栈对不同优先级的操作符采用不同策略：
如果当前操作符的优先级大于栈顶元素的 或者 当前操作符为 ' ( '，直接将操作符推入栈。
如果当前操作符的优先级小于等于栈顶元素的，那么将栈顶元素弹出成为后缀表达式，再将当前操作符推入栈。
如果当前操作符为 ' ) '，将栈里的元素弹出成为后缀表达式，知道碰到 ' ( '
#include <bits/stdc++.h> using namespace std; int main() { map<char,int>mp; mp['#']=-1; mp['(']=mp[')']=0; mp['+']=mp['-']=1; mp['*']=mp['/']=2; stack<char>sta; vector<string>ve; string str,ans; cin>>str; sta.push('#'); for(int i=0;i<str.size();i++) { if(isdigit(str[i])) ans+=str[i]; else { if(ans!="") ve.push_back(ans); ans.clear(); if(str[i]=='(') { sta.push('('); continue; } else if(str[i]==')') { while(sta.top()!='(') { ve.push_back(string(1,sta.top())); sta.pop(); } sta.pop(); continue; } while(mp[str[i]]<=mp[sta.top()]) { ve.push_back(string(1,sta.top())); sta.pop(); } sta.push(str[i]); } } while(sta.top()!='#') { ve.push_back(string(1,sta.top())); sta.pop(); } stack<int> st; for(int i=0;i<ve.size();i++) { if(!isdigit(ve[i][0])) { int b=st.top(); st.pop(); int a=st.top(); st.pop(); if(ve[i]=="+") a+=b; else if(ve[i]=="-") a-=b; else if(ve[i]=="*") a*=b; else if(ve[i]=="/") a/=b; st.push(a); } else { int num=0; for(int j=0;j<ve[i].size();j++) num=num*10+ve[i][j]-'0'; st.push(num); } } cout<<st.top(); return 0; }
