题解 | 表达式求值

1、解题思路

1. 栈的应用： 使用两个栈：nums 栈存储数字，ops 栈存储运算符和括号。遵循以下规则： 遇到数字时，提取完整的数字并压入 nums 栈。遇到左括号时，压入 ops 栈。遇到右括号时，弹出 ops 栈直到遇到左括号，计算括号内的表达式。遇到运算符时，根据优先级决定是否先计算栈中的部分表达式。
2. 运算符优先级： 乘法优先级高于加减法。遇到高优先级的运算符时，先计算栈中的部分表达式。
3. 计算顺序： 从左到右依次处理字符。遇到高优先级运算符时，先计算高优先级的部分。

2、代码实现

C++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int solve(string s) {
        // write code here
        stack<int> nums;
        stack<char> ops;
        int n = s.size();

        for (int i = 0; i < n; ++i) {
            char c = s[i];
            if (isdigit(c)) {
                int num = 0;
                while (i < n && isdigit(s[i])) {
                    num = num * 10 + (s[i] - '0');
                    ++i;
                }
                --i;
                nums.push(num);
            } else if (c == '(') {
                ops.push(c);
            } else if (c == ')') {
                while (ops.top() != '(') {
                    calculate(nums, ops);
                }
                ops.pop();  // 弹出 '('
            } else {
                // 处理运算符
                while (!ops.empty() && ops.top() != '(' && precedence(ops.top()) >= precedence(c)) {
                    calculate(nums, ops);
                }
                ops.push(c);
            }
        }
        while (!ops.empty()) {
            calculate(nums, ops);
        }
        return nums.top();
    }

    int precedence(char op) {
        if (op == '+' || op == '-') {
            return 1;
        }
        if (op == '*' || op == '/') {
            return 2;
        }
        return 0;
    }

    void calculate(stack<int>& nums, stack<char>& ops) {
        int b = nums.top();
        nums.pop();
        int a = nums.top();
        nums.pop();
        char op = ops.top();
        ops.pop();

        if (op == '+') {
            nums.push(a + b);
        } else if (op == '-') {
            nums.push(a - b);
        } else if (op == '*') {
            nums.push(a * b);
        }
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve (String s) {
        // write code here
        Stack<Integer> nums = new Stack<>();
        Stack<Character> ops = new Stack<>();
        int n = s.length();

        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int num = 0;
                while (i < n && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + (s.charAt(i) - '0');
                    i++;
                }
                i--;
                nums.push(num);
            } else if (c == '(') {
                ops.push(c);
            } else if (c == ')') {
                while (ops.peek() != '(') {
                    calculate(nums, ops);
                }
                ops.pop();  // 弹出 '('
            } else {
                // 处理运算符
                while (!ops.empty() && ops.peek() != '(' &&
                        precedence(ops.peek()) >= precedence(c)) {
                    calculate(nums, ops);
                }
                ops.push(c);
            }
        }
        while (!ops.empty()) {
            calculate(nums, ops);
        }
        return nums.pop();
    }

    private int precedence(char op) {
        if (op == '+' || op == '-') {
            return 1;
        }
        if (op == '*' || op == '/') {
            return 2;
        }
        return 0;
    }

    private void calculate(Stack<Integer> nums, Stack<Character> ops) {
        int b = nums.pop();
        int a = nums.pop();
        char op = ops.pop();

        if (op == '+') {
            nums.push(a + b);
        } else if (op == '-') {
            nums.push(a - b);
        } else if (op == '*') {
            nums.push(a * b);
        }
    }
}

Python

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

        while i < n:
            c = s[i]
            if c.isdigit():
                num = 0
                while i < n and s[i].isdigit():
                    num = num * 10 + int(s[i])
                    i += 1
                i -= 1
                nums.append(num)
            elif c == '(':
                ops.append(c)
            elif c == ')':
                while ops[-1] != '(':
                    self.calculate(nums, ops)
                ops.pop()  # 弹出 '('
            else:
                # 处理运算符
                while ops and ops[-1] != '(' and self.precedence(ops[-1]) >= self.precedence(c):
                    self.calculate(nums, ops)
                ops.append(c)
            i += 1

        while ops:
            self.calculate(nums, ops)
        return nums[-1]

    def precedence(self, op):
        if op in '+-':
            return 1
        if op in '*/':
            return 2
        return 0

    def calculate(self, nums, ops):
        b = nums.pop()
        a = nums.pop()
        op = ops.pop()

        if op == '+':
            nums.append(a + b)
        elif op == '-':
            nums.append(a - b)
        elif op == '*':
            nums.append(a * b)

3、复杂度分析

• 每个字符处理一次，时间复杂度为 O(n)。
• 空间复杂度为 O(n)，因为使用栈存储中间结果。