描述
Given a string s which represents an expression, evaluate this expression and return its value.
The integer division should truncate toward zero.
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
Example 1:
1
2
| Input: s = "3+2*2"
Output: 7
|
Example 2:
1
2
| Input: s = " 3/2 "
Output: 1
|
Example 3:
1
2
| Input: s = " 3+5 / 2 "
Output: 5
|
Constraints:
1 <= s.length <= 3 * 105s 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, 231 - 1].
- The answer is guaranteed to fit in a 32-bit integer.
分析
解析字符串表达式，实现一个基础的计算器。利用栈实现。
解决方案1（Python）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution:
def calculate(self, s: str) -> int:
sLen = len(s)
stack = []
preSign = "+"
num = 0
for i in range(sLen):
if s[i] != ' ' and s[i].isdigit():
num = num * 10 + ord(s[i]) - ord('0')
if i == sLen-1 or s[i] in '+-*/':
if preSign == "+":
stack.append(num)
elif preSign == "-":
stack.append(-num)
elif preSign == "*":
stack.append(stack.pop() * num)
else:
stack.append(int(stack.pop() / num))
preSign = s[i]
num = 0
return sum(stack)
|
解决方案2(Golang)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| func calculate(s string) int {
stack, preCh, num, result := []int{}, '+', 0, 0
for i, ch := range s {
isDigit := false
if '0' <= ch && ch <= '9' {
isDigit = true
}
if isDigit {
num = num * 10 + int(ch-'0')
}
if !isDigit && ch != ' ' || i == len(s) - 1 {
switch preCh {
case '+':
stack = append(stack, num)
case '-':
stack = append(stack, -num)
case '*':
stack[len(stack) - 1] *= num
default:
stack[len(stack)-1] /= num
}
preCh = ch
num = 0
}
}
for _, v := range stack {
result += v
}
return result
}
|
相关问题