逆波兰表达式求值

题目要求

根据逆波兰表示法,求表达式的值。
比如 ["2", "1", "+", "3", "*"],对应到小学所学的四则运算表达式就是((2 + 1) * 3) 计算结果为9

["4", "13", "5", "/", "+"] 所对应的四则运算表达式是 (4 + (13 / 5)) = 6

现在请计算["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] 的结果

思路分析

题目所要求计算的逆波兰表达式对应的四则运算表达式是((10 * (6 / ((9 + 3) * -11))) + 17) + 5

逆波兰表达式的计算,其实是栈这种数据结构的经典应用,将逆波兰表达式中的元素逐一放入一个栈中,当遇到运算符时,则从栈顶连续弹出两个元素进行计算,然后把计算结果放入到栈中,最后,栈里只有保存一个元素,这个元素就是整个表达式的计算结果。

因此这道题目,你需要实现一个简单的栈,好在有列表这种神器,栈的实现非常容易。

有一个比较坑的地方是python的除法,python中,采用的是向下取整的办法,比如

  • 5/3 = 1.666 向下取整得到1
  • 5/-3 = -1.6666 向下取整得到-2

其他语言中,5/-3会向上取整,就会得到-1, 这个是符合我们日常判断的,但python里却偏偏向下取整得到了-2,为了使结果符合人们的常识,需要用到operator 模块的truediv 方法。

示例代码

# coding=utf-8
import operator

class Stack(object):
    def __init__(self):
        self.items = []
        self.count = 0

    def push(self, item):
        """
        放入一个新的元素
        :param item:
        :return:
        """
        self.items.append(item)
        self.count += 1

    def top(self):
        # 获得栈顶的元素
        return self.items[self.count-1]

    def size(self):
        # 返回栈的大小
        return self.count

    def pop(self):
        # 从栈顶移除一个元素
        item = self.top()
        del self.items[self.count-1]
        self.count -= 1
        return item

def cal_exp(expression):
    stack = Stack()
    for item in expression:
        if item in "+-*/":
            # 遇到运算符就从栈里弹出两个元素进行计算
            value_1 = stack.pop()
            value_2 = stack.pop()
            if item == '/':
                res = int(operator.truediv(int(value_2), int(value_1)))
            else:
                res = eval(value_2 + item + value_1)
            # 计算结果最后放回栈,参与下面的计算
            stack.push(str(res))
        else:
            stack.push(item)

    res = stack.pop()
    return res

if __name__ == '__main__':
    print(cal_exp(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]))

扫描关注, 与我技术互动

QQ交流群: 211426309

加入知识星球, 每天收获更多精彩内容

分享日常研究的python技术和遇到的问题及解决方案