Basic Calculator (I, II, III, IV)
ID
224
Data Type
Stack
Difficulty
Hard
Tags
Recursion
Completed Date
May 12, 2024
Preference
🤔 Thought-provoking
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
就行了最优代码
主要思路是:
- 使用一个栈来保存遇到的"("之前的结果和符号。
- 使用
result
变量来保存当前的计算结果,num
变量来保存当前正在处理的数字,sign
变量来保存当前的符号(1表示加号,-1表示减号)。
- 当遇到一个数字时,将其加到
num
上(乘以10是因为可能遇到多位数)。
- 当遇到加号或减号时,将之前的数字(
num
)乘以符号(sign
)加到结果(result
)上,然后重置num
为0,更新sign
为对应的符号。
- 当遇到"("时,将当前的结果(
result
)和符号(sign
)推入栈中,然后重置result
为0,sign
为1。
- 当遇到")"时,先将之前的数字(
num
)乘以符号(sign
)加到结果(result
)上,然后重置num
为0。然后将结果(result
)乘以栈顶的符号,加上栈顶的结果,然后弹出栈顶的两个元素。
- 在遍历完字符串后,如果
num
不为0,说明还有一个没有处理的数字,将其乘以sign
加到结果(result
)上。
这个函数的时间复杂度为O(n),其中n是字符串的长度。空间复杂度为O(m),其中m是字符串中"("的数量。
让我们使用这个例子 "(1+(4+5+2)-3)+(6+8)" 来模拟函数的运行过程:
- 初始化:
stack = []
,result = 0
,num = 0
,sign = 1
。
- 遇到左括号,不做任何操作。
- 遇到数字1,
num = 1
。
- 遇到加号,
result = result + sign * num = 0 + 1 * 1 = 1
,然后num = 0
,sign = 1
。
- 遇到左括号,将
result
和sign
推入栈中,然后result = 0
,sign = 1
,所以stack = [1, 1]
。
- 遇到数字4,
num = 4
。
- 遇到加号,
result = result + sign * num = 0 + 1 * 4 = 4
,然后num = 0
,sign = 1
。
- 遇到数字5,
num = 5
。
- 遇到加号,
result = result + sign * num = 4 + 1 * 5 = 9
,然后num = 0
,sign = 1
。
- 遇到数字2,
num = 2
。
- 遇到右括号,
result = result + sign * num = 9 + 1 * 2 = 11
,然后num = 0
。然后将result
乘以栈顶的符号,加上栈顶的结果,然后弹出栈顶的两个元素,所以result = 11 * 1 + 1 = 12
,stack = []
。
- 遇到减号,
num = 0
,sign = -1
。
- 遇到数字3,
num = 3
。
- 遇到右括号,
result = result + sign * num = 12 - 1 * 3 = 9
,然后num = 0
,sign = 1
。
- 遇到加号,
num = 0
,sign = 1
。
- 遇到数字6,
num = 6
。
- 遇到加号,
result = result + sign * num = 9 + 1 * 6 = 15
,然后num = 0
,sign = 1
。
- 遇到数字8,
num = 8
。
- 遍历完字符串,
result = result + sign * num = 15 + 1 * 8 = 23
。
所以,这个函数计算 "(1+(4+5+2)-3)+(6+8)" 的结果是 23,这是正确的。
递归
我写的垃圾代码
倒序法