基本计算器

难度:

标签:

题目描述

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

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

示例 1：

输入：s = "1 + 1"
输出：2

示例 2：

输入：s = " 2-1 + 2 "
输出：3

示例 3：

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

提示：

1 <= s.length <= 3 * 10⁵
s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
s 表示一个有效的表达式
'+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)
'-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)
输入中不存在两个连续的操作符
每个数字和运行的计算将适合于一个有符号的 32位整数

代码结果

运行时间: 32 ms, 内存: 17.3 MB

// Java Stream-like solution (though Streams are not ideal for this task, as it involves state changes and conditional operations)
// Idea: Use Java's streams to simulate the main logic, but actual calculation is done imperatively.
public class BasicCalculatorStream {
    public int calculate(String s) {
        return java.util.stream.IntStream.range(0, s.length())
            .mapToObj(i -> s.charAt(i))
            .reduce(new Object() {
                int result = 0;
                int sign = 1;
                Stack<Integer> stack = new Stack<>();
                int num = 0;
                boolean inNumber = false;
            }, (acc, c) -> {
                if (Character.isDigit(c)) {
                    acc.num = acc.num * 10 + (c - '0');
                    acc.inNumber = true;
                } else {
                    if (acc.inNumber) {
                        acc.result += acc.sign * acc.num;
                        acc.num = 0;
                        acc.inNumber = false;
                    }
                    if (c == '+') {
                        acc.sign = 1;
                    } else if (c == '-') {
                        acc.sign = -1;
                    } else if (c == '(') {
                        acc.stack.push(acc.result);
                        acc.stack.push(acc.sign);
                        acc.result = 0;
                        acc.sign = 1;
                    } else if (c == ')') {
                        acc.result = acc.result * acc.stack.pop() + acc.stack.pop();
                    }
                }
                return acc;
            }, (acc1, acc2) -> acc1).result;
    }
}

解释

方法:

该题解使用了一个栈来处理带括号的表达式。首先，通过一个循环遍历整个字符串，使用变量curNum来维护当前的数字，使用curOp来表示当前的操作符（加号为1，减号为-1）。当遇到'('时，将当前的curNum和curOp存入栈中，并重置curNum和curOp，这样可以处理新的子表达式。当遇到')'时，将栈顶的元素（之前的curNum和curOp）取出，根据这些值计算括号内表达式的值。对于数字的处理，使用while循环连续读取字符直到非数字，计算出完整的数字并根据之前的curOp更新curNum。最终，在字符串遍历完成后，curNum将包含整个表达式的计算结果。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

在处理数字时，你是如何确保连续数字字符串被正确转换为整数的？

▷

在题解中，为了正确处理和转换连续的数字字符为整数，使用了一个内部的循环。当遇到一个数字字符时，初始化一个变量 `k` 为 0，然后进入一个内部循环，这个循环会持续读取字符串中的连续数字字符。在每次循环中，将 `k` 的值乘以 10（这是因为我们正在处理十进制数，并且每向前一位，数值的大小就放大10倍），然后将当前字符表示的整数加到 `k` 上。这样，通过连续读取和更新 `k` 的值，就能将一串连续的数字字符正确地转换为整数。

🦆

在题解中，当遇到'('时你将curNum和curOp压入栈，为何选择在这一点重置curNum和curOp？

▷

在遇到左括号 '(' 时，意味着将要开始一个新的子表达式的计算。此时将当前的 `curNum`（当前已经计算的结果）和 `curOp`（最近的操作符）压入栈，是为了保存当前表达式的上下文状态，以便在后续遇到对应的右括号 ')' 时能恢复这个状态继续之前的计算。重置 `curNum` 和 `curOp` 则是因为括号内的表达式应当独立计算，它们的计算结果最终会根据之前保存的状态（操作符和数值）与外部表达式合并。因此，重置这两个变量可以确保不会将外部的计算结果错误地混入新的子表达式中。

🦆

题解中提到，遇到')'将栈顶的元素取出并计算括号内表达式的值，能否详细说明这一计算过程是如何进行的？

▷

当遇到右括号 ')' 时，首先从栈中弹出之前压入的元素，这些元素包括上一个未完的表达式的累计结果 `prevNum` 和与之对应的操作符 `prevOp`。这时，栈顶的 `prevNum` 表示在当前括号表达式之前已经计算的结果，而 `prevOp` 表示这个括号表达式外的操作符，即这个括号表达式应该如何影响整体计算结果（是加上还是减去括号内的结果）。括号内的表达式的计算结果已经在 `curNum` 中。因此，通过执行 `prevNum + prevOp * curNum` 计算，可以将括号内的结果合并到总表达式的计算中。这样，括号表达式的计算结果被正确地加入到了整体的计算流程中。

相关问题

逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

有效的算符为 '+'、'-'、'*' 和 '/' 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

提示：

1 <= tokens.length <= 10⁴
tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中