题目描述
leetcode 第227题:基本计算器 II
给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
示例:
输入:s = " 3+5 / 2 "
输出:5
解题方法
栈
参照题解
- 解题思路
由于字符串表达式
s
中存在空格,需要先去除空格,这时s
中仅存在数字、加减乘除号
然后定义变量sign
来标示每个数前面的运算符
对于s
,第一个数前面的符号一定为正,3+5看作0+3+5,所以sign
默认为+
,
先计算乘除后整体转换为加法运算,创建栈stack
存储每次需要相加的数值
获取s
的长度n
,在[0,n)
的范围内循环得到当前字符s[i]
如果s[i]
为数字,计算当前数字的数值num
如果s[i]
为运算符或者下标i
等于n-1
(保证末尾数字参与运算)时
分别考虑以下情况:
s[i]
为+
号,num
压栈
s[i]
为-
号,负的num
压栈
s[i]
为*
号,计算num
与栈顶元素相乘的结果后压栈
s[i]
为/
号,计算num
与栈顶元素相除的结果后压栈
每次压栈后,更新sign
为当前的运算符并将num
清零
最后将栈stack
中元素求和,即为s
计算后的值
- 复杂度
时间复杂度:O(n),n为字符串s的长度
空间复杂度:O(n),n为字符串s的长度
python3
class Solution:
def calculate(self, s: str) -> int:
s = s.replace(" ","")
n = len(s)
sign = "+"
stack = []
i = num = 0
while i<n:
if s[i].isdigit():
num = num*10+int(s[i])
if not s[i].isdigit() or i==n-1:
if sign=="+":
stack.append(num)
elif sign=="-":
stack.append(-num)
elif sign=="*":
stack.append(stack.pop()*num)
elif sign=="/":
stack.append(int(stack.pop()/num))
sign = s[i]
num = 0
i+=1
return sum(stack)
php
class Solution {
function calculate($s) {
$s = str_replace(" ","",$s);
$n = strlen($s);
$sign = "+";
$stack = [];
$i = $num = 0;
while($i<$n){
if(is_numeric($s[$i])){
$num = $num*10+$s[$i];
}
if(!is_numeric($s[$i]) || $i==$n-1){
if($sign=="+"){
array_push($stack,$num);
}elseif($sign=="-"){
array_push($stack,-$num);
}elseif($sign=="*"){
array_push($stack,array_pop($stack)*$num);
}elseif($sign=="/"){
array_push($stack,(int) (array_pop($stack)/$num));
}
$num = 0;
$sign = $s[$i];
}
$i++;
}
return array_sum($stack);
}
}
网友评论