题目描述:
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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。