算法基础之表达式求值

算法基础之表达式求值

• 中序表达式求值 用栈

  • 

  • 将字符和数字分别用栈存储 由下往上计算

  • 左子树算完再算右子树 判断方法：当前符号优先级<=前一个符号优先级 则左右子树已遍历完

  •   #include<iostream>#include<cstring>#include<stack>#include<algorithm>#include<unordered_map>using namespace std;//分别存储数字和符号stack<int> num;stack<int> op;void eval(){//先取b 再取a auto b = num.top(); num.pop();auto a = num.top(); num.pop();auto c = op.top(); op.pop();int x;if(c=='+') x=a+b;else if(c=='-') x=a-b;else if(c=='*') x=a*b;else x=a/b;//算完放回栈 作为一颗子树的值num.push(x);}int main(){//用哈希表存储 字符及其优先级unordered_map<char,int> pr{{'+',1},{'-',1},{'*',2},{'/',2}};string str;cin>>str;for(int i=0;i<str.size();i++){auto c =str[i];//数字if(isdigit(c)){int x=0,j=i;//可能是连续的数字 一个大数while(j<str.size()&&isdigit(str[j])){x = x*10 + str[j++] - '0';}//因为退出这个if以后 j++已经执行 i++又做自增 所以会多1 要减去i = j-1;num.push(x);}//左括号放进栈else if(c=='(') op.push(c);//有括号执行之前存入的符号else if(c==')'){while(op.top() != '(') eval();//删掉左括号op.pop();}//符号else {//如果栈顶运算符优先级较高,先操作栈顶元素再入栈while(op.size()&&pr[op.top()]>=pr[c]) eval();//如果栈顶运算符优先级较低,直接入栈op.push(c);}}//没有操作完的继续操作(最外层没有括号的没操作)while(op.size()) eval();//栈顶元素为答案cout<<num.top()<<endl;return 0;}