Evaluate Reverse Polish Notation

Problem Statement

You are given an array of strings tokens that represents a valid arithmetic expression in Reverse Polish Notation.

Return the integer that represents the evaluation of the expression.

The operands may be integers or the results of other operations.
The operators include '+', '-', '*', and '/'.
Assume that division between integers always truncates toward zero.

Example 1:

Input: tokens = ["1","2","+","3","*","4","-"]
Output: 5
Explanation: ((1 + 2) * 3) - 4 = 5

Constraints:

1 <= tokens.length <= 1000.
tokens[i] is "+", "-", "*", or "/", or a string representing an integer in the range [-100, 100].

You should aim for a solution with O(n) time and O(n) space, where n is the size of the input array.

Recommended Time and Space Complexity

You should aim for a solution with O(n) time and O(n) space, where n is the size of the input array.

Hint 1

A brute force solution would involve repeatedly finding an operator + - * / in the array and modifying the array by computing the result for that operator and two operands to its left. This would be an O(n^2) solution. Can you think of a better way? Maybe we can use a data structure to handle operations efficiently.

Hint 2

We can use a stack. We iterate through the array, and if we encounter a number, we push it onto the stack. If we encounter an operator, we pop two elements from the stack, treat them as operands, and solve the equation using the current operator. Then, we push the result back onto the stack. Why does this work?

Hint 3

As the array has postfix expression, stack helps us to maintain the correct order of operations by ensuring that we always use the most recent operands (those closest to the operator) when performing the operation. After the iteration, the final result is left in the stack.

Solution

Brute Force

def eval_rpn(tokens: list[str]) -> int:
    while len(tokens) > 1:
        for i in range(len(tokens)):
            if tokens[i] in "+-*/":
                a = int(tokens[i-2])
                b = int(tokens[i-1])
                if tokens[i] == '+':
                    result = a + b
                elif tokens[i] == '-':
                    result = a - b
                elif tokens[i] == '*':
                    result = a * b
                elif tokens[i] == '/':
                    result = int(a / b)
                tokens = tokens[:i-2] + [str(result)] + tokens[i+1:]
                break
    return int(tokens[0])

Time complexity: O(n^2) Space complexity: O(n)

Doubly Linked List

class DoublyLinkedList:
    def __init__(self, val, next=None, prev=None):
        self.val = val
        self.next = next
        self.prev = prev


def eval_rpn(tokens: list[str]) -> int:
    head = DoublyLinkedList(tokens[0])
    curr = head

    for i in range(1, len(tokens)):
        curr.next = DoublyLinkedList(tokens[i], prev=curr)
        curr = curr.next

    while head is not None:
        if head.val in "+-*/":
            l = int(head.prev.prev.val)
            r = int(head.prev.val)
            if head.val == '+':
                res = l + r
            elif head.val == '-':
                res = l - r
            elif head.val == '*':
                res = l * r
            else:
                res = int(l / r)

            head.val = str(res)
            head.prev = head.prev.prev.prev
            if head.prev is not None:
                head.prev.next = head

        ans = int(head.val)
        head = head.next

    return ans

Time complexity: O(n) Space complexity: O(n)

Recursion

def eval_rpn(tokens: list[str]) -> int:
    def dfs():
        token = tokens.pop()
        if token not in "+-*/":
            return int(token)

        right = dfs()
        left = dfs()

        if token == '+':
            return left + right
        elif token == '-':
            return left - right
        elif token == '*':
            return left * right
        elif token == '/':
            return int(left / right)

    return dfs()

Time complexity: O(n) Space complexity: O(n)

Stack

def eval_rpn(tokens: list[str]) -> int:
    stack = []
    for token in tokens:
        if token == "+":
            stack.append(stack.pop() + stack.pop())
        elif token == "-":
            a, b = stack.pop(), stack.pop()
            stack.append(b - a)
        elif token == "*":
            stack.append(stack.pop() * stack.pop())
        elif token == "/":
            a, b = stack.pop(), stack.pop()
            stack.append(int(float(b) / a))
        else:
            stack.append(int(token))
    return stack[0]

Time complexity: O(n) Space complexity: O(n)