Evaluate Reverse Polish Notation - Practice Coding Problems

Evaluate Reverse Polish Notation - Problem

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.

Note that:

The valid operators are '+', '-', '*', and '/'
Each operand may be an integer or another expression
The division between two integers always truncates toward zero
There will not be any division by zero
The input represents a valid arithmetic expression in reverse polish notation
The answer and all intermediate calculations can be represented in a 32-bit integer

Input & Output

Example 1 — Basic RPN Expression

$ Input: tokens = ["2","1","+","3","*"]

› Output: 9

💡 Note: Step by step: Push 2, push 1, encounter '+' so pop 1 and 2, compute 2+1=3, push 3. Push 3, encounter '*' so pop 3 and 3, compute 3*3=9, push 9. Result is 9.

Example 2 — Division with Truncation

$ Input: tokens = ["4","13","5","/","+"]

› Output: 6

💡 Note: Push 4, push 13, push 5, encounter '/' so pop 5 and 13, compute 13/5=2 (truncated), push 2. Encounter '+' so pop 2 and 4, compute 4+2=6.

Example 3 — Negative Result

$ Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]

› Output: 22

💡 Note: Complex expression that evaluates through multiple stack operations, handling negative numbers and multiple operators.

Constraints

1 ≤ tokens.length ≤ 10⁴
tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200]

Visualization

Tap to expand

3+1=3Final Result9Process: Push 2 → Push 1 → Pop 2, compute 2+1=3, push 3 → Push 3 → Pop 2, compute 3*3=9Expression evaluates to: 9

Understanding the Visualization

Input

Array of tokens representing RPN expression

Process

Use stack to evaluate: push numbers, pop and compute for operators

Output

Single integer result of the expression

Key Takeaway

🎯 Key Insight: RPN eliminates the need for parentheses by using postfix notation where operators follow their operands

Asked in

a Amazon 25 M Microsoft 18 G Google 15 f Facebook 12

The key insight is that Reverse Polish Notation naturally maps to stack operations - operands are pushed onto a stack, and when an operator is encountered, the required number of operands are popped, the operation is performed, and the result is pushed back. Best approach is the stack-based solution with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Parsing	O(n)	O(n)	Parse tokens recursively to build and evaluate expression tree
Stack-Based Evaluation	O(n)	O(n)	Use a stack to store operands and evaluate operators immediately

Recursive Parsing — Algorithm Steps

Parse tokens to identify operators and operands
Build expression tree recursively
Evaluate tree by traversing nodes

Visualization

Tap to expand

Step-by-Step Walkthrough

Parse Tokens

Read tokens from right to left

Build Tree

Create nodes for operators with operand children

Evaluate

Traverse tree to compute final result

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int parseFromEnd(char tokens[][20], int size, int* pos) {
    if (*pos < 0) return 0;
    
    char* token = tokens[*pos];
    (*pos)--;
    
    if (strcmp(token, "+") == 0 || strcmp(token, "-") == 0 || 
        strcmp(token, "*") == 0 || strcmp(token, "/") == 0) {
        int right = parseFromEnd(tokens, size, pos);
        int left = parseFromEnd(tokens, size, pos);
        
        if (strcmp(token, "+") == 0) return left + right;
        else if (strcmp(token, "-") == 0) return left - right;
        else if (strcmp(token, "*") == 0) return left * right;
        else return (int)((double)left / right);
    }
    return atoi(token);
}

int solution(char tokens[][20], int size) {
    int pos = size - 1;
    return parseFromEnd(tokens, size, &pos);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    char tokens[100][20];
    int count = 0;
    
    char* token = strtok(line, "[],\"\n ");
    while (token != NULL && count < 100) {
        strcpy(tokens[count], token);
        count++;
        token = strtok(NULL, "[],\"\n ");
    }
    
    printf("%d\n", solution(tokens, count));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each token once during parsing and evaluation

✓ Linear Growth

Space Complexity

O(n)

Expression tree and recursion stack require O(n) space

⚡ Linearithmic Space

185.0K Views

Medium Frequency

~15 min Avg. Time

3.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Parsing — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler