LeetCode 150: Evaluate Reverse Polish Notation in C++ Using a Stack

Disclaimer

This article is an independent educational explanation of a programming problem originally published on LeetCode and included in the NeetCode 150 study list. The original problem statement, examples, constraints, trademarks, and related materials belong to LeetCode, NeetCode, and their respective rights holders.

The real-world scenario is a hypothetical educational adaptation and does not represent a confirmed company process unless explicitly stated with a reliable source.

The solution, explanation, and code are for learning and reference. Other valid approaches may exist. Readers should verify current requirements on the original problem pages.

Article Summary

The Evaluate Reverse Polish Notation problem asks us to calculate the result of an arithmetic expression written in postfix notation.

Unlike a normal arithmetic expression, an operator in Reverse Polish Notation appears after its operands. For example:

2 3 +

represents:

2 + 3

The main challenge is identifying which operands belong to each operator, especially when intermediate results are used by later operations.

A stack fits this process because the most recently discovered operands or intermediate results must be used first. Whenever we encounter a number, we push it onto the stack. Whenever we encounter an operator, we pop the two most recent values, perform the operation, and push the result back.

This article explains how to recognize the stack pattern, preserve the correct operand order, handle integer division in C++, and evaluate the complete expression in O(n) time.

Original Problem and Credit

This article is based on the LeetCode problem “150. Evaluate Reverse Polish Notation.”

• Original LeetCode problem: https://leetcode.com/problems/evaluate-reverse-polish-notation/
• NeetCode practice page: https://neetcode.io/problems/evaluate-reverse-polish-notation/question?list=neetcode150
• Platforms: LeetCode and NeetCode
• Original problem, examples, and constraints credit: LeetCode and NeetCode
• Explanation, adaptation, analysis, and commentary: Andy

The original problem statement is summarized and adapted rather than reproduced in full.

Real-World Scenario

Imagine a hypothetical data-processing platform that receives arithmetic transformation instructions from another system.

The instructions are encoded in postfix form so that the processing engine does not need parentheses or operator-precedence rules.

For example, the following instruction stream:

["1", "2", "+", "3", "*", "4", "-"]

represents this calculation:

((1 + 2) * 3) - 4

The processing engine reads the instructions from left to right.

When it receives a number, that number becomes an available input.

When it receives an operator, the engine applies that operator to the two most recently available values. The calculated result then becomes a new available value that can be used by a later instruction.

For example:

1
2
+

The + operator consumes 1 and 2, producing:

3

The next instructions are:

3
*

The multiplication operator consumes the previous result 3 and the new value 3, producing:

9

Finally:

4
-

The subtraction operator consumes 9 and 4, producing:

5

The platform therefore returns:

5

This scenario is hypothetical, but it preserves the token order, operand rules, supported operators, integer behavior, and expected results of the original problem.

Examples

Example 1

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

Output:
5

Explanation

The expression is evaluated as:

((1 + 2) * 3) - 4

Step by step:

1 + 2 = 3
3 * 3 = 9
9 - 4 = 5

Therefore, the final result is:

5

Example 2

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

Output:
9

Explanation

The postfix expression represents:

(2 + 1) * 3

The calculation is:

2 + 1 = 3
3 * 3 = 9

Therefore:

9

Example 3

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

Output:
6

Explanation

The postfix expression represents:

4 + (13 / 5)

Integer division truncates the decimal portion toward zero:

13 / 5 = 2

The remaining calculation is:

4 + 2 = 6

Therefore:

6

Constraints

On the provided NeetCode problem page:

1 <= tokens.length <= 1000

Each token is one of the following:

"+"
"-"
"*"
"/"

or a string representing an integer in the range:

-200 <= integer value <= 200

The complete token sequence represents a valid Reverse Polish Notation expression.

Division between integers truncates toward zero.

Mapping to the Original Problem

The terminology changes, but the input, output, ordering rules, supported operations, and expected behavior remain mathematically equivalent.

Solution Intuition

Understanding Reverse Polish Notation

Reverse Polish Notation, also called postfix notation, places each operator after its operands.

In a normal infix expression, an operator appears between its operands:

2 + 3

In postfix notation, the same expression becomes:

2 3 +

A more complex infix expression such as:

(2 + 3) * 4

becomes:

2 3 + 4 *

Because each operator appears only after its required operands, postfix notation does not need parentheses to describe the calculation order.

Recognizing the Stack Pattern

When an operator appears, it must use the two most recent values that have not already been consumed by another operator.

