Evaluate Postfix Expression Using Stack in DSA Python - Time & Space Complexity

Time Complexity: Evaluate Postfix Expression Using Stack

O(n)

Understanding Time Complexity

We want to understand how the time taken to evaluate a postfix expression changes as the expression gets longer.

Specifically, how does the number of steps grow when we use a stack to solve this?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def evaluate_postfix(expression):
    stack = []
    for char in expression:
        if char.isdigit():
            stack.append(int(char))
        else:
            right = stack.pop()
            left = stack.pop()
            if char == '+':
                stack.append(left + right)
            elif char == '*':
                stack.append(left * right)
    return stack.pop()
    

This code evaluates a postfix expression with single-digit numbers and '+' or '*' operators using a stack.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each character in the expression once.
• How many times: Exactly once for each character in the input expression.

How Execution Grows With Input

Each character in the expression is processed once, so the steps grow directly with the length of the expression.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The number of operations increases in a straight line as the input size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to evaluate grows directly in proportion to the length of the postfix expression.

Common Mistake

[X] Wrong: "Evaluating postfix expressions takes more than linear time because of the stack operations."

[OK] Correct: Each character is handled once, and stack operations (push/pop) are very fast and happen only once per character, so overall time stays linear.

Interview Connect

Understanding this linear time behavior helps you explain how stacks efficiently solve expression evaluation problems, a common topic in interviews.

Self-Check

"What if the expression contained multi-digit numbers separated by spaces? How would the time complexity change?"