Data-Structure/模板/树/表达式树.cpp

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

using namespace std;

/*
    表达式树节点
*/
struct ExprNode {
    char op;          // 运算符，若是操作数则无意义
    int val;          // 操作数值，仅在叶子节点有效
    ExprNode* left;
    ExprNode* right;

    // 构造操作数节点
    ExprNode(int v) : op(0), val(v), left(nullptr), right(nullptr) {}

    // 构造运算符节点
    ExprNode(char c, ExprNode* l, ExprNode* r)
        : op(c), val(0), left(l), right(r) {}
};

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

/*
    运算符优先级
*/
int priority(char c) {
    if (c == '+' || c == '-') return 1;
    if (c == '*' || c == '/') return 2;
    return 0;
}

/*
    中缀表达式转后缀表达式（Shunting-yard 算法）
*/
vector<string> infixToPostfix(const string& s) {
    vector<string> postfix;
    stack<char> ops;

    for (int i = 0; i < (int)s.size(); ) {

        // 读取数字（支持多位数）
        if (isdigit(s[i])) {
            int num = 0;
            while (i < (int)s.size() && isdigit(s[i])) {
                num = num * 10 + (s[i] - '0');
                i++;
            }
            postfix.push_back(to_string(num));
        }
        // 左括号直接入栈
        else if (s[i] == '(') {
            ops.push(s[i]);
            i++;
        }
        // 右括号：弹到遇见左括号
        else if (s[i] == ')') {
            while (!ops.empty() && ops.top() != '(') {
                postfix.push_back(string(1, ops.top()));
                ops.pop();
            }
            ops.pop(); // 弹出 '('
            i++;
        }
        // 运算符
        else if (isOperator(s[i])) {
            while (!ops.empty() &&
                   priority(ops.top()) >= priority(s[i])) {
                postfix.push_back(string(1, ops.top()));
                ops.pop();
            }
            ops.push(s[i]);
            i++;
        }
        // 跳过空格等非法字符
        else {
            i++;
        }
    }

    // 清空操作符栈
    while (!ops.empty()) {
        postfix.push_back(string(1, ops.top()));
        ops.pop();
    }

    return postfix;
}

/*
    后缀表达式构建表达式树
*/
ExprNode* buildExpressionTree(const vector<string>& postfix) {
    stack<ExprNode*> st;

    for (auto& token : postfix) {
        // 操作数
        if (isdigit(token[0])) {
            st.push(new ExprNode(stoi(token)));
        }
        // 运算符
        else {
            ExprNode* right = st.top(); st.pop();
            ExprNode* left = st.top(); st.pop();
            st.push(new ExprNode(token[0], left, right));
        }
    }

    return st.top();
}

/*
    递归计算表达式树的值
*/
int evaluate(ExprNode* root) {
    if (!root) return 0;

    // 叶子节点：操作数
    if (root->op == 0) {
        return root->val;
    }

    int l = evaluate(root->left);
    int r = evaluate(root->right);

    switch (root->op) {
        case '+': return l + r;
        case '-': return l - r;
        case '*': return l * r;
        case '/': return l / r;  // 默认题目保证可整除
    }
    return 0;
}

/*
    中序遍历（带括号，便于验证结构）
*/
void inorder(ExprNode* root) {
    if (!root) return;
    if (root->op) cout << '(';
    inorder(root->left);
    if (root->op) cout << root->op;
    else cout << root->val;
    inorder(root->right);
    if (root->op) cout << ')';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string expr;
    getline(cin, expr);  // 读取一整行表达式

    // 中缀 → 后缀
    vector<string> postfix = infixToPostfix(expr);

    // 后缀 → 表达式树
    ExprNode* root = buildExpressionTree(postfix);

    // 输出表达式值
    cout << evaluate(root) << '\n';

    // 可选：输出中序遍历结果
    // inorder(root);

    return 0;
}