题解 | #表达式求值#

题目链接

整数计算器

题目描述

请写一个整数计算器，支持加、减、乘三种运算和括号。

数据范围：字符串长度满足 1 <= len <= 1000，保证计算结果始终在整型范围内。

输入格式 一个字符串 s，代表待计算的表达式。

输出格式 一个整数，代表表达式的值。

示例

输入: "(2*(3-4))*5"
输出: -10
输入: 3+2*3*4-1
输出: 26

解题思路

这是一个经典的表达式求值问题，最通用的解法是使用双栈法。

一个栈 nums 用来存放数字（操作数）。
另一个栈 ops 用来存放操作符和括号。

算法的核心思想是，从左到右遍历表达式字符串，根据当前字符的类型执行不同的操作，同时利用操作符的优先级规则来决定何时进行计算。

算法步骤：

定义优先级: 首先，我们需要定义操作符的优先级。乘法 * 的优先级高于加法 + 和减法 -。我们可以用一个哈希表来存储：{'*': 2, '+': 1, '-': 1}。
遍历表达式: 我们从左到右遍历字符串中的每个字符。
- 如果当前字符是数字，则向后解析，直到得到一个完整的整数，然后将其压入 nums 栈。
- 如果当前字符是左括号 (，直接将其压入 ops 栈。
- 如果当前字符是右括号 )，这是一个计算信号。我们从 ops 栈顶弹出一个操作符，再从 nums 栈顶弹出两个数字，进行计算，然后将结果压回 nums 栈。重复此过程，直到 ops 栈顶是左括号 ( 为止，最后将这个 ( 弹出。
- 如果当前字符是操作符（+, -, *）:
  - 在将其压入 ops 栈之前，先进行检查：只要 ops 栈不为空，且栈顶不是 (，并且栈顶操作符的优先级不低于当前操作符的优先级，就持续进行第3步中的"弹栈计算"过程。
  - 检查结束后，将当前操作符压入 ops 栈。
最终计算: 当遍历完整个字符串后，ops 栈中可能还剩下一些操作符。我们按照第3步中的"弹栈计算"方法，清空 ops 栈。
返回结果: 最后，nums 栈中只会剩下一个数字，这就是整个表达式的最终结果。

这个算法可以正确处理操作符的优先级和括号嵌套，是解决此类问题的标准模板。

代码

cpp
java
python

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int solve(string s) {
        stack<long long> nums;
        stack<char> ops;
        map<char, int> precedence = {{'+', 1}, {'-', 1}, {'*', 2}};

        auto calculate = [&]() {
            long long num2 = nums.top(); nums.pop();
            long long num1 = nums.top(); nums.pop();
            char op = ops.top(); ops.pop();
            if (op == '+') nums.push(num1 + num2);
            else if (op == '-') nums.push(num1 - num2);
            else if (op == '*') nums.push(num1 * num2);
        };

        for (int i = 0; i < s.length(); ++i) {
            char c = s[i];
            if (isdigit(c)) {
                long long num = 0;
                while (i < s.length() && isdigit(s[i])) {
                    num = num * 10 + (s[i] - '0');
                    i++;
                }
                nums.push(num);
                i--; 
            } else if (c == '(') {
                ops.push(c);
            } else if (c == ')') {
                while (!ops.empty() && ops.top() != '(') {
                    calculate();
                }
                if (!ops.empty()) ops.pop(); 
            } else { // Operator
                while (!ops.empty() && ops.top() != '(' && precedence[ops.top()] >= precedence[c]) {
                    calculate();
                }
                ops.push(c);
            }
        }

        while (!ops.empty()) {
            calculate();
        }

        return nums.top();
    }
};

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve(String s) {
        Deque<Long> nums = new ArrayDeque<>();
        Deque<Character> ops = new ArrayDeque<>();
        Map<Character, Integer> precedence = new HashMap<>();
        precedence.put('+', 1);
        precedence.put('-', 1);
        precedence.put('*', 2);

        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                long num = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + (s.charAt(i) - '0');
                    i++;
                }
                nums.push(num);
                i--;
            } else if (c == '(') {
                ops.push(c);
            } else if (c == ')') {
                while (!ops.isEmpty() && ops.peek() != '(') {
                    calculate(nums, ops);
                }
                if (!ops.isEmpty()) ops.pop();
            } else { // Operator
                while (!ops.isEmpty() && ops.peek() != '(' && precedence.get(ops.peek()) >= precedence.get(c)) {
                    calculate(nums, ops);
                }
                ops.push(c);
            }
        }
        
        while (!ops.isEmpty()) {
            calculate(nums, ops);
        }

        return nums.peek().intValue();
    }

    private void calculate(Deque<Long> nums, Deque<Character> ops) {
        long num2 = nums.pop();
        long num1 = nums.pop();
        char op = ops.pop();
        if (op == '+') nums.push(num1 + num2);
        else if (op == '-') nums.push(num1 - num2);
        else if (op == '*') nums.push(num1 * num2);
    }
}

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回表达式的值
# @param s string字符串 待计算的表达式
# @return int整型
#
class Solution:
    def solve(self , s: str) -> int:
        nums = []
        ops = []
        precedence = {'+': 1, '-': 1, '*': 2}

        def calculate():
            op = ops.pop()
            num2 = nums.pop()
            num1 = nums.pop()
            if op == '+': nums.append(num1 + num2)
            elif op == '-': nums.append(num1 - num2)
            elif op == '*': nums.append(num1 * num2)
        
        i = 0
        while i < len(s):
            c = s[i]
            if c.isdigit():
                num = 0
                while i < len(s) and s[i].isdigit():
                    num = num * 10 + int(s[i])
                    i += 1
                nums.append(num)
                i -= 1
            elif c == '(':
                ops.append(c)
            elif c == ')':
                while ops and ops[-1] != '(':
                    calculate()
                if ops: ops.pop()
            else:
                while ops and ops[-1] != '(' and precedence.get(ops[-1], 0) >= precedence.get(c, 0):
                    calculate()
                ops.append(c)
            i += 1
            
        while ops:
            calculate()
            
        return nums[0] if nums else 0

算法及复杂度

算法: 双栈表达式求值。
时间复杂度: $\mathcal{O}(L)$ ，其中 L 是输入字符串的长度。每个数字和操作符都只会被压入和弹出栈一次，所以总操作次数与字符串长度呈线性关系。
空间复杂度: $\mathcal{O}(L)$ 。在最坏的情况下（例如 ((...((1+1))...)) 或 1+2+3+...+N），栈的深度可能与字符串长度成正比。