使用无序遍历计算C++中的表达式树

#include <iostream>
#include <string>
#include <stack>
using namespace std;

// 表达式树的节点
struct Node {
    char value;         // 操作符或操作数的值
    Node* left;         // 左子树指针
    Node* right;        // 右子树指针
};

// 判断是否是操作符
bool isOperator(char c) {
    return (c == '+' || c == '-' || c == '*' || c == '/');
}

// 创建表达式树
Node* createExpressionTree(const string& postfix) {
    stack<Node*> stk;
    for (char c : postfix) {
        Node* node = new Node;
        node->value = c;
        node->left = node->right = nullptr;
        
        if (isOperator(c)) {
            node->right = stk.top();
            stk.pop();
            node->left = stk.top();
            stk.pop();
        }
        
        stk.push(node);
    }
    
    return stk.top();
}

// 无序遍历计算表达式树
int evaluateExpressionTree(Node* root) {
    if (!root) {
        return 0;
    }
    
    if (!root->left && !root->right) {
        return root->value - '0';
    }
    
    int leftValue = evaluateExpressionTree(root->left);
    int rightValue = evaluateExpressionTree(root->right);
    
    switch (root->value) {
        case '+': return leftValue + rightValue;
        case '-': return leftValue - rightValue;
        case '*': return leftValue * rightValue;
        case '/': return leftValue / rightValue;
    }
    
    return 0;   // 如果表达式树有误，返回0
}

int main() {
    string postfix = "34*5+";
    Node* root = createExpressionTree(postfix);
    int result = evaluateExpressionTree(root);
    
    cout << "表达式树计算结果: " << result << endl;
    
    return 0;
}