moonlightshadow123
6/19/2017 - 9:58 AM

150. Evaluate Reverse Polish Notation

  1. Evaluate Reverse Polish Notation
import math
class Solution(object):
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        operators = set(['+', '-', '*', '/'])
        stack = []
        for token in tokens:
            if token in operators:
                y = stack[-1]
                del stack[-1]
                x = stack[-1]
                del stack[-1]
                stack.append(self.operate(x, y, token))
            else:
                stack.append(int(token))
        return stack[-1]
    def operate(self, x, y, token):
        if token == '+':
            return x + y
        elif token == '-':
            return x - y
        elif token == '*':
            return x * y
        elif token == '/':
            if x*y < 0:
                return int(math.ceil(float(x) / y))
            else:
                return x / y

https://leetcode.com/problems/evaluate-reverse-polish-notation/#/description

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