LC-0150 Medium LeetCode

150. Evaluate Reverse Polish Notation

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 55% Topics: Array, Math, Stack

Reading material

Arrays & Hashing 12 min Math & Geometry 12 min Stacks & Queues 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

import operator

class Solution(object):
    # @param tokens, a list of string
    # @return an integer
    def evalRPN(self, tokens):
        numerals, operators = [], {"+": operator.add, "-": operator.sub, "*": operator.mul, "/": operator.div}
        for token in tokens:
            if token not in operators:
                numerals.append(int(token))
            else:
                y, x = numerals.pop(), numerals.pop()
                numerals.append(int(operators[token](x * 1.0, y)))
        return numerals.pop()

Solution from kamyu104/LeetCode-Solutions · MIT