计算表达式

一、算法思想

对于「任何表达式」而言，我们都使用两个栈 nums 和 ops：

• nums ： 存放所有的数字；
• ops ：存放所有的数字以外的操作。

然后从前往后做，对遍历到的字符做分情况讨论：

• 数字：从当前位置开始继续往后取，将整一个连续数字整体取出，加入 nums；
• (：直接加入 ops 中，等待与之匹配的 )；
• )：使用现有的 nums 和 ops 进行计算，直到遇到左边最近的一个左括号为止，计算结果放到 nums；
• + - * /：需要将操作放入 ops 中。在放入之前先把栈内可以算的都算掉（只有「栈内运算符」比「当前运算符」优先级高 / 同等，才进行运算），使用现有的 nums 和 ops 进行计算，直到没有操作或者遇到左括号，计算结果放到 nums。

注意

在具体应用时，可以根据输入条件做以下处理，这里为了保证模板的简洁性只保留了主体代码。

• 由于第一个数可能是负数，为了减少边界判断。一个小技巧是先往 nums 添加一个 0；
• 为防止 () 内出现的首个字符为运算符，将所有的空格去掉，并将 (- 替换为 (0-，(+ 替换为 (0+；
• 从理论上分析，nums 最好存放的是 long，而不是 int。因为可能存在中间结果溢出，最终答案不溢出的情况。

二、算法模板

C++

stack<int> nums;
stack<char> ops;

unordered_map<char, int> pr = {
    {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}
};

void eval()
{
    auto b = nums.top(); nums.pop();
    auto a = nums.top(); nums.pop();
    auto c = ops.top(); ops.pop();
    
    int x;
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;
    
    nums.push(x);
}

int calculate(string s)
{
    for (int i = 0; i < s.length(); i++) {
        auto c = s[i];
        if (isdigit(c)) {
            int x = 0, j = i;
            while (j < s.length() && isdigit(s[j])) {
                x = x * 10 + s[j++] - '0';
            }
            i = j - 1;
            nums.push(x);
        } else if (c == '(') {
            ops.push(c);
        } else if (c == ')') {
            while (ops.top() != '(') eval();
            ops.pop();
        } else {
            while (ops.size() && pr[ops.top()] >= pr[c]) eval();
            ops.push(c);
        }
    }
    while (ops.size()) eval();
    
    return nums.top();
}

三、代码实战

AcWing 0828

---

题目：模拟栈

给定一个表达式，其中运算符仅包含 +,-,*,/（加、减、乘、整除），可能包含括号，请你求出表达式的最终值。

注意：

• 数据保证给定的表达式合法。
• 题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2、(2+2)*(-(1+1)+2) 之类表达式均不会出现。
• 题目保证表达式中所有数字均为正整数。
• 题目保证表达式在中间计算过程以及结果中，均不超过 $2^{31}−1$。
• 题目中的整除是指向 $0$ 取整，也就是说对于大于 $0$ 的结果向下取整，例如 5/3=1，对于小于 $0$ 的结果向上取整，例如 5/(1−4)=−1。

输入格式

共一行，为给定表达式。

输出格式

共一行，为表达式的结果。

数据范围

表达式的长度不超过 $10^5$。

输入样例：

(2+2)*(1+1)

输出样例：

8

解答代码：

#include <iostream>
#include <stack>
#include <unordered_map>

using namespace std;


stack<int> nums;
stack<char> ops;

unordered_map<char, int> pr = {
    {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}
};

void eval()
{
    auto b = nums.top(); nums.pop();
    auto a = nums.top(); nums.pop();
    auto c = ops.top(); ops.pop();
    
    int x;
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;
    
    nums.push(x);
}

int calculate(string s)
{
    for (int i = 0; i < s.length(); i++) {
        auto c = s[i];
        if (isdigit(c)) {
            int x = 0, j = i;
            while (j < s.length() && isdigit(s[j])) {
                x = x * 10 + s[j++] - '0';
            }
            i = j - 1;
            nums.push(x);
        } else if (c == '(') {
            ops.push(c);
        } else if (c == ')') {
            while (ops.top() != '(') eval();
            ops.pop();
        } else {
            while (ops.size() && pr[ops.top()] >= pr[c]) eval();
            ops.push(c);
        }
    }
    while (ops.size()) eval();
    
    return nums.top();
}

int main()
{
    string s;
    cin >> s;
    
    cout << calculate(s) << endl;
    
    return 0;
}