题目描述
leetcode 第224题:基本计算器
实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。
示例:
输入:s = “ (1+(4+5+2)-3)+(6+8) “
输出:23
解题方法
栈
参照题解
- 解题思路
由于字符串表达式
s
中存在空格,需要先去除空格,这时s
中仅存在数字、加减号、括号
将s
整体转换为加法运算,减去一个数可以理解为加上这个数的负数,1-1看作1+(-1)
然后定义变量sign
来标示每个数前面的正负符号{-1,+1}
对于s
,第一个数前面的符号一定为正,1-1看作0+1-1,所以sign
默认为1并压栈
定义变量sumS
,存储s
计算后的值,初始为0
获取s
的长度n
,在[0,n)
的范围内循环得到当前字符s[i]
如果s[i]
为+
号,则更新sign
为栈顶元素
如果s[i]
为-
号,则更新sign
为栈顶元素的负数
如果s[i]
为(
号,将当前的sign
压栈
如果s[i]
为)
号,弹出栈顶元素
如果s[i]
为数字,sumS
累加当前数字的数值sign*num
最后s
计算后的值就是sumS
- 复杂度
时间复杂度:O(n),n为字符串s的长度
空间复杂度:O(n),n为字符串s的长度
- 代码实现
python3
1 | class Solution: |
php
1 | class Solution { |