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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Evaluate Reverse Polish Notation

Number: 150

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Microsoft, Meta, Citadel, Bloomberg, Yandex, Apple, Canonical, LinkedIn, Zendesk

Problem Description

Given an array of strings representing an arithmetic expression in Reverse Polish Notation (RPN), evaluate the expression and return the resulting integer. The valid operators are "+", "-", "*", and "/". The division between two integers should truncate toward zero. The input is guaranteed to be a valid RPN expression.

Key Insights

  • Use a stack to process the tokens.
  • Push numbers onto the stack.
  • When an operator is encountered, pop the top two numbers, perform the operation, and push the result back.
  • Handle division carefully to ensure it truncates toward zero.
  • The final result remains as the only value in the stack.

Space and Time Complexity

Time Complexity: O(n), where n is the number of tokens (each token is processed once). Space Complexity: O(n), in the worst-case scenario where all tokens are numbers and are stored in the stack.

Solution

We use a stack data structure to evaluate the RPN expression. Iterate through each token:

  1. If the token is a number, convert and push it onto the stack.
  2. If the token is an operator, pop the top two numbers (be careful about order), perform the corresponding arithmetic operation, and push the result back onto the stack.
  3. At the end of processing, the stack contains the result of the expression. Special attention is needed for division to ensure it truncates toward zero (using language-specific functions when necessary).

Code Solutions

def evalRPN(tokens):
    # Initialize a stack to hold numbers
    stack = []
    # Loop through each token in the input list
    for token in tokens:
        if token in {"+", "-", "*", "/"}:
            # Pop the two topmost values; note the order is important
            b = stack.pop()
            a = stack.pop()
            # Apply the operation based on the token
            if token == "+":
                result = a + b
            elif token == "-":
                result = a - b
            elif token == "*":
                result = a * b
            else:
                # Use int division to truncate towards zero
                result = int(a / b)
            # Push the result back onto the stack
            stack.append(result)
        else:
            # Token is a number; push its integer value onto the stack
            stack.append(int(token))
    # The final result is the only element left in the stack
    return stack.pop()

# Example usage:
# tokens = ["2", "1", "+", "3", "*"]
# print(evalRPN(tokens))  # Output: 9
← Back to All Questions