逆波兰表达式求值

题目要求

根据逆波兰表示法，求表达式的值。
比如 ["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", "+"]))