Leetcode: Evaluate Reverse Polish Notation

Evaluate Reverse Polish Notation



Similar Problems:


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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## Blog link: https://code.dennyzhang.com/evaluate-reverse-polish-notation
## Basic Ideas: Use stack
## Complexity: Time O(n), Space O(n)
class Solution(object):
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        length = len(tokens)
        if length == 0:
            return None

        stack = []
        for token in tokens:
            if token not in '+-*/':
                stack.append(int(token))
            else:
                num2 = int(stack.pop())
                num1 = int(stack.pop())
                if token == '+':
                    v = num1+num2
                if token == '-':
                    v = num1-num2
                if token == '*':
                    v = num1*num2
                if token == '/':
                    if num1*num2 < 0:
                        v = abs(num1)/abs(num2)
                        v = -v
                    else:
                        v = num1/num2
                stack.append(v)
                #print stack[-1]
        return stack.pop()

# s = Solution()
# print s.evalRPN(["10","6","9","3","+","-11","*","/","*","17","+","5","+"]) # 22
# print s.evalRPN(["2", "1", "+", "3", "*"]) # 9
# print s.evalRPN(["4", "13", "5", "/", "+"]) # 6
# print s.evalRPN(["18"]) # 18
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.