LeetCode 150. Evaluate Reverse Polish Notation

简介: 根据逆波兰表示法,求表达式的值。有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。

v2-8ce1dab25b770578bdf69ebd638c0df2_1440w.jpg


Description



Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.


Note:

Division between two integers should truncate toward zero.

The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation.


Example 1:


Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9


Example 2:


Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6


Example 3:


Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Explanation: 
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22


描述



根据逆波兰表示法,求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。


说明:


整数除法只保留整数部分。

给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。


思路



  • 使用两个栈来实现逆波兰表达式.
  • 先将表达式中的所有元素压入到栈1,接下来我们pop出栈,如果是数字则压入栈2,如果是符号我们从栈2中弹出两个数组,用刚才的符号对其进行操作,再将操作的结果压入栈2.最后的结果是栈2中剩下的一个元素.


# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-01-14 17:15:18
# @Last Modified by:   何睿
# @Last Modified time: 2019-01-14 17:50:02
class Solution:
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        stack1, stack2 = [], []
        for i in range(len(tokens) - 1, -1, -1):
            stack1.append(tokens[i])
        operateset = set(["+", "-", "*", "/"])
        while stack1:
            top = stack1.pop()
            if top in operateset:
                num1, num2 = stack2.pop(), stack2.pop()
                stack2.append(self.operate(top, num1, num2))
            else:
                stack2.append(int(top))
        return stack2[-1]
    def operate(self, op, num1, num2):
        if op == "+":
            return num2 + num1
        if op == "-":
            return num2 - num1
        if op == "*":
            return num2 * num1
        if op == "/":
            # 这里可以不用做判断,题目保证了除数不会是0
            return int(num2 / num1) if num1 != 0 else 0


源代码文件在这里.

目录
相关文章
|
索引
LeetCode 345. Reverse Vowels of a String
编写一个函数,以字符串作为输入,反转该字符串中的元音字母。
114 0
LeetCode 345. Reverse Vowels of a String
|
机器学习/深度学习 NoSQL
LeetCode 344. Reverse String
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。 不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
109 0
LeetCode 344. Reverse String
LeetCode 190. Reverse Bits
颠倒给定的 32 位无符号整数的二进制位。
100 0
LeetCode 190. Reverse Bits
LeetCode 92. Reverse Linked List II
给定一个链表,反转指定的子序列.
91 0
LeetCode 92. Reverse Linked List II
|
机器学习/深度学习 NoSQL 算法
LeetCode 344. 反转字符串 Reverse String
LeetCode 344. 反转字符串 Reverse String
LeetCode 206. 反转链表 Reverse Linked List
LeetCode 206. 反转链表 Reverse Linked List
LeetCode之Reverse String II
LeetCode之Reverse String II
123 0
LeetCode之Reverse String
LeetCode之Reverse String
110 0
LeetCode之Reverse Integer
LeetCode之Reverse Integer
110 0
LeetCode 150:逆波兰表达式求值 Evaluate Reverse Polish Notation
题目: 根据逆波兰表示法,求表达式的值。 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。 Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression. 说明: 整数除法只保留整数部分。
1383 0