Leetcode 150: Evaluate Reverse Polish Notation

150. Evaluate Reverse Polish Notation

  • Total Accepted: 76968
  • Total Submissions: 304324
  • Difficulty: Medium
  • Contributors: Admin

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

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

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

 

Code

class Solution(object):
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        stk = []
        for s in tokens:
            try:
                # test whether s is a number
                int(s)
                stk.append(s)
            except:
                a = stk.pop()
                b = stk.pop()
                stk.append(str(int(eval(str(float(b)) + s + a))))
                
        return int(stk[-1])

 

Idea

Use stack. Every time you see an operator, pop the last element in the stack.

Leave a comment

Your email address will not be published. Required fields are marked *