224. 基本计算器
实现一个基本的计算器来计算一个简单的字符串表达式 s
的值。
示例 1:
1 | 输入:s = "1 + 1" |
示例 2:
1 | 输入:s = " 2-1 + 2 " |
示例 3:
1 | 输入:s = "(1+(4+5+2)-3)+(6+8)" |
提示:
1 <= s.length <= 3 * 105
s
由数字、'+'
、'-'
、'('
、')'
、和' '
组成s
表示一个有效的表达式
方法一:栈
基本计算器只包含加减法,括号对一个数只影响其正负。以示例三为例:
- 数字 1 前面没有符号,记为 +1
- 数字 4 前面有一个 + 号,记为 +4
- 数字 5 和 数字 2 前面有两个 + 号,记为 +5,+2
- 数字 3 前面有一个 + 号(不包括(4 + 5 + 2)里的 + 号)和一个 - 号,记为 -3
- 数字 6 前面有一个 + 号,记为 +6
- 数字 8 前面有两个 + 号,记为 + 8
将这些数字加起来,我们得到最终结果 23。
我们使用一个栈 ops 来记录当前位置所处的每个括号所共同形成的符号,同时使用 sign 来表示当前的符号(sign 为 1 代表正数)。
如果当前遇到了 + 号,当前符号为 ops.peek();如果当前遇到了 - 号,当前符号为 - ops.peek()。
每当遇到 ( 时,都要将当前 sign 取值压入栈中;每当遇到 )时,都从栈中弹出一个元素。
1 | class Solution { |
- 时间复杂度O(n)
- 空间复杂度O(n)
v1.5.2