Skip to content

Latest commit

 

History

History
121 lines (91 loc) · 3.9 KB

0150._evaluate_reverse_polish_notation.md

File metadata and controls

121 lines (91 loc) · 3.9 KB

150. Evaluate Reverse Polish Notation

难度: Medium

刷题内容

原题连接

内容描述

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

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

栈

实际上这里有一个很奇（sha）怪（bi）的地方，看到了么，除法➗处，如果我不这么做，就是错的，这是python 2 和 python 3 的除法不一致导致的，所以最终我这样做了才能得到正确答案。

已经给了我们wikipedia的链接了https://en.wikipedia.org/wiki/Reverse_Polish_notation

  • While there are input tokens left
    • Read the next token from input.
    • If the token is a value
      • Push it onto the stack. -Otherwise, the token is an operator (operator here includes both operators and functions).
      • It is already known that the operator takes n arguments.
      • If there are fewer than n values on the stack
        • (Error) The user has not input sufficient values in the expression.
      • Else, Pop the top n values from the stack.
      • Evaluate the operator, with the values as arguments.
      • Push the returned results, if any, back onto the stack.
  • If there is only one value in the stack
    • That value is the result of the calculation.
  • Otherwise, there are more values in the stack
    • (Error) The user input has too many values.

再参考这里

http://interactivepython.org/runestone/static/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html

  1. Create an empty stack called operandStack.
  2. Convert the string to a list by using the string method split.
  3. Scan the token list from left to right.
    • If the token is an operand, convert it from a string to an integer and push the value onto the operandStack.
    • If the token is an operator, *, /, +, or -, it will need two operands. Pop the operandStack twice. The first pop is the second operand and the second pop is the first operand. Perform the arithmetic operation. Push the result back on the operandStack.
  4. When the input expression has been completely processed, the result is on the stack. Pop the operandStack and return the value.
class Solution(object):
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        stack = []
        for t in tokens:
            if t not in '+-*/':
                stack.append(int(t))
            else:
                r, l = stack.pop(), stack.pop()
                if t == "+":
                    stack.append(l+r)
                elif t == "-":
                    stack.append(l-r)
                elif t == "*":
                    stack.append(l*r)
                else:
                    stack.append(int(float(l) / r))
                    # here take care of the case like "1/-22",
                    # in Python 2.x, it returns -1, while in 
                    # Leetcode it should return 0
                    # if l*r < 0 and l % r != 0:
                    #     stack.append(l/r+1)
                    # else:
                    #     stack.append(l/r)
        return stack.pop()