基本计算器 III

难度:

标签:

题目描述

代码结果

运行时间: 26 ms, 内存: 16.0 MB

/*
 * 基本计算器 III
 * 题目思路:
 * 1. 使用Java Stream API进行字符串处理。
 * 2. 将字符串转换为字符流, 然后进行过滤和映射操作。
 * 3. 利用栈数据结构来处理括号和运算符的优先级。
 */

import java.util.*;
import java.util.stream.*;

public class BasicCalculatorIIIStream {
    public int calculate(String s) {
        Stack<Integer> nums = new Stack<>();
        Stack<Character> ops = new Stack<>();
        Stream<Character> stream = s.chars().mapToObj(c -> (char) c);
        List<Character> list = stream.collect(Collectors.toList());
        for (int i = 0; i < list.size(); i++) {
            char c = list.get(i);
            if (Character.isDigit(c)) {
                int num = 0;
                while (i < list.size() && Character.isDigit(list.get(i))) {
                    num = num * 10 + (list.get(i) - '0');
                    i++;
                }
                i--;
                nums.push(num);
            } else if (c == '(') {
                ops.push(c);
            } else if (c == ')') {
                while (ops.peek() != '(') {
                    nums.push(applyOp(ops.pop(), nums.pop(), nums.pop()));
                }
                ops.pop();
            } else if (c == '+' || c == '-' || c == '*' || c == '/') {
                while (!ops.isEmpty() && precedence(c) <= precedence(ops.peek())) {
                    nums.push(applyOp(ops.pop(), nums.pop(), nums.pop()));
                }
                ops.push(c);
            }
        }
        while (!ops.isEmpty()) {
            nums.push(applyOp(ops.pop(), nums.pop(), nums.pop()));
        }
        return nums.pop();
    }

    private int applyOp(char op, int b, int a) {
        switch (op) {
            case '+': return a + b;
            case '-': return a - b;
            case '*': return a * b;
            case '/': return a / b;
        }
        return 0;
    }

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

解释

方法:

该题解使用栈来模拟计算过程。从左到右遍历字符串，遇到数字时更新当前数字，遇到左括号时将当前的运算符入栈并重置当前数字和运算符，遇到运算符时根据之前的运算符进行相应的计算并更新当前运算符，遇到右括号时计算括号内的结果并将结果作为数字进行进一步计算。最后将栈中所有数字求和得到最终结果。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

在算法中，遇到左括号`(`时，为什么要将当前运算符入栈并重置数字和运算符？这样做的目的是什么？

▷

在算法中，遇到左括号`(`时将当前运算符入栈并重置数字和运算符的目的是为了处理嵌套的表达式。当解析器遇到左括号时，意味着将开始一个新的表达式的解析，这个新的表达式在逻辑上是独立的，并且其结果将作为整个包含它的更大表达式的一部分。通过入栈当前运算符，我们可以在遇到对应的右括号时，恢复之前的计算环境，确保括号内的表达式计算完成后能够正确地与外部表达式整合。

🦆

在处理完括号内的表达式后，为什么需要将括号前的运算符从栈中弹出，并用这个运算符继续计算？

▷

处理完括号内的表达式后，需要将括号前的运算符从栈中弹出并用这个运算符继续计算，因为这个运算符表示了括号表达式与其前一个数字或表达式之间的关系。括号内的表达式被视为一个整体（一个数值），一旦计算得到这个值，就需要使用它与之前的值根据保存的运算符进行合并计算。这样做可以确保表达式的运算顺序和数学逻辑的正确性。

🦆

在实现除法时，为什么采用`int(stack.pop() / num)`而不是直接`stack.pop() / num`？这样处理的原因是什么？

▷

在实现除法时，使用`int(stack.pop() / num)`而不是直接`stack.pop() / num`是为了确保结果是整数。在许多编程语言中，整数除法的结果需要是整数类型。由于题目或环境可能要求或假定整数运算，使用`int()`可以确保不论输入的正负，结果都符合整数的预期（例如，Python中的整数除法会向下取整）。这样处理可以防止结果中出现浮点数，从而满足特定的题目要求或实现细节。

🦆

该题解在处理运算符时，有考虑运算符的优先级吗？如果有，是如何实现的？如果没有，这样做会有什么潜在问题？

▷

该题解在处理运算符时有部分考虑运算符的优先级，主要通过立即计算乘法和除法来实现，而加法和减法则通过将数字推入栈中延后处理。这种实现方式在处理没有括号的基本表达式时能够正确处理运算符优先级。然而，这种方法可能在更复杂的情况下遇到问题，尤其是当多个不同优先级的运算符在没有明确括号的情况下连续出现时，这种实现可能会导致运算顺序错误，从而影响最终结果的正确性。

相关问题

基本计算器

给你一个字符串表达式 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位整数

基本计算器 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 整数

基本计算器 IV

给定一个表达式如 expression = "e + 8 - a + 5" 和一个求值映射，如 {"e": 1}（给定的形式为 evalvars = ["e"] 和 evalints = [1]），返回表示简化表达式的标记列表，例如 ["-1*a","14"]

表达式交替使用块和符号，每个块和符号之间有一个空格。
块要么是括号中的表达式，要么是变量，要么是非负整数。
变量是一个由小写字母组成的字符串（不包括数字）。请注意，变量可以是多个字母，并注意变量从不具有像 "2x" 或 "-x" 这样的前导系数或一元运算符。

表达式按通常顺序进行求值：先是括号，然后求乘法，再计算加法和减法。

例如，expression = "1 + 2 * 3" 的答案是 ["7"]。

输出格式如下：

对于系数非零的每个自变量项，我们按字典排序的顺序将自变量写在一个项中。
- 例如，我们永远不会写像 “b*a*c” 这样的项，只写 “a*b*c”。
项的次数等于被乘的自变量的数目，并计算重复项。我们先写出答案的最大次数项，用字典顺序打破关系，此时忽略词的前导系数。
- 例如，"a*a*b*c" 的次数为 4。
项的前导系数直接放在左边，用星号将它与变量分隔开(如果存在的话)。前导系数 1 仍然要打印出来。
格式良好的一个示例答案是 ["-2*a*a*a", "3*a*a*b", "3*b*b", "4*a", "5*c", "-6"] 。
系数为 0 的项（包括常数项）不包括在内。
- 例如，“0” 的表达式输出为 [] 。

注意：你可以假设给定的表达式均有效。所有中间结果都在区间 [-2³¹, 2³¹ - 1] 内。

示例 1：

输入：expression = "e + 8 - a + 5", evalvars = ["e"], evalints = [1]
输出：["-1*a","14"]

示例 2：

输入：expression = "e - 8 + temperature - pressure",
evalvars = ["e", "temperature"], evalints = [1, 12]
输出：["-1*pressure","5"]

示例 3：

输入：expression = "(e + 8) * (e - 8)", evalvars = [], evalints = []
输出：["1*e*e","-64"]

提示：

1 <= expression.length <= 250
expression 由小写英文字母，数字 '+', '-', '*', '(', ')', ' ' 组成
expression 不包含任何前空格或后空格
expression 中的所有符号都用一个空格隔开
0 <= evalvars.length <= 100
1 <= evalvars[i].length <= 20
evalvars[i] 由小写英文字母组成
evalints.length == evalvars.length
-100 <= evalints[i] <= 100

二叉搜索树中的插入操作搜索长度未知的有序数组