150.逆波兰表达式求值

题目描述

根据逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：
输入：tokens = [“2”,”1”,”+”,”3”,”*”]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

题目链接

思路

1.栈
遍历逆波兰表达式中的每一个字符，遇到数字则将数字入栈，遇到运算符则将栈顶的两个操作数出栈作此运算符对应的运算，再将运算结果入栈，…，以此类推，直到遍历完整个表达式，栈中剩余的元素就是表达式的结果。
2.数组模拟栈
对于一个有效的逆波兰表达式，其长度 n 一定是奇数，且操作数的个数一定比运算符的个数多 1 个，即包含 (n+1)/2 个操作数和 (n-1)/2 个运算符。考虑遇到操作数和运算符时，栈内元素个数分别会如何变化：
如果遇到操作数，则将操作数入栈，因此栈内元素增加 1 个；
如果遇到运算符，则将两个操作数出栈，然后将一个新操作数入栈，因此栈内元素先减少 2 个再增加 1 个，结果是栈内元素减少 1 个。
由此可以得到操作数和运算符与栈内元素个数变化的关系：遇到操作数时，栈内元素增加 1 个；遇到运算符时，栈内元素减少 1 个。
最坏情况下，(n+1)/2 个操作数都在表达式的前面，(n-1)/2 个运算符都在表达式的后面，此时栈内元素最多为 (n+1)/2 个。在其余情况下，栈内元素总是少于 (n+1)/2 个。因此，在任何情况下，栈内元素最多可能有 (n+1)/2 个，将数组的长度定义为 (n+1)/2 即可。
具体实现方面，创建数组 stack 模拟栈，数组下标 0 的位置对应栈底，定义 index 表示栈顶元素的下标位置，初始时栈为空，index=−1。当遇到操作数和运算符时，进行如下操作：
如果遇到操作数，则将 index 的值加 111，然后将操作数赋给 stack[index]；
如果遇到运算符，则将 index 的值减 111，此时 stack[index] 和 stack[index+1] 的元素分别是左操作数和右操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数赋给 stack[index]。
整个逆波兰表达式遍历完毕之后，栈内只有一个元素，因此 index=0，此时 stack[index] 即为逆波兰表达式的值。

代码

class Solution(object):
    def evalRPN(self, tokens):
        """
        使用栈进行表达式求值

        :type tokens: List[str]
        :rtype: int
        """
        op_to_binary_fn = {
            "+": lambda x, y: x + y,
            '-': lambda x, y: x - y,
            '*': lambda x, y: x * y,
            '/': lambda x, y: int(x / y),
        }

        stack = list()
        for token in tokens:
            try:
                num = int(token)
            except ValueError:
                num2 = stack.pop()
                num1 = stack.pop()
                num = op_to_binary_fn[token](num1, num2)
            finally:
                stack.append(num)

        return stack[0]

    def evalRPN1(self, tokens):
        """
        使用数组模拟栈进行表达式求值

        :type tokens: List[str]
        :rtype: int
        """
        op_to_binary_fn = {
            "+": lambda x, y: x + y,
            '-': lambda x, y: x - y,
            '*': lambda x, y: x * y,
            '/': lambda x, y: int(x / y),
        }
        n = len(tokens)
        stack = [0] * ((n + 1) // 2)
        index = -1
        for token in tokens:
            try:
                num = int(token)
                index += 1
                stack[index] = num
            except ValueError:
                index -= 1
                stack[index] = op_to_binary_fn[token](stack[index], stack[index + 1])
        return stack[0]


if __name__ == "__main__":
    slt = Solution()
    # tokens = ["2", "1", "+", "3", "*"]
    # tokens = ["4", "13", "5", "/", "+"]
    tokens = ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
    print("表达式的值为：{}".format(slt.evalRPN1(tokens)))

victory的博客

leetcode | 150.逆波兰表达式求值

150.逆波兰表达式求值

题目描述

思路

代码