0227. Basic Calculator I I

# 227. Basic Calculator II#

## 题目 #

Given a string `s` which represents an expression, evaluate this expression and return its value.

The integer division should truncate toward zero.

Example 1:

``````Input: s = "3+2*2"
Output: 7
``````

Example 2:

``````Input: s = " 3/2 "
Output: 1
``````

Example 3:

``````Input: s = " 3+5 / 2 "
Output: 5
``````

Constraints:

• `1 <= s.length <= 3 * 10^5`
• `s` consists of integers and operators `('+', '-', '*', '/')` separated by some number of spaces.
• `s` represents a valid expression.
• All the integers in the expression are non-negative integers in the range `[0, 2^31 - 1]`.
• The answer is guaranteed to fit in a 32-bit integer.

## 解题思路 #

• 这道题是第 224 题的加强版。第 224 题中只有加减运算和括号，这一题增加了乘除运算。由于乘除运算的优先级高于加减。所以先计算乘除运算，将算出来的结果再替换回原来的算式中。最后只剩下加减运算，于是题目降级成了第 224 题。
• 把加减运算符号后面的数字压入栈中，遇到乘除运算，直接将它与栈顶的元素计算，并将计算后的结果放入栈顶。若读到一个运算符，或者遍历到字符串末尾，即认为是遍历到了数字末尾。处理完该数字后，更新 `preSign` 为当前遍历的字符。遍历完字符串 `s` 后，将栈中元素累加，即为该字符串表达式的值。时间复杂度 O(n)，空间复杂度 O(n)。

## 代码 #

``````package leetcode

func calculate(s string) int {
stack, preSign, num, res := []int{}, '+', 0, 0
for i, ch := range s {
isDigit := '0' <= ch && ch <= '9'
if isDigit {
num = num*10 + int(ch-'0')
}
if !isDigit && ch != ' ' || i == len(s)-1 {
switch preSign {
case '+':
stack = append(stack, num)
case '-':
stack = append(stack, -num)
case '*':
stack[len(stack)-1] *= num
default:
stack[len(stack)-1] /= num
}
preSign = ch
num = 0
}
}
for _, v := range stack {
res += v
}
return res
}
``````

Apr 8, 2023