Consider:

["2", "3", "+", "4", "*"]

After reading 2 and 3, both numbers must be temporarily stored.

When + appears, it uses those two values:

2 + 3 = 5

The result 5 must then be stored because the later * operator will use it together with 4:

5 * 4 = 20

The most recently stored values are always the first values used by an operator.

This is a Last-In, First-Out, or LIFO, pattern.

A stack is designed for this behavior:

• push places a value on top of the stack.
• pop removes the top value.
• top retrieves the top value without removing it.

What the Stack Stores

The stack stores every available operand or intermediate result that has not yet been consumed.

When we read a number:

"13"

we convert it from a string to an integer and push it onto the stack:

st.push(std::stoi(each_token));

When we read an operator, we remove two values, calculate the result, and push that result back.

For example, suppose the stack is:

Top    5
       13
Bottom 4

If the next token is /, the two values used are:

13 / 5

After calculating the result, the stack becomes:

Top    2
Bottom 4

The intermediate result 2 can now be used by a later operator.

Why Operand Order Matters

When an operator appears, the first value popped from the stack is the right operand.

The second value popped is the left operand.

Suppose the postfix expression is:

["10", "3", "-"]

Before processing the operator, the stack is:

Top    3
Bottom 10

The first value removed is:

3

This is the right operand.

The second value removed is:

10

This is the left operand.

The correct calculation is:

10 - 3

not:

3 - 10

The same rule is important for division:

left_operand / right_operand

Addition and multiplication are commutative, so reversing their operands does not change their results:

a + b = b + a
a * b = b * a

Subtraction and division are not commutative:

a - b != b - a
a / b != b / a

Using descriptive names such as left_operand and right_operand helps prevent this mistake.

Processing a Number

If the current token is not an operator, it represents an integer.

Because tokens is a vector of strings, even numeric values arrive as strings:

"42"
"-11"
"7"

C++ cannot directly push these strings into a stack of integers.

The std::stoi function converts a numeric string into an integer:

st.push(std::stoi(each_token));

For example:

std::stoi("42")   // 42
std::stoi("-11")  // -11

The negative sign in "-11" is part of the number. It must not be confused with the subtraction operator "-".

Processing an Operator

When the current token is an operator:

1. Read and remove the right operand.
2. Read and remove the left operand.
3. Apply the operator in the correct order.
4. Push the calculated result back onto the stack.

For example:

["8", "3", "-"]

The stack operations are:

Push 8
Push 3
Pop 3 as the right operand
Pop 8 as the left operand
Calculate 8 - 3
Push 5

The stack now contains:

5

Why Intermediate Results Must Be Pushed Back

An operation result may become an operand for a later operation.

Consider:

["2", "1", "+", "3", "*"]

The first operation calculates:

2 + 1 = 3

That result must be saved because the multiplication operation uses it:

3 * 3 = 9

If the result were not pushed back onto the stack, the later operator would not be able to access it.

Integer Division in C++

For integer operands, C++ integer division discards the fractional part and truncates toward zero.

For example:

13 / 5   // 2

The mathematical result is 2.6, but both operands are integers, so C++ returns:

2

For a negative result:

-7 / 3   // -2

The mathematical result is approximately -2.333, and truncation toward zero produces:

-2

This behavior matches the division rule required by the problem.

Algorithm

1. Create an empty stack of integers.
2. Iterate through every token from left to right.
3. For each token:
   1. Check whether it is one of the four operators.
   2. If it is a number:
      • Convert it from a string to an integer using std::stoi.
      • Push the integer onto the stack.
   3. If it is an operator:
      • Read the top value as the right operand.
      • Remove the right operand from the stack.
      • Read the next top value as the left operand.
      • Remove the left operand from the stack.
      • Apply the current operator as left_operand operator right_operand.
      • Push the calculated result onto the stack.
4. After every token has been processed, the stack contains one value.
5. Return the value at the top of the stack.

Why the Algorithm Works

The main invariant is:

After processing any prefix of the token array, the stack contains the evaluated values of all complete subexpressions that have been discovered but have not yet been consumed by a later operator.

Base Case

Before processing any tokens, no operands or subexpressions have been discovered.

The stack is empty, so the invariant is true.

Processing a Number

Suppose the current token is a number.

A number is already a complete expression by itself. It has not yet been consumed by an operator, so the algorithm pushes its integer value onto the stack.

The stack therefore continues to contain exactly the available values of all completed but unconsumed expressions.

The invariant remains true.

