0. 表达式树

在一颗树中，叶子节点都是操作数，所有的非叶子节点都是运算符，这样的树叫做表达式树。
如图:

1. 后缀表达式计算

后缀表达式：也叫逆波兰表达式，是表达式树的后序遍历。

在计算时，不用还原出整棵树，可用一个栈来辅助计算。

leetcode 150. 逆波兰表达式求值

class Solution {
public:

    int evalRPN(vector<string>& tokens) {

        int st[10005];
        int tt = 0;

        for( auto &x : tokens){
            if(x == "+" || x == "-" || x == "*" || x == "/") {
                int b = st[tt--];
                int a = st[tt--];
                if(x == "+") st[++tt] = a + b;
                else if(x == "-") st[++tt] = a - b;
                else if(x == "*") st[++tt] = a * b;
                else st[++tt] = a / b;
            }
            else st[++tt] = stoi(x);
        }
        return st[tt];

    }
};

2. 中缀表达式计算

法1:

  • 转成后缀表达式计算。

法2：

直接利用表达式树计算结果
需要两个栈：数字栈 和 符号栈

伪代码：

if 是数字
	入栈
else if 左括号 
	入栈
else if 右括号
	while 栈顶元素不是左括号
		消耗栈顶两个数字 和 一个符号 做一次计算
	弹出左括号
else //是普通符号
	while 当前符号优先级 <= 栈顶符号优先级
		消耗栈顶两个数字 和 一个符号 做一次计算（把之前可以计算的  都计算出来，用作下一次计算）
	当前符号入栈

/*
 * @Brief: 
 * @Author: 
 * @Date: 2021-07-14 
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <stack>
#include <unordered_map>

using namespace std;

stack<int> num;
stack<char> op;

void calc(){
	int b = num.top(); num.pop();
	int a = num.top(); num.pop();
	
	char c = op.top(); op.pop();
	
	if(c == '+') num.push(a + b);
	else if(c == '-') num.push(a - b);
	else if(c == '*') num.push(a * b);
	else num.push(a / b);
	
}

int main(){

	string sc;
	cin >> sc;

	unordered_map<char, int> mp = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};

	for(int i = 0; i < sc.size(); i++){
		auto c = sc[i];
		if( isdigit(c) ){
			int x = 0, j = i;
			while(j < sc.size() && isdigit(sc[j])) x = x * 10 + sc[j++] -'0';

			num.push(x);

			i = j - 1;
		}else if(c == '(') op.push(c);
		else if(c == ')'){
		    while(op.top() != '(') calc();
		    
		    // 弹出左括号
		    op.pop();
		      
		} else {
			// 普通运算符
			while(op.size() && mp[c] <= mp[op.top()]) calc();   // 把之前可以计算的  都计算出来
			op.push(c);

		}

	}
	while(op.size()) calc();

	cout << num.top() << endl;

	return 0;
}