题目描述：
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.
题目大意：
实现一个简易计算器，计算简单表达式的值。
表达式字符串可能包含左括号（、右括号），加号 + 或者减号 -， 非负整数和空白字符。
你可以假设给定的表达式总是有效的。
测试样例见题目描述。
注意：不要使用内置库函数eval
解题思路：
表达式求值可以分解为下列两步完成：
1. 中缀表达式转为后缀表达式（逆波兰表达式）
2. 后缀表达式求值
以下内容来自百度百科：“后缀表达式”词条
中缀表达式转为后缀表达式的要点：
开始扫描；
数字时，加入后缀表达式；
运算符：
a. 若为 '('，入栈；
b. 若为 ')'，则依次把栈中的的运算符加入后缀表达式中，直到出现'('，从栈中删除'(' ；
c. 若为 除括号外的其他运算符， 当其优先级高于除'('以外的栈顶运算符时，直接入栈。否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或者遇到了一个左括号为止。
·当扫描的中缀表达式结束时，栈中的的所有运算符出栈；
后缀表达式求值的过程简述：
建立一个栈S
从左到右读表达式，如果读到操作数就将它压入栈S中
如果读到n元运算符(即需要参数个数为n的运算符)则取出由栈顶向下的n项按操作符运算，再将运算的结果代替原栈顶的n项，压入栈S中
如果后缀表达式未读完，则重复上面过程，最后输出栈顶的数值则为结束。
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())
return tokens
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)
本文链接：http://bookshadow.com/weblog/2015/06/09/leetcode-basic-calculator/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