Processing an Operator

Suppose the current token is an operator.

Because the token sequence is a valid Reverse Polish Notation expression, the two operands required by the operator have already been processed.

According to the invariant, their evaluated values are the two most recent available values on the stack.

The algorithm removes:

1. The right operand from the top.
2. The left operand from the next position.

It then evaluates:

left_operand operator right_operand

The two operand expressions have now been consumed, so they should no longer remain on the stack.

Their calculated result is a new complete expression that may be consumed by a later operator, so the algorithm pushes that result onto the stack.

The stack once again contains exactly the values of completed but unconsumed expressions.

Therefore, the invariant remains true.

Final State

The input represents one complete valid expression.

After all tokens have been processed, every smaller expression has been combined into the complete expression.

Therefore, exactly one evaluated value remains on the stack.

That value is the result of the entire Reverse Polish Notation expression, so returning st.top() is correct.

Complexity Analysis

Let n be the number of tokens in the input vector.

Time Complexity

The algorithm iterates through all n tokens exactly once.

For a numeric token, it performs:

• One conversion from string to integer
• One stack insertion

For an operator token, it performs:

• Two top operations
• Two pop operations
• One arithmetic operation
• One stack insertion

Each stack operation takes constant time.

The numeric strings have bounded length under the problem constraints, so converting each numeric token also takes constant time relative to n.

Therefore, the total time complexity is:

O(n)

Constant factors are ignored, so the complexity is not reported as O(2n) or any similar expression.

Space Complexity

The stack stores operands and intermediate results that have not yet been consumed.

In the worst case, many numeric tokens may appear before their corresponding operators.

For a valid binary Reverse Polish Notation expression, the maximum number of stored operands is proportional to the number of tokens. Although the exact maximum may be approximately half of the complete token count, constant factors are ignored in Big-O notation.

Therefore, the maximum stack size grows linearly with n.

The auxiliary space complexity is:

O(n)

The variables left_operand, right_operand, and the loop reference use only constant additional space:

O(1)

The stack is the largest input-dependent data structure, so the total auxiliary space remains:

O(n)

Corrected Solution: Evaluate the Expression with a Stack

The solution stores operands and intermediate results in a stack.

Numeric tokens are converted with std::stoi. When an operator appears, the code pops the right operand first and the left operand second, applies the operation in the correct order, and pushes the result back.

#include <stack>
#include <string>
#include <vector>

class Solution {
public:
    int evalRPN(std::vector<std::string>& tokens) {
        std::stack<int> st;

        for (const std::string& each_token : tokens) {
            if (each_token == "+" ||
                each_token == "-" ||
                each_token == "*" ||
                each_token == "/") {

                int right_operand = st.top();
                st.pop();

                int left_operand = st.top();
                st.pop();

                if (each_token == "+") {
                    st.push(left_operand + right_operand);
                } else if (each_token == "-") {
                    st.push(left_operand - right_operand);
                } else if (each_token == "*") {
                    st.push(left_operand * right_operand);
                } else {
                    st.push(left_operand / right_operand);
                }
            } else {
                st.push(std::stoi(each_token));
            }
        }

        return st.top();
    }
};

Why const std::string& Is Used

The loop is written as:

for (const std::string& each_token : tokens)

The ampersand means each_token is a reference to the existing string inside the vector.

Without the reference:

for (std::string each_token : tokens)

C++ creates a copy of every string during iteration.

Using a reference avoids those unnecessary copies:

const std::string& each_token

The const keyword means the loop is only allowed to read the token. It cannot modify the original string stored in tokens.

This is appropriate because the algorithm only needs to inspect each token.

Why the Input Uses std::vector<std::string>&

The function parameter is:

std::vector<std::string>& tokens

This means:

• std::vector is a dynamic array.
• std::string means every element is a string.
• & means the vector is passed by reference instead of being copied.

The input might look like:

{"2", "1", "+", "3", "*"}

Even the numbers are strings because the same vector must store both numbers and operators.

Passing the vector by reference avoids copying the complete input array when the function is called.

The function does not modify tokens, so outside LeetCode it could also be declared as:

int evalRPN(const std::vector<std::string>& tokens)

However, the supplied LeetCode function signature uses a non-const reference, so the corrected solution preserves that interface.

Walkthrough

Consider:

tokens = ["1", "2", "+", "3", "*", "4", "-"]

The expression represents:

((1 + 2) * 3) - 4

Initial State

Stack: empty

Token 1: "1"

The token is a number.

