本文用于记录个人算法竞赛学习，仅供参考

 对于这个过程可以抽象为一颗二叉树来理解后序的做法（理解过程，但不是最终解法）

对于  1 + 2 * 2 - 1，可以通过中序遍历构建出一颗二叉树

 计算过程为

 

对于上述过程可以总结出一个计算规律：

1.叶子节点是数字，根节点是运算符

2.这颗二叉树自根节点到叶子节点的运算符的优先级是递增的，根节点的优先级最低

但这通过已经构建好的二叉树再来进行计算的，要计算其他表达式时，再人为构建一颗树是非常麻烦的，所以可以通过表达式从左向右扫描，通过优先级来构建一颗数，这个过程是通过栈来实现的。

1.扫描过程中，当前运算符优先级小于等于前一个运算符（栈顶的运算符）优先级时，代表当前运算符的的子树已经遍历完了，子树内的数字和符号合并计算成一个数值并加入栈内

2.当前运算符的优先级大于前一个运算符（栈顶的运算符）优先级时，代表子树还没有遍历完，直接将当前运算符入栈，等待后序操作

3.遇到’（‘时直接入栈，等待有序遇到’）‘再进行操作

4.遇到’）‘时求出（）内的值，并入栈

代码如下

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <stack>
using namespace std;const int N = 100010;
//存数字的栈和存符号的栈
stack<int> nums;
stack<char> op;
//优先级
unordered_map<char,int> pr = {{'+',1},{'-',1},{'*',2},{'/',2}};//将两个数进行操作合并
void eval()
{auto b = nums.top();    nums.pop();auto a = nums.top();    nums.pop();auto c = op.top();      op.pop();if(c == '+'){nums.push(a + b);}else if(c == '-'){nums.push(a - b);}else if(c == '*'){nums.push(a * b);}else if(c == '/'){nums.push(a / b);}
}int main()
{string s;cin >> s;//从左向右扫描for(int i = 0; i < s.size(); i++){auto ch = s[i];//当前字符是数字if(isdigit(ch)){//读取数字串称为一个数字int x = 0;int j = i;while(j < s.size() && isdigit(s[j])){x = x * 10 + s[j++] - '0';}i = j - 1;nums.push(x);}//当前字符是'('else if(s[i] == '(')op.push('(');//求括号内的值else if(s[i] == ')'){while(op.top() != '('){eval();}//弹出'('op.pop();}//" + - * / "else{//当前运算符优先级小于前一个运算符（栈顶）的优先级while(!op.empty() && pr[s[i]] <= pr[op.top()]){eval();}//当前运算符入栈（如果当前运算符优先级大于前一个运算符优先级就直接入栈）op.push(s[i]);}}//将剩下的数字和运算符从右向左依次处理//数字最后剩下一个，运算符最后一个不剩while(op.size()){eval();}cout << nums.top() << endl;return 0;
}