实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。
示例 1:输入:s = "1 1" 输出:2
示例 2:输入:s = " 2-1 2 " 输出:3
示例 3:输入:s = "(1 (4 5 2)-3) (6 8)" 输出:23
提示:1 <= s.length <= 3 * 105
s 由数字、' '、'-'、'('、')'、和 ' ' 组成
s 表示一个有效的表达式
解题思路分析1、栈;时间复杂度O(n),空间复杂度O(n)
func calculate(s string) int {
stack := make([]int, 0)
num := 0
res := 0
sign := 1
for i := 0; i < len(s); i {
if '0' <= s[i] && s[i] <= '9' {
num = 0
for ; i < len(s) && '0' <= s[i] && s[i] <= '9'; i {
num = num*10 int(s[i]-'0')
}
res = res sign*num
i--
} else if s[i] == ' ' {
sign = 1
} else if s[i] == '-' {
sign = -1
} else if s[i] == '(' {
stack = append(stack, res, sign)
res = 0
sign = 1
} else if s[i] == ')' {
sign = stack[len(stack)-1]
prev := stack[len(stack)-2]
stack = stack[:len(stack)-2]
res = prev sign*res*sign
}
}
return res
}
Hard题目,计算器系列题目,类似的题目还有 leetcode 227.基本计算器II
,