[LeetCode]Basic Calculator

题目描述:

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

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

暂无评论

张贴您的评论