C++如何实现一个简单的表达式树-C++-PHP中文网

表达式树是节点含义固定的二叉树：叶子必为操作数（数字或变量），非叶子必为二元运算符，构造需满足语义约束；普通二叉树无此限制。

c++如何实现一个简单的表达式树

什么是表达式树，它和普通二叉树有什么区别

表达式树本质是二叉树，但节点含义固定：叶子节点一定是操作数（如 3、x），非叶子节点一定是运算符（如 +、*），且每个运算符节点必须有且仅有两个子节点（即使是一元运算符如负号，也常被建模为二元结构，右子为空或设为占位符）。这决定了它的构造不能随意——你不能把 + 当作叶子插入，也不能让 5 节点有两个子节点。

常见错误是直接套用通用二叉树模板，忽略语义约束，结果在遍历或求值时崩溃或逻辑错乱。

如何设计节点结构并支持基本运算符

节点类型需区分操作数与运算符，推荐用枚举 + 联合体（或 std::variant）避免虚函数开销。例如：

enum class NodeType { NUM, VAR, OP };
struct Node {
    NodeType type;
    union {
        double num_val;   // 仅 type == NUM 时有效
        char var_name;    // 仅 type == VAR 时有效（简化起见用单字符）
        char op;          // 仅 type == OP 时有效，如 '+'、'*'
    };
    Node* left = nullptr;
    Node* right = nullptr;
};

关键点：

op 只能是 '+'、'-'、'*'、'/' 等有限集合，构造时必须校验
叶子节点（NUM 或 VAR）的 left 和 right 必须为 nullptr，否则后续求值逻辑会误判
若需支持变量代入，VAR 节点应在求值时查表（如传入 std::map<char double></char>）

如何从中缀表达式字符串构建树（不带括号的简化版）

完整中缀转表达式树需处理优先级和括号，复杂度高。实际开发中，更可行的是先转后缀（逆波兰），再用栈构建——这是稳定、易调试的路径。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

假设输入是空格分隔的后缀表达式，如 "3 4 + 2 *"，构建逻辑如下：

std::stack<node> st;
for (const auto& token : tokens) {
    if (token == "+" || token == "-" || token == "*" || token == "/") {
        Node* right = st.top(); st.pop();
        Node* left = st.top(); st.pop();
        Node* op_node = new Node{NodeType::OP, .op = token[0], left, right};
        st.push(op_node);
    } else {
        Node* leaf = new Node{NodeType::NUM, .num_val = std::stod(token)};
        st.push(leaf);
    }
}
Node* root = st.top();
</node>

注意：

后缀表达式保证了运算符总在操作数之后，因此每次取两个栈顶元素作为左右子树，左操作数先弹出（因为栈是后进先出）
必须确保 tokens 是合法后缀序列，否则栈空时调用 top() 会崩溃
若含变量（如 "x 2 +"），需额外判断 token 是否为字母，走 NodeType::VAR 分支

如何安全求值并避免除零或类型错误

递归求值函数必须检查节点类型，并对运算符做分支处理：

double eval(const Node* n, const std::map<char double>& vars) {
    if (!n) return 0.0;
    switch (n->type) {
        case NodeType::NUM: return n->num_val;
        case NodeType::VAR: return vars.at(n->var_name); // 抛出 std::out_of_range 若未定义
        case NodeType::OP:
            double l = eval(n->left, vars);
            double r = eval(n->right, vars);
            switch (n->op) {
                case '+': return l + r;
                case '-': return l - r;
                case '*': return l * r;
                case '/': 
                    if (r == 0.0) throw std::runtime_error("division by zero");
                    return l / r;
                default: throw std::runtime_error("unknown operator");
            }
    }
    return 0.0;
}
</char>

容易忽略的细节：