LeetCode题练习与总结：基本计算器 Ⅱ--227

一、题目描述

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

二、解题思路

这个问题可以使用栈（stack）来解决。我们使用两个栈，一个用于存储操作数，另一个用于存储操作符。遍历字符串s，根据遇到的字符类型（数字、操作符或空格）进行相应的处理。

当遇到数字时，将其转换为整数并存储在操作数栈中。
当遇到操作符时，需要考虑操作符的优先级。如果当前操作符的优先级高于栈顶操作符的优先级，则直接将当前操作符入栈。否则，需要先计算栈顶的操作符，并将结果重新入栈，然后比较当前操作符与新的栈顶操作符的优先级。
当遇到空格时，忽略它。
对于乘法和除法，因为它们的优先级高于加法和减法，所以一旦遇到乘号或除号，需要立即计算结果，并将结果入栈。
对于加法和减法，可以直接将操作数入栈，因为它们可以在最后一起计算。

以下是具体的步骤：

初始化两个栈：一个用于存储操作数（nums），另一个用于存储操作符（ops）。
遍历字符串s，对于每个字符c：
- 如果c是空格，则忽略。
- 如果c是数字，则解析出完整的数字并压入nums栈。
- 如果c是操作符（+、-、*、/）：
  - 如果ops栈为空或者栈顶的操作符是(，则直接将c压入ops栈。
  - 如果c是*或/，则从nums栈中弹出两个操作数进行计算，并将结果压回nums栈。
  - 如果c是+或-，并且ops栈顶不是(，则从nums栈中弹出两个操作数进行计算，并将结果压回nums栈，然后将c压入ops栈。
遍历完成后，如果ops栈中还有操作符，则继续从nums栈中弹出操作数进行计算，直到ops栈为空。
最后，nums栈中的唯一元素即为表达式的结果。

三、具体代码

import java.util.Stack;public class Solution {public int calculate(String s) {Stack<Integer> nums = new Stack<>();Stack<Character> ops = new Stack<>();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (c == ' ') continue;if (Character.isDigit(c)) {int num = 0;while (i < s.length() && Character.isDigit(s.charAt(i))) {num = num * 10 + (s.charAt(i) - '0');i++;}i--; // since the for loop also increments inums.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() && hasPrecedence(c, 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();}public boolean hasPrecedence(char op1, char op2) {if (op2 == '(' || op2 == ')') return false;if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-')) return false;return true;}public 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;}
}

请注意，代码中的applyOp方法假设栈中的操作数顺序是正确的，并且对于减法和除法，a和b的顺序很重要（a是被操作数，b是操作数）。代码也处理了括号的情况，确保在遇到右括号时，所有括号内的表达式都会被计算。

四、时间复杂度和空间复杂度

1. 时间复杂度

遍历字符串s：假设字符串s的长度为n，则遍历字符串的时间复杂度为O(n)。
解析数字：在遍历过程中，每次遇到数字，需要解析出完整的数字。在最坏的情况下，数字可能连续出现，这意味着对于每个数字字符，我们需要进行一次操作。因此，解析数字的总操作次数也是O(n)。
应用操作符：在遍历字符串的过程中，每次遇到操作符，我们可能需要从栈中弹出元素进行计算，然后将结果压回栈中。在最坏的情况下，可能需要对每个操作符都进行这样的操作。由于每个操作符最多被处理一次，因此这一步的时间复杂度也是O(n)。

综上所述，总的时间复杂度为O(n)，其中n是字符串s的长度。

2. 空间复杂度

操作数栈nums：在最坏的情况下，所有数字都直接入栈，没有进行任何计算，因此栈的大小可能达到O(n)。
操作符栈ops：在最坏的情况下，所有操作符都直接入栈，没有进行任何计算，因此栈的大小可能达到O(n)。

综上所述，总的空间复杂度为O(n)，其中n是字符串s的长度。

这里的O(n)表示算法的复杂度与输入字符串的长度成线性关系。在实际情况中，由于数字不会连续占据整个字符串，操作符栈和操作数栈的大小通常会小于n，但最坏情况下的复杂度分析仍然是O(n)。

五、总结知识点

栈（Stack）的使用：
- 栈是一种后进先出（Last In First Out, LIFO）的数据结构。
- 在Java中，Stack类是java.util包中的一个类，用于实现栈数据结构。
字符和字符串操作：
- 使用char类型来处理单个字符。
- 使用String类的charAt方法来获取字符串中指定位置的字符。
- 使用Character.isDigit方法来判断一个字符是否是数字。
数字解析：
- 通过循环和字符减去’0’的方式，将字符串中的连续数字字符转换为整数。
运算符优先级：
- 在处理算术表达式时，需要根据运算符的优先级来决定计算的顺序。
- 使用hasPrecedence方法来判断当前运算符与栈顶运算符的优先级关系。
条件逻辑：
- 使用if-else语句来处理不同类型的字符（空格、数字、运算符、括号）。
- 使用while循环来处理连续的数字字符，以及应用运算符。
异常处理：
- 虽然在给出的代码中没有显示异常处理，但在实际应用中，应当考虑除法操作可能导致的ArithmeticException（如除以零）。
递归下降：
- 在处理括号时，实际上隐式地使用了递归下降解析的原理，通过递归地将括号内的表达式视为一个子表达式来处理。
运算符应用：
- 使用applyOp方法来根据运算符执行相应的算术运算。
算法逻辑：
- 理解和实现一个基本的算术表达式求值算法，这涉及到算法设计的基本概念。
类型转换：
- 在将字符转换为整数时，涉及到从char到int的类型转换。