基本计算器 II

难度:

标签:

题目描述

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-2³¹, 2³¹ - 1] 的范围内。

注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

输入：s = "3+2*2"
输出：7

示例 2：

输入：s = " 3/2 "
输出：1

示例 3：

输入：s = " 3+5 / 2 "
输出：5

提示：

1 <= s.length <= 3 * 10⁵
s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
s 表示一个 有效表达式
表达式中的所有整数都是非负整数，且在范围 [0, 2³¹ - 1] 内
题目数据保证答案是一个 32-bit 整数

代码结果

运行时间: 68 ms, 内存: 0.0 MB

/*
 * 题目思路：
 * 1. 使用一个栈来存储每个操作数，根据当前的运算符来决定如何处理栈顶元素。
 * 2. 使用Java Stream进行最终的栈元素求和。
 */
 
import java.util.Stack;
 
public class BasicCalculator {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        int num = 0;
        char sign = '+';
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            }
            if (!Character.isDigit(c) && c != ' ' || i == s.length() - 1) {
                if (sign == '+') {
                    stack.push(num);
                } else if (sign == '-') {
                    stack.push(-num);
                } else if (sign == '*') {
                    stack.push(stack.pop() * num);
                } else if (sign == '/') {
                    stack.push(stack.pop() / num);
                }
                sign = c;
                num = 0;
            }
        }
        return stack.stream().mapToInt(Integer::intValue).sum();
    }
}

解释

方法:

这个题解使用了一个栈来模拟计算过程。遍历字符串 s 中的每个字符，如果当前字符是数字，则更新当前数 cur；如果当前字符是运算符，则根据上一个运算符 op 来决定如何处理当前数，并更新上一个运算符为当前运算符。具体来说： 1. 如果上一个运算符是加号，则将当前数压入栈； 2. 如果上一个运算符是减号，则将当前数的相反数压入栈； 3. 如果上一个运算符是乘号，则将栈顶元素弹出，与当前数相乘后压入栈； 4. 如果上一个运算符是除号，则将栈顶元素弹出，与当前数相除后压入栈，注意处理除数为负数的情况。最后将栈中所有元素求和即为最终结果。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

为什么在处理每个数字后，需要加一个额外的'+'到字符串末尾来确保最后一个数字被正确处理？

▷

在此算法中，处理运算符和数字的逻辑是在遇到一个新的运算符时才回顾并处理之前的数字和运算符。这意味着字符串末尾的数字和运算符不会被处理，除非有一个新的运算符触发这一处理逻辑。通过在字符串末尾添加一个'+'，算法可以确保最后一个数字也被正确地按之前的运算符处理，而'+'本身不会改变现有结果的总和，因为它只是将最后一个数字正常加入到结果中。

🦆

在处理除法时，为什么选择用0减去正数除法的结果来处理负数情况，这种做法是否有可能导致结果错误？

▷

在处理除法时，特别是涉及负数的除法，需要确保结果的符号正确。在Python中，整数除法（//）的结果总是向下取整，即向负无穷方向取整。当被除数是负数的时候，使用0减去正数除法的结果是为了得到正确的商值。例如，`-3 // 2`结果为-2，而我们期望的商应该是更贴近0的-1，所以使用`0 - (abs(-3) // 2)`即`0 - 1 = -1`可得到预期结果。这种做法不会导致结果错误，而是一种确保在负数除法情况下符号正确的技巧。

🦆

在遇到乘号或除号时直接修改栈顶元素而不是先出栈再压入的做法，这种处理有什么优点或潜在的风险？

▷

直接修改栈顶元素而不是先出栈再压入可以减少操作的复杂性和提高一定的效率，因为这避免了不必要的出栈和入栈操作。然而，这种做法的潜在风险在于它修改了栈中的现有元素，这在多线程环境下或在其他需要跟踪元素历史的场景中可能会引发问题。在当前的单线程和简单计算场景中，这种方法是安全且有效的。

🦆

在这种解法中，如果输入字符串包含错误或非法字符（如字母或特殊字符），算法将如何响应？

▷

这种解法假设输入字符串只包含数字和合法的运算符（`+`, `-`, `*`, `/`），因此它没有处理非法字符的特定逻辑。如果输入包含字母或特殊字符，算法可能会表现出不可预测的行为或抛出错误。在实际应用中，应该在处理输入之前验证并清理数据，确保只包含预期的字符，从而避免运行时错误。

相关问题