1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

class Solution
{
public:
    std::stack<int> nums;         // 存储操作数
    std::stack<char> op;          // 存储操作符

    // 执行栈顶一次运算
    void eval()
    {
        int b = nums.top(); nums.pop();
        int a = nums.top(); nums.pop();
        char c = op.top(); op.pop();
        if (c == '+')
            nums.push(a + b);
        else if (c == '-')
            nums.push(a - b);
        else if (c == '*')
            nums.push(a * b);
        else
            nums.push(a / b);
    }

    // 字符串替换函数
    void replace(std::string& s, std::string src, std::string dest)
    {
        int pos = s.find(src), n = src.size();
        while (pos != std::string::npos)
        {
            s.replace(pos, n, dest);
            pos = s.find(src);
        }
    }

    // 主函数
    int calculate(string s)
    {
        // 去掉空格，处理括号中的正负号
        replace(s, " ", "");
        replace(s, "(+", "(0+");
        replace(s, "(-", "(0-");
        nums.push(0);  // 初始化 nums 栈，避免边界条件

        // 定义操作符优先级
        std::unordered_map<char, int> priority_op{{'-', 1}, {'+', 1}, {'/', 2}, {'*', 2}};

        // 遍历表达式
        for (int i = 0; i < s.size(); ++i)
        {
            if (isdigit(s[i]))
            { // 处理数字
                int num = 0, j = i;
                while (j < s.size() && isdigit(s[j]))
                    num = num * 10 + (s[j++] - '0');
                nums.push(num); // 数字入栈
                i = j - 1;      // 更新索引
            }
            else if (s[i] == '(')
            { // 左括号直接入栈
                op.push(s[i]);
            } else if (s[i] == ')')
            { // 右括号
                while (op.size() && op.top() != '(')
                    eval(); // 计算括号内表达式
                op.pop(); // 弹出左括号
            }
            else
            { // 遇到操作符
                while (op.size() && op.top() != '(' && priority_op[op.top()] >= priority_op[s[i]])
                    eval(); // 优先级高于当前操作符时，计算
                op.push(s[i]); // 当前操作符入栈
            }
        }

        // 清算剩余操作
        while (op.size())
            eval();

        return nums.top();
    }
};