You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.
Evaluate the expression. Return an integer that represents the value of the expression.
Note that:
'+', '-', '*', and '/'.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 <= 104tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].The key idea behind solving Evaluate Reverse Polish Notation is understanding how postfix expressions work. In Reverse Polish Notation (RPN), operators appear after their operands, removing the need for parentheses. A natural way to process this order is by using a stack.
Iterate through the array of tokens. When you encounter a number, push it onto the stack. When an operator such as +, -, *, or / appears, pop the top two numbers from the stack, apply the operation in the correct order, and push the result back onto the stack. Continue processing tokens until the end of the array.
The final value left in the stack represents the evaluated result of the expression. This approach works efficiently because each token is processed exactly once, making it well-suited for stack-based expression evaluation problems often seen in coding interviews.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Stack-based evaluation of RPN | O(n) | O(n) |
NeetCode
The stack-based approach is ideal for evaluating Reverse Polish Notation (RPN) expressions because it naturally follows the Last-In-First-Out (LIFO) principle, which aligns with the evaluation order of RPN expressions. The key idea is to iterate through the tokens, pushing operands onto the stack, and handling operators by popping the required number of operands from the stack, performing the operation, and pushing the result back onto the stack.
Time Complexity: O(n), where n is the number of tokens.
Space Complexity: O(n) due to stack usage.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5int evalRPN(char **tokens, intThe program uses an integer array as a stack to evaluate the RPN expression. As it processes each token:
The final result is the only element left on the stack.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
In RPN, the order of operations is inherently defined by the placement of operators after their operands. This eliminates ambiguity and removes the need for parentheses to control precedence.
Yes, this problem or variations of stack-based expression evaluation are commonly asked in technical interviews, including FAANG companies. It tests understanding of stacks, expression parsing, and careful handling of operator order.
A stack is the best data structure for this problem because postfix expressions naturally follow a last-in, first-out evaluation pattern. It allows easy retrieval of the most recent operands when an operator appears.
The optimal approach uses a stack to process tokens sequentially. Numbers are pushed onto the stack, while operators pop the top two values, apply the operation, and push the result back. This ensures each token is processed once, giving an efficient O(n) solution.