We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Evaluate Reverse Polish Notation

Difficulty: Medium

Problem Description

You are given an array of strings tokens that represents an arithmetic expression in Reverse Polish Notation. Evaluate the expression and return an integer that represents the value of the expression.

Key Insights

  • The valid operators are +, -, *, and /.
  • Operands can be either integers or expressions.
  • Division truncates towards zero.
  • The input is guaranteed to be a valid expression in Reverse Polish Notation.
  • We can use a stack to evaluate the expression efficiently.

Space and Time Complexity

Time Complexity: O(n), where n is the number of tokens in the input array.
Space Complexity: O(n), for storing the operands in the stack.

Solution

To solve the problem, we will utilize a stack data structure. The algorithm proceeds as follows:

  1. Initialize an empty stack.
  2. Iterate through each token in the input array.
  3. If the token is an operand (a number), convert it to an integer and push it onto the stack.
  4. If the token is an operator, pop the top two elements from the stack, apply the operator, and push the result back onto the stack.
  5. At the end of the iteration, the stack will contain a single element, which is the result of the expression.

Code Solutions

def evalRPN(tokens):
    stack = []
    for token in tokens:
        if token in ["+", "-", "*", "/"]:
            b = stack.pop()
            a = stack.pop()
            if token == "+":
                stack.append(a + b)
            elif token == "-":
                stack.append(a - b)
            elif token == "*":
                stack.append(a * b)
            elif token == "/":
                # Perform integer division that truncates toward zero
                stack.append(int(a / b))
        else:
            stack.append(int(token))
    return stack[0]
← Back to All Questions