后缀表达式构建表达式树

后缀表达式（也叫逆波兰式）消除了运算符优先级和括号的歧义，适合用栈来处理。基于后缀表达式构建表达式树，是所有表达式类问题的通用解法。数学中常用的的中缀表达式（如 (1+2)*3-4/2）需要处理复杂的优先级和括号规则，直接解析难度大、容易出错。

一、基本原理

1. 核心算法思想

后缀表达式的本质是：运算符永远在它的两个操作数的后面。基于这个特性，我们可以用栈来辅助构建表达式树：

• 从左到右遍历后缀表达式的每一个元素（token）
• 遇到数字：它是一个叶子节点，直接压入栈中
• 遇到运算符：它是一个内部节点，从栈中弹出两个最近的节点作为它的左右孩子，然后将这个新的运算符节点压回栈中
• 遍历结束后，栈中只会剩下一个节点，就是整棵表达式树的根节点

2. 过程模拟演示

后缀表达式 1 2 + 3 * 4 2 / - ：

最终得到的完整表达式树：

        -
      /   \
     *     /
    / \   / \
   +   3 4   2
  / \
 1   2

二、模板代码

以下示例代码支持多位数、负数和加减乘除四则运算。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 2000010; // 足够容纳1e6长度表达式的所有节点

// 数组模拟表达式树节点
struct Node {
    bool is_num;    // true=数字节点，false=运算符节点
    int val;        // 数字节点的值
    char op;        // 运算符节点：+ - * /
    int l, r;       // 左右孩子下标，0表示无孩子
} tr[MAXN];

int tot; // 节点编号分配器，从1开始

// -------------------------- 1. 新建节点函数 --------------------------
// 新建数字节点，返回节点下标
int new_num(int v) {
    tot++;
    tr[tot].is_num = true;
    tr[tot].val = v;
    tr[tot].op = 0;
    tr[tot].l = tr[tot].r = 0;
    return tot;
}

// 新建二元运算符节点，返回节点下标
int new_op(char o, int left, int right) {
    tot++;
    tr[tot].is_num = false;
    tr[tot].op = o;
    tr[tot].l = left;
    tr[tot].r = right;
    return tot;
}

// -------------------------- 2. 后缀表达式构建表达式树 --------------------------
// 输入：空格分隔的后缀表达式拆分后的token数组
// 输出：根节点下标
int build_tree(vector<string>& post) {
    stack<int> st; // 栈存节点下标
    tot = 0;       // 重置节点计数器

    for (string& token : post) {
        // 情况1：数字节点（支持多位数、负数）
        if (isdigit(token[0]) || (token.size() > 1 && token[0] == '-')) {
            int num = stoll(token);
            st.push(new_num(num));
        }
        // 情况2：二元运算符节点 + - * /
        else {
            char op = token[0];
            // 注意：先弹的是右孩子，后弹的是左孩子
            int r = st.top(); st.pop();
            int l = st.top(); st.pop();
            st.push(new_op(op, l, r));
        }
    }

    return st.top(); // 栈顶即为整棵树的根节点
}

// -------------------------- 3. 后序遍历表达式树求值 --------------------------
int calculate(int u) {
    // 叶子节点（数字）直接返回值
    if (tr[u].is_num) {
        return tr[u].val;
    }

    // 先算左子树，再算右子树
    int left_val = calculate(tr[u].l);
    int right_val = calculate(tr[u].r);

    // 根据运算符计算当前节点值
    switch (tr[u].op) {
        case '+': return left_val + right_val;
        case '-': return left_val - right_val;
        case '*': return left_val * right_val;
        case '/': return left_val / right_val; // 整数除法向0取整
    }

    return 0; // 合法表达式不会走到这里
}

// -------------------------- 主函数 --------------------------
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // 读取空格分隔的后缀表达式
    string s;
    vector<string> post;
    while (cin >> s) {
        post.push_back(s);
    }

    // 核心两步
    int root = build_tree(post);    // 1. 后缀表达式建树
    int ans = calculate(root);      // 2. 后序遍历求值

    cout << ans << endl;

    return 0;
}

中缀表达式转后缀表达式

1 核心算法：调度场算法（Shunting-yard Algorithm）

中缀转后缀的标准算法是由Dijkstra发明的调度场算法，它通过一个运算符栈来管理运算符的优先级和括号，将中缀表达式线性转换为后缀表达式，时间复杂度为O(n)。

1.1 算法核心思想

调度场算法的本质是模拟人工转后缀表达式的顺序：

• 遇到数字直接加入后缀表达式
• 遇到运算符，将栈中所有优先级大于等于当前运算符的元素弹出加入后缀表达式，然后将当前运算符压栈
• 遇到左括号直接压栈
• 遇到右括号，不断弹出栈顶元素并加入后缀表达式，直到遇到左括号，最后弹出左括号（注意不要把左括号自己加进表达式了）
• 遍历结束后，将栈中剩余的所有运算符依次弹出并加入后缀表达式

1.2 运算符优先级定义

我们需要先定义每个运算符的优先级，优先级越高的运算符越先被计算：

• )不需要入栈，不参与讨论

1.3 转换过程演示

中缀表达式 (1+2)*3-4/2 ：

最终得到的后缀表达式：1 2 + 3 * 4 2 / -，和我们之前使用的完全一致。

2 实现代码

// -------------------------- 4. 中缀表达式转后缀表达式 --------------------------
// 运算符优先级：乘除(2) > 加减(1) > 括号(0)
int priority(char op) {
    if (op == '*' || op == '/') return 2;
    if (op == '+' || op == '-') return 1;
    return 0; // 左括号优先级最低
}

// 输入：无空格的中缀表达式字符串
// 输出：空格分隔的后缀表达式token数组
vector<string> infix_to_postfix(string s) {
    vector<string> post; // 后缀表达式结果
    stack<char> op;      // 运算符栈
    string ss = ""; // 用于稍后字符转字符串

    for (int i = 0; i < s.size(); i++) {
        char c = s[i];

        // 情况1：处理数字（支持多位数、负数）
        if (isdigit(c) || 
            // 负号判断：出现在表达式开头 或 左括号后面
            (c == '-' && (i == 0 || s[i-1] == '('))) {
            string num;
            if (c == '-') { // 处理负号
                num += '-';
                i++;
            }
            // 拼接多位数
            while (i < s.size() && isdigit(s[i])) {
                num += s[i];
                i++;
            }
            i--; // 回退一位，因为for循环会自动i++
            post.push_back(num);
        }
        // 情况2：遇到左括号，直接压栈
        else if (c == '(') {
            op.push(c);
        }
        // 情况3：遇到右括号，弹出直到左括号
        else if (c == ')') {
            while (op.top() != '(') {
                post.push_back(ss + op.top());
                op.pop();
            }
            op.pop(); // 弹出左括号，不加入后缀
        }
        // 情况4：遇到运算符 + - * /
        else {
            // 弹出所有栈顶优先级≥当前运算符的元素
            while (!op.empty() && priority(op.top()) >= priority(c)) {
                post.push_back(ss + op.top());
                op.pop();
            }
            op.push(c); // 当前运算符入栈
        }
    }

    // 弹出栈中剩余的所有运算符
    while (!op.empty()) {
        post.push_back(ss + op.top());
        op.pop();
    }

    return post;
}