表达式树

三种表达式

在计算机做数值运算时，我们有三种常见的表达式，分别是中缀表达式、前缀表达式、后缀表达式。

中缀表达式

中缀表达式是我们通常在数学中使用的表达式表示方法，操作符位于两个操作数之间。例如，加法操作 3 + 4 通常表示为 "3 + 4"。中缀表达式具有运算符优先级规则，需要考虑括号来明确运算顺序。中缀表达式可以通过算法（如递归解析或运算符优先级解析器）转换为其他表达式形式，如前缀或后缀表达式。

示例： \[ (a + b) \times c \]

前缀表达式

前缀表达式，也被称为波兰记法（Polish Notation）。在前缀表达式中，运算符位于操作数之前，例如，加法操作 3 + 4 可以表示为"+ 3 4"。前缀表达式没有优先级问题，因为每个运算符都在其操作数之前，而计算前缀表达式通常需要使用栈数据结构来执行。

示例： \[ \times +\ a\ b\ c \]

后缀表达式

后缀表达式，也被称为逆波兰记法（Reverse Polish Notation，RPN）。在后缀表达式中，运算符位于操作数之后，例如，加法操作 3 + 4 可以表示为"3 4 +"。后缀表达式也不涉及运算符优先级，因此计算顺序是十分明确的，计算后缀表达式通常使用栈数据结构来执行。

示例： \[ a\ b\ + c\ \times \]

表达式树

以上三种表达式都可以相互转化并且使用特定的方法求值，我们在此不做赘述，那么我们是否可以将三种表达式统一为某种适合计算机运算的数据结构呢？我们在此引入表达式树（Expression Tree）。

表达式树是一种数据结构，用于表示数学表达式的层次结构，其中每个节点表示操作数或运算符，而边表示它们之间的关系。表达式树可以用来表示前缀、中缀或后缀表达式，并提供了一种有效的方式来表示和计算复杂的数学表达式。

以 \((a + b) \times c\) 为例，我们可以构造如下表达式树：

不难发现，表达式树有如下性质：

1. 叶节点只能是操作数，非叶节点只能是运算符；
2. 表达式树的非叶节点的度数只能是 2。

表达式 \(\to\) 表达式树

在这里我们以后缀表达式为例，展示一下表达式树的构建过程。

事实上，我们只需要创建一个栈，然后从左至右遍历表达式并重复以下步骤即可：

• 如果遇到操作数，创建操作数节点，并压入栈内；
• 如果遇到运算符，创建运算符节点，从栈内弹出两个元素分别做运算符节点的右节点和左节点；
• ...

如此重复，最后栈内会剩下唯一的节点，该节点就是表达式树的根节点。

代码实现：

#include <iostream>
#include <string>
#include <vector>
#include <stack>

namespace __expression_tree {
    enum node_type {
        // 节点类型
        OPEROTOR,
        NUMBER
    };

    struct ExpTreeNode {
        node_type type;
        union {
            char op;
            int val;
        };
        ExpTreeNode* left;
        ExpTreeNode* right;
        ExpTreeNode(node_type _type, int _val, ExpTreeNode* l = nullptr, ExpTreeNode* r = nullptr): type(_type), left(l), right(r) {
            if (type == OPEROTOR) {
                op = _val;
            }
            else {
                val = _val;
            }
        }
    };

    ExpTreeNode* suffix2tree(std::vector<std::string>& ex) {
        // 后缀表达式转化为表达式树
        std::stack<ExpTreeNode*> st;
        for (const auto& ele : ex) {
            ExpTreeNode* rt = nullptr;
            if (ele == "+" || ele == "-" || ele == "*" || ele == "/") {
                ExpTreeNode* r = st.top();
                st.pop();
                ExpTreeNode* l = st.top();
                st.pop();
                rt = new ExpTreeNode(OPEROTOR, ele[0], l, r);
            }
            else {
                rt = new ExpTreeNode(NUMBER, stoi(ele));
            }
            st.push(rt);
        }

        return st.top();
    }

    int compute(ExpTreeNode* root) {
        // 计算以 root 为根节点的表达式树的值
        if (root->type == NUMBER) return root->val;

        int l_val = compute(root->left), r_val = compute(root->right);
        switch (root->op) {
            case '+': return l_val + r_val;
            case '-': return l_val - r_val;
            case '*': return l_val * r_val;
            case '/': return l_val / r_val;
        }
        
        exit(1); // error
    }
}

using namespace __expression_tree;

int main() {
    std::vector<std::string> ex{"9", "8", "+", "2", "*", "8", "4", "/", "-"};
    ExpTreeNode* rt = suffix2tree(ex);

    std::cout << compute(rt) << '\n'; // (9 + 8) * 2 - 8 / 4 == 32

    return 0;
}

如果是前缀表达式，则只需从右往左遍历表达式，然后采取相同的步骤即可（左右子树的顺序上会有差异）。

如果是中缀表达式，可以考虑使用递归构造表达式树，也可以先将前缀表达式转化为后缀表达式，然后再转化为表达式树。

表达式树 \(\to\) 表达式

事实上，中缀表达式、前缀表达式、后缀表达式，本质上就是表达式树的中序遍历、前序遍历与后续遍历。

代码实现：

std::string tree2prefix(ExpTreeNode* root) {
    // 表达式树 -> 前缀表达式
    if (root->type == NUMBER) return std::to_string(root->val);

    return std::string(1, root->op) + " " + tree2prefix(root->left) + " " + tree2prefix(root->right);
}

std::string tree2infix(ExpTreeNode* root, char pre_op = 0) {
    // 表达式树 -> 中缀表达式
    if (root->type == NUMBER) return std::to_string(root->val);

    if ((root->op == '+' || root->op == '-') && (pre_op == '*' || pre_op == '/')) {
        return "(" + tree2infix(root->left, root->op) + " " + std::string(1, root->op) + " " + tree2infix(root->right, root->op) + ")";
    }
    
    return tree2infix(root->left, root->op) + " " + std::string(1, root->op) + " " + tree2infix(root->right, root->op);
}

std::string tree2sufix(ExpTreeNode* root) {
    // 表达式树 -> 后缀表达式
    if (root->type == NUMBER) return std::to_string(root->val);

    return tree2sufix(root->left) + " " + tree2sufix(root->right) + " " + std::string(1, root->op);
}