Basic Calculator (I, II, III, IV)
|Last edited: 2024-5-12
ID
224
Data Type
Stack
Difficulty
Hard
Tags
Recursion
URL
https://leetcode.com/problems/basic-calculator/description/
Completed Date
May 12, 2024
Preference
🤔 Thought-provoking
II : Basic Calculator II - LeetCode
 
Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
Example 1:
Example 2:
Example 3:
Constraints:
  • 1 <= s.length <= 3 * 105
  • s consists of digits, '+', '-', '(', ')', and ' '.
  • s represents a valid expression.
  • '+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).
  • '-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
  • There will be no two consecutive operators in the input.
  • Every number and running calculation will fit in a signed 32-bit integer.
 

题解

💡
最关键的一点就是以后string数字不用用倒算乘10，直接用 res = res * 10 + num 就行了

最优代码

主要思路是：
  1. 使用一个栈来保存遇到的"("之前的结果和符号。
  1. 使用result变量来保存当前的计算结果，num变量来保存当前正在处理的数字，sign变量来保存当前的符号（1表示加号，-1表示减号）。
  1. 当遇到一个数字时，将其加到num上（乘以10是因为可能遇到多位数）。
  1. 当遇到加号或减号时，将之前的数字（num）乘以符号（sign）加到结果（result）上，然后重置num为0，更新sign为对应的符号。
  1. 当遇到"("时，将当前的结果（result）和符号（sign）推入栈中，然后重置result为0，sign为1。
  1. 当遇到")"时，先将之前的数字（num）乘以符号（sign）加到结果（result）上，然后重置num为0。然后将结果（result）乘以栈顶的符号，加上栈顶的结果，然后弹出栈顶的两个元素。
  1. 在遍历完字符串后，如果num不为0，说明还有一个没有处理的数字，将其乘以sign加到结果（result）上。
这个函数的时间复杂度为O(n)，其中n是字符串的长度。空间复杂度为O(m)，其中m是字符串中"("的数量。
 
让我们使用这个例子 "(1+(4+5+2)-3)+(6+8)" 来模拟函数的运行过程：
  1. 初始化：stack = []，result = 0，num = 0，sign = 1。
  1. 遇到左括号，不做任何操作。
  1. 遇到数字1，num = 1。
  1. 遇到加号，result = result + sign * num = 0 + 1 * 1 = 1，然后num = 0，sign = 1。
  1. 遇到左括号，将result和sign推入栈中，然后result = 0，sign = 1，所以stack = [1, 1]。
  1. 遇到数字4，num = 4。
  1. 遇到加号，result = result + sign * num = 0 + 1 * 4 = 4，然后num = 0，sign = 1。
  1. 遇到数字5，num = 5。
  1. 遇到加号，result = result + sign * num = 4 + 1 * 5 = 9，然后num = 0，sign = 1。
  1. 遇到数字2，num = 2。
  1. 遇到右括号，result = result + sign * num = 9 + 1 * 2 = 11，然后num = 0。然后将result乘以栈顶的符号，加上栈顶的结果，然后弹出栈顶的两个元素，所以result = 11 * 1 + 1 = 12，stack = []。
  1. 遇到减号，num = 0，sign = -1。
  1. 遇到数字3，num = 3。
  1. 遇到右括号，result = result + sign * num = 12 - 1 * 3 = 9，然后num = 0，sign = 1。
  1. 遇到加号，num = 0，sign = 1。
  1. 遇到数字6，num = 6。
  1. 遇到加号，result = result + sign * num = 9 + 1 * 6 = 15，然后num = 0，sign = 1。
  1. 遇到数字8，num = 8。
  1. 遍历完字符串，result = result + sign * num = 15 + 1 * 8 = 23。
所以，这个函数计算 "(1+(4+5+2)-3)+(6+8)" 的结果是 23，这是正确的。

递归

我写的垃圾代码

倒序法