Convert it to an integer and push it:

Top    1

Token 2: "2"

The token is another number.

Push it:

Top    2
Bottom 1

Token 3: "+"

The token is an operator.

Pop the first value:

right_operand = 2

Pop the second value:

left_operand = 1

Calculate:

1 + 2 = 3

Push the result:

Top    3

Token 4: "3"

The token is a number.

Push it:

Top    3
Bottom 3

The bottom 3 is the result of 1 + 2. The top 3 came directly from the current token.

Token 5: "*"

Pop the first value:

right_operand = 3

Pop the second value:

left_operand = 3

Calculate:

3 * 3 = 9

Push the result:

Top    9

Token 6: "4"

The token is a number.

Push it:

Top    4
Bottom 9

Token 7: "-"

Pop the first value:

right_operand = 4

Pop the second value:

left_operand = 9

Calculate:

9 - 4 = 5

Push the result:

Top    5

Final Result

All tokens have been processed.

The only value remaining in the stack is:

5

Therefore, the function returns:

5

Common Mistakes

Pushing Operators onto the Integer Stack

The stack is declared as:

std::stack<int> st;

It can store integers, not strings such as:

"+"
"-"

Operators should trigger a calculation rather than being pushed onto the stack.

Correct behavior:

if (each_token is an operator) {
    // Pop operands and calculate.
} else {
    // Convert the number and push it.
}

Performing the Number Logic and Operator Logic in the Wrong Branch

Numeric tokens should be pushed immediately.

Operators should pop and combine previous values.

Reversing these branches causes the program to attempt calculations when reading numbers or attempt conversions when reading operators.

Reversing the Operands

The first value popped is the right operand:

int right_operand = st.top();
st.pop();

The second value popped is the left operand:

int left_operand = st.top();
st.pop();

The operation must be:

left_operand - right_operand

or:

left_operand / right_operand

Reversing them produces incorrect results for subtraction and division.

Calling pop() as Though It Returns a Value

In C++, std::stack::pop() removes the top element but does not return it.

This is invalid:

int value = st.pop();

The correct approach is:

int value = st.top();
st.pop();

First read the value with top(), and then remove it with pop().

Comparing a String with Character Literals

Each token has the type:

std::string

Therefore, operators should be compared with string literals:

each_token == "+"

A character literal uses single quotation marks:

'+'

That represents a char, not a std::string.

Because each_token is a string, double quotation marks are the clearest and correct choice:

"+"

Forgetting to Convert Numeric Strings

The input vector stores strings, while the stack stores integers.

This is invalid:

st.push(each_token);

The numeric token must first be converted:

st.push(std::stoi(each_token));

Treating a Negative Number as an Operator

The token:

"-11"

is a number.

The subtraction operator is exactly:

"-"

Checking for the complete operator string ensures that negative numeric tokens are passed to std::stoi correctly.

Forgetting to Push the Intermediate Result

After calculating an operation, its result may be needed by a later operator.

The result must be returned to the stack:

st.push(left_operand + right_operand);

Without this step, later operators would not have access to the intermediate value.

Returning st.pop()

The pop() function does not return the removed value.

This is invalid:

return st.pop();

After processing a valid expression, the answer is available through:

return st.top();

Expecting Decimal Division

The stack stores integers:

std::stack<int>

Therefore:

13 / 5

returns:

2

It does not return:

2.6

This integer behavior is required by the problem.

Reporting the Stack as Constant Space

Each individual stack element uses constant space, but the number of stored elements depends on the input size.

The stack may hold a linear number of operands and intermediate results.

Therefore, the auxiliary space complexity is:

O(n)

not:

O(1)

Reporting O(n / 2) as the Final Space Complexity

A valid expression may store approximately half of its tokens as operands before later operators consume them.

However, Big-O notation ignores constant factors:

O(n / 2) = O(n)

Therefore, the final auxiliary space complexity is:

O(n)

Key Takeaways

• Reverse Polish Notation places each operator after its operands.
• A stack follows Last-In, First-Out order and naturally stores the most recent available operands.
• Numeric strings must be converted to integers before being pushed onto an integer stack.
• When processing an operator, the first popped value is the right operand and the second is the left operand.
• Operand order is especially important for subtraction and division.
• Every intermediate result must be pushed back because it may be used by a later operator.
• C++ integer division truncates toward zero, matching the problem requirement.
• Each token is processed once, giving O(n) time complexity.
• The stack may grow proportionally to the input, giving O(n) auxiliary space complexity.