Teaching Kids Programming – Evaluate Reverse Polish Notation


Teaching Kids Programming: Videos on Data Structures and Algorithms

Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, and /. Each operand may be an integer or another expression. Note that division between two integers should truncate toward zero. It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.

Example 1:
Input: tokens = [“2″,”1″,”+”,”3″,”*”]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:
Input: tokens = [“4″,”13″,”5″,”/”,”+”]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:
Input: tokens = [“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

Constraints:
1 <= tokens.length <= 10^4
tokens[i] is either an operator: “+”, “-“, “*”, or “/”, or an integer in the range [-200, 200].

Evaluate Reverse Polish Notation using a Stack

Let’s walk through each token from left to right. If we have numbers, we simply push it to a stack, otherwise, we pop two numbers from the stack and perform the corresponding operations (which can be defined as lambda functions). The result is then pushed back to the stack.

The result of the RPN (Reverse Polish Notation) expression is at the top of the stack. The time complexity is O(N) and the space complexity is also O(N) as we need a stack.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:        
        operations = {
            "+": lambda a, b: a + b,
            "-": lambda a, b: a - b,
            "/": lambda a, b: int(a/b),
            "*": lambda a, b: a * b
        }
        stack = []
        for e in tokens:
            if e in operations:
                n2 = stack.pop()
                n1 = stack.pop()
                stack.append(operations[e](n1, n2))
            else:
                stack.append(int(e))
        return stack[-1] # or stack.pop()        
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:        
        operations = {
            "+": lambda a, b: a + b,
            "-": lambda a, b: a - b,
            "/": lambda a, b: int(a/b),
            "*": lambda a, b: a * b
        }
        stack = []
        for e in tokens:
            if e in operations:
                n2 = stack.pop()
                n1 = stack.pop()
                stack.append(operations[e](n1, n2))
            else:
                stack.append(int(e))
        return stack[-1] # or stack.pop()        

See also: How to Evaluate Reverse Polish Notation using Stack?

Supporting Unary Operators in Reverse Polish Notation

The RPN can support the unary operators, for example the “+” and “-“. Thus, we can evaluate the RPN with Unary Operators such as -(1+2) i.e. [“1”, “2”, “+”, “-“]

We just need to check the size of the stack, if it is only one – then it is unary.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:        
        operations = {
            "+": lambda a, b: a + b,
            "-": lambda a, b: a - b,
            "/": lambda a, b: int(a/b),
            "*": lambda a, b: a * b
        }
        stack = []
        for e in tokens:
            if e in operations:
                if len(stack) == 0:
                    raise Exception("No Numbers Found")
                elif len(stack) == 1:
                    if e in ["+", "-"]:
                        stack.append(-stack.pop())
                    else:
                        raise Exception("Only Unary +/- Supported")
                else:
                    n2 = stack.pop()
                    n1 = stack.pop()
                    stack.append(operations[e](n1, n2))
            else:
                stack.append(int(e))
        return stack[-1]
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:        
        operations = {
            "+": lambda a, b: a + b,
            "-": lambda a, b: a - b,
            "/": lambda a, b: int(a/b),
            "*": lambda a, b: a * b
        }
        stack = []
        for e in tokens:
            if e in operations:
                if len(stack) == 0:
                    raise Exception("No Numbers Found")
                elif len(stack) == 1:
                    if e in ["+", "-"]:
                        stack.append(-stack.pop())
                    else:
                        raise Exception("Only Unary +/- Supported")
                else:
                    n2 = stack.pop()
                    n1 = stack.pop()
                    stack.append(operations[e](n1, n2))
            else:
                stack.append(int(e))
        return stack[-1]

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
589 words
Last Post: Teaching Kids Programming - Minimum Difference Between Highest and Lowest of K Scores
Next Post: Teaching Kids Programming - Leaderboard Algorithm: Compute the Ranking of Numbers

The Permanent URL is: Teaching Kids Programming – Evaluate Reverse Polish Notation

Leave a Reply