## 题目描述：

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

```"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23```

Note: Do not use the eval built-in library function.

## 解题思路：

1. 中缀表达式转为后缀表达式（逆波兰表达式）

2. 后缀表达式求值

a. 若为 '('，入栈；

b. 若为 ')'，则依次把栈中的的运算符加入后缀表达式中，直到出现'('，从栈中删除'(' ；

c. 若为 除括号外的其他运算符， 当其优先级高于除'('以外的栈顶运算符时，直接入栈。否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或者遇到了一个左括号为止。
·当扫描的中缀表达式结束时，栈中的的所有运算符出栈；

## Python代码：

``````class Solution:
# @param {string} s
# @return {integer}
def calculate(self, s):
tokens = self.toRPN(s)
return self.evalRPN(tokens)

operators = ['+', '-', '*', '/']

def toRPN(self, s):
tokens, stack = [], []
number = ''
for c in s:
if c.isdigit():
number += c
else:
if number:
tokens.append(number)
number = ''
if c in self.operators:
while len(stack) and self.getPriority(stack[-1]) >= self.getPriority(c):
tokens.append(stack.pop())
stack.append(c)
elif c == '(':
stack.append(c)
elif c == ')':
while len(stack) and stack[-1] != '(':
tokens.append(stack.pop())
stack.pop()
if number:
tokens.append(number)
while len(stack):
tokens.append(stack.pop())

def evalRPN(self, tokens):
operands = []
for token in tokens:
if token in self.operators:
y, x = operands.pop(), operands.pop()
operands.append(self.getVal(x, y, token))
else:
operands.append(int(token))
return operands[0]

def getVal(self, x, y, operator):
return {
'+': lambda x, y: x + y,
'-': lambda x, y: x - y,
'*': lambda x, y: x * y,
'/': lambda x, y: int(float(x) / y),
}[operator](x, y)

def getPriority(self, operator):
return {
'+' : 1,
'-' : 1,
'*' : 2,
'/' : 2,
}.get(operator, 0)
``````

Pingbacks已关闭。