#include #include #include #include #include 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 infixToPostfix(const string& s) { vector postfix; stack 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& postfix) { stack 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 postfix = infixToPostfix(expr); // 后缀 → 表达式树 ExprNode* root = buildExpressionTree(postfix); // 输出表达式值 cout << evaluate(root) << '\n'; // 可选:输出中序遍历结果 // inorder(root); return 0; }