LeetCode 题解 | 224.基本计算器 基本算法是什么

力扣 224.基本计算器 （点击查看题目）

题目描述

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负 整数和空格 。

示例 1:

输入: "1 + 1"
输出: 2

示例 2:

输入: " 2-1 + 2 "
输出: 3

示例 3:

输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23

说明：

• 你可以假设所给定的表达式都是有效的。
• 请不要使用内置的库函数 eval。

解决方案

概述

解决这个问题需要理解以下内容：

• 输入始终包含有效的字符串。
• 加减法规则。
• 括号中的优先含义。
• 空格不影响输入表达式的计算。

方法一：栈和反转字符串

这个问题适合用栈来解决，因为表达式中包含括号，我们可以使用栈来查找每个子表达式的值。本质上，我们需要延迟处理主表达式，直到完成对括号种的中间子表达式的求值，我们使用栈来解决它。

我们将表达式的元素一个接一个的添加到栈上，直到我们遇到一个右括号 )。然后逐个弹出栈中的元素，在运行时对子表达式进行求值，直到遇到左括号 ( 为止。

我们需要理解 + 和 - 的区别。+ 遵循结合律。例如 A + B + C，等价于（A + B ）+ C = A +（B + C）。然后 - 不遵循这个一规则，这是该方法中所有问题的根本原因。

如果我们使用栈并从左到右读取表达式的元素，则最终我们会从右到左计算表达式。就会出现 （A -B）- C 等于（C - B）- A 的情况，这是不正确的。减法即不遵循结合律也不遵循交换律。

这个问题很容易解决，我们通过反转字符串，然后再按需添加到栈中，我们将字符串从右到左放入栈中，并从左到右正确的计算表达式。

算法：

1. 按逆序迭代字符串。
2. 操作数可以由多个字符组成，字符串 "123" 表示数字 123，它可以被构造为：123 >> 120 + 3 >> 100 + 20 + 3。如果我们读取的字符是一个数字，则我们要将读取的数字乘以 10 的幂并将当前数字相加，形成操作数。因为我们是按逆序处理字符串。
3. 操作数由多个字符组成，一旦我们遇到的字符不是数字，则我们将操作数添加到栈上。
4. 当我们遇到最括号 (，这意味这遇到了一个子表达式结束。由于我们是逆序，所以开括号成了表达式的结尾。则需要从栈中弹出操作数和运算发来计算表达式，直到弹出相应的右括号。子表达式的最终结果最终添加到栈上。
5. 将非数字字符添加到栈上。
6. 这个做直到我们得到最终的结果。可能我们没有更多的字符要处理，但是栈仍然是非空的。当主表达式没有用括号括起来时，就会发生这种情况。因此，在完成对整个表达式求值之后，我们将检查栈是否非空。如果是的话，我们将栈中的元素作为最终表达式处理，并像遇到左括号时那样对其求值。我们还可以用一组括号覆盖原表达式，以此避免额外调用。

Python 实现（电脑端查看代码）

class Solution:

    def evaluate_expr(self, stack):
        res = stack.pop() if stack else 0

        # Evaluate the expression till we get corresponding ')'
        while stack and stack[-1] != ')':
            sign = stack.pop()
            if sign == '+':
                res += stack.pop()
            else:
                res -= stack.pop()
        return res

    def calculate(self, s: str) -> int:

        stack = []
        n, operand = 0, 0

        for i in range(len(s) - 1, -1, -1):
            ch = s[i]

            if ch.isdigit():

                # Forming the operand - in reverse order.
                operand = (10**n * int(ch)) + operand
                n += 1

            elif ch != " ":
                if n:
                    # Save the operand on the stack
                    # As we encounter some non-digit.
                    stack.append(operand)
                    n, operand = 0, 0

                if ch == '(':         
                    res = self.evaluate_expr(stack)
                    stack.pop()

                    # Append the evaluated result to the stack.
                    # This result could be of a sub-expression within the parenthesis.
                    stack.append(res)

                # For other non-digits just push onto the stack.
                else:
                    stack.append(ch)

        # Push the last operand to stack, if any.
        if n:
            stack.append(operand)

        # Evaluate any left overs in the stack.
        return self.evaluate_expr(stack)

Java 实现（电脑端查看代码）

class Solution {

    public int evaluateExpr(Stack<Object> stack) {

        int res = 0;

        if (!stack.empty()) {
            res = (int) stack.pop();
        }

        // Evaluate the expression till we get corresponding ')'
        while (!stack.empty() && !((char) stack.peek() == ')')) {

            char sign = (char) stack.pop();

            if (sign == '+') {
                res += (int) stack.pop();
            } else {
                res -= (int) stack.pop();
            }
        }
        return res;
    }

    public int calculate(String s) {

        int operand = 0;
        int n = 0;
        Stack<Object> stack = new Stack<Object>();

        for (int i = s.length() - 1; i >= 0; i--) {

            char ch = s.charAt(i);

            if (Character.isDigit(ch)) {

                // Forming the operand - in reverse order.
                operand = (int) Math.pow(10, n) * (int) (ch - '0') + operand;
                n += 1;

            } else if (ch != ' ') {
                if (n != 0) {

                    // Save the operand on the stack
                    // As we encounter some non-digit.
                    stack.push(operand);
                    n = 0;
                    operand = 0;

                }
                if (ch == '(') {

                    int res = evaluateExpr(stack);
                    stack.pop();

                    // Append the evaluated result to the stack.
                    // This result could be of a sub-expression within the parenthesis.
                    stack.push(res);

                } else {
                    // For other non-digits just push onto the stack.
                    stack.push(ch);
                }
            }
        }

        //Push the last operand to stack, if any.
        if (n != 0) {
            stack.push(operand);
        }

        // Evaluate any left overs in the stack.
        return evaluateExpr(stack);
    }
}

复杂度分析

时间复杂度：O(N)，其中 N 指的是字符串的长度。

空间复杂度：O(N)，其中 N 指的是字符串的长度。

方法二：栈和不反转字符串

解决 - 结合律的问题的一个分厂简单的方法就是使将 - 运算符看作右侧操作数的大小。一旦我们将 - 看作操作数的大小，则表达式将只剩下一个操作符。就是 + 运算符，而 + 是遵循结合律的。

例如，A - B - C 等于 A +（-B）+（-C）。

重写以后的表达式将遵循结合律，所以我们从左或从右计算表达式都是正确的。

我们需要注意的是给定的表达式会很复杂，即会有嵌套在其他表达式的表达式。即 (A - (B - C)，我们需要 B-C 外面的 - 号与 B-C 关联起来，而不是仅仅与 B 关联起来。

/ 我们可以通过遵循前面的基本练习并将符号与其右侧的表达式关联来解决此问题。然而，我们将采用的方法有一个小的转折，因为我们将在运行中评估大多数表达式。这减少了推送和弹出操作的数量。

算法：

1. 正序迭代字符串。
2. 操作数可以由多个字符组成，字符串 "123" 表示数字 123，它可以被构造为：123 >> 120 + 3 >> 100 + 20 + 3。如果我们读取的字符是一个数字，则我们要将先前形成的操作数乘以 10 并于读取的数字相加，形成操作数。
3. 每当我们遇到 + 或 - 运算符时，我们首先将表达式求值到左边，然后将正负符号保存到下一次求值。
4. 如果字符是左括号 (，我们将迄今为止计算的结果和符号添加到栈上，然后重新开始进行计算，就像计算一个新的表达式一样。
5. 如果字符是右括号 )，则首先计算左侧的表达式。则产生的结果就是刚刚结束的子表达式的结果。如果栈顶部有符号，则将此结果与符号相乘。

Python 实现（电脑端查看代码）

class Solution:
    def calculate(self, s: str) -> int:

        stack = []
        operand = 0
        res = 0 # For the on-going result
        sign = 1 # 1 means positive, -1 means negative  

        for ch in s:
            if ch.isdigit():

                # Forming operand, since it could be more than one digit
                operand = (operand * 10) + int(ch)

            elif ch == '+':

                # Evaluate the expression to the left,
                # with result, sign, operand
                res += sign * operand

                # Save the recently encountered '+' sign
                sign = 1

                # Reset operand
                operand = 0

            elif ch == '-':

                res += sign * operand
                sign = -1
                operand = 0

            elif ch == '(':

                # Push the result and sign on to the stack, for later
                # We push the result first, then sign
                stack.append(res)
                stack.append(sign)

                # Reset operand and result, as if new evaluation begins for the new sub-expression
                sign = 1
                res = 0

            elif ch == ')':

                # Evaluate the expression to the left
                # with result, sign and operand
                res += sign * operand

                # ')' marks end of expression within a set of parenthesis
                # Its result is multiplied with sign on top of stack
                # as stack.pop() is the sign before the parenthesis
                res *= stack.pop() # stack pop 1, sign

                # Then add to the next operand on the top.
                # as stack.pop() is the result calculated before this parenthesis
                # (operand on stack) + (sign on stack * (result from parenthesis))
                res += stack.pop() # stack pop 2, operand

                # Reset the operand
                operand = 0

        return res + sign * operand

Java 实现（电脑端查看代码）

class Solution {
    public int calculate(String s) {

        Stack<Integer> stack = new Stack<Integer>();
        int operand = 0;
        int result = 0; // For the on-going result
        int sign = 1;  // 1 means positive, -1 means negative

        for (int i = 0; i < s.length(); i++) {

            char ch = s.charAt(i);
            if (Character.isDigit(ch)) {

                // Forming operand, since it could be more than one digit
                operand = 10 * operand + (int) (ch - '0');

            } else if (ch == '+') {

                // Evaluate the expression to the left,
                // with result, sign, operand
                result += sign * operand;

                // Save the recently encountered '+' sign
                sign = 1;

                // Reset operand
                operand = 0;

            } else if (ch == '-') {

                result += sign * operand;
                sign = -1;
                operand = 0;

            } else if (ch == '(') {

                // Push the result and sign on to the stack, for later
                // We push the result first, then sign
                stack.push(result);
                stack.push(sign);

                // Reset operand and result, as if new evaluation begins for the new sub-expression
                sign = 1;
                result = 0;

            } else if (ch == ')') {

                // Evaluate the expression to the left
                // with result, sign and operand
                result += sign * operand;

                // ')' marks end of expression within a set of parenthesis
                // Its result is multiplied with sign on top of stack
                // as stack.pop() is the sign before the parenthesis
                result *= stack.pop();

                // Then add to the next operand on the top.
                // as stack.pop() is the result calculated before this parenthesis
                // (operand on stack) + (sign on stack * (result from parenthesis))
                result += stack.pop();

                // Reset the operand
                operand = 0;
            }
        }
        return result + (sign * operand);
    }
}

复杂度分析

时间复杂度：O(N)，其中 N 指的是字符串的长度。这种方法与前一种方法的区别在于，这种方法的每个字符都将被精确的处理一次。但是前面的方法中，每个字符可能被处理两次，一次是被添加到栈上，另一次是被弹出处理最终结果。这就是为什么这种方法更快的原因。

空间复杂度：O(N)，其中 N 指的是字符串的长度。

本文作者：力扣

声明：本文归“力扣”版权所有，如需转载请联系。