Evaluating Postfix Expressions with Stacks

Welcome back! In our last lesson, we explored the monotonic stack, a clever pattern for efficiently finding the next greater or smaller element in a sequence. This demonstrated how enforcing a property on a data structure can lead to highly optimized solutions.

Today, we'll continue our work with stacks by tackling a classic computer science problem: evaluating postfix expressions. This topic might seem a bit unusual at first, but it's a perfect illustration of how stacks can be used to parse and compute expressions that are structured differently from the standard arithmetic we use every day. Your goal for this lesson is to learn how to evaluate these postfix expressions using an explicit operand stack. This is a fundamental algorithm that cleanly showcases the LIFO (Last-In, First-Out) nature of stacks.

From Infix to Postfix: A New Way to Write Expressions

In our daily lives and most programming, we use infix notation, where operators sit between their operands: 3 + 4. However, there are other ways to represent the same logic.

One such way is postfix notation, also known as Reverse Polish Notation (RPN). In RPN, the operator comes after its operands: 3 4 +.

Let's look at a more complex example:

• Infix: (2 + 3) * 5
• Postfix: 2 3 + 5 *

Why would anyone use this? One key advantage of postfix notation is that it's unambiguous and doesn't require parentheses or rules for operator precedence (* before +). The order of operations is determined entirely by the sequence of tokens. This property made it popular in early stack-based calculators and some programming languages.

To get a feel for how to read and manually evaluate these expressions, the following video offers an excellent primer.

The Algorithm: Evaluating RPN with a Stack

As you might have guessed from the manual process, the "wait for an operator and then use the last two numbers" pattern is a perfect fit for a stack. The algorithm is straightforward and elegant:

1. Create an empty stack, which will hold operands (numbers).
2. Iterate through the tokens of the postfix expression from left to right.
3. If the token is an operand, push it onto the stack.
4. If the token is an operator (+, -, *, /), do the following:
   a. Pop the top two operands from the stack.
   b. Crucially, the first element popped is the right-hand operand, and the second element popped is the left-hand operand.
   c. Perform the operation.
   d. Push the result back onto the stack.
5. After processing all tokens, the stack will contain a single number: the final result.

The Back To Back SWE video below provides a fantastic walkthrough of this exact process.

A Detailed Trace

Let's trace a complete example using a table. The image below shows the step-by-step evaluation of the expression 20 50 3 6 + * * 300 / 2 -. Pay close attention to the "Action" and "Stack" columns to see how the stack state changes with each token.

Let's follow the first few steps from the image:

1. Tokens 20, 50, 3, 6: These are all operands, so they are pushed onto the stack in order. The stack becomes [20, 50, 3, 6].
2. Token +: This is an operator.
   • Pop 6 (right operand).
   • Pop 3 (left operand).
   • Calculate 3 + 6 = 9.
   • Push 9. The stack is now [20, 50, 9].
3. Token *: Another operator.
   • Pop 9 (right operand).
   • Pop 50 (left operand).
   • Calculate 50 * 9 = 450.
   • Push 450. The stack is now [20, 450].

This process continues until only the final result, 28, remains on the stack.

From Algorithm to Code: Implementation and Pitfalls

Translating this algorithm into code is quite direct, but there are a couple of critical details that often trip up developers. Given your experience, you know that subtle off-by-one errors or incorrect assumptions can derail an otherwise correct algorithm. The following resource provides a superb breakdown of a TypeScript implementation and, most importantly, highlights these common pitfalls.

For another look at a clean implementation in your preferred language, you can also refer to the code provided by GeeksForGeeks.

Complexity Analysis

The complexity analysis for this algorithm is very clean.

• Time Complexity: $O(n)$ where n is the number of tokens in the expression. We iterate through the tokens once, and each operation (push, pop, arithmetic) is $O(1)$.
• Space Complexity: $O(n)$ in the worst case. An expression like ["1", "2", "3", "4", "*", "+", "-"] would require pushing all operands onto the stack before any operations begin. The number of operands is roughly half the total tokens, so the space is proportional to n.

Conclusion

Today's lesson provided a very direct and satisfying application of the stack data structure. By following a simple set of rules, we can robustly evaluate postfix expressions, which are otherwise unintuitive to parse. This is a classic problem that reinforces the LIFO principle and its power in managing nested or ordered computations.

Key takeaways from this lesson:

• Postfix Notation (RPN): An unambiguous way of writing expressions where operators follow operands, eliminating the need for parentheses.
• The Algorithm: Iterate through tokens. Push operands to a stack. When an operator is found, pop two operands, compute, and push the result back.
• Key Pitfall #1 (Operand Order): For a - b, the postfix is a b -. The stack will pop b then a. The operation must be a - b.
• Key Pitfall #2 (Division): Be mindful of problem requirements for division, specifically whether to use floor division or truncation towards zero (Math.trunc() in JS/TS).
• Complexity: The algorithm is efficient, with $O(n)$ time and $O(n)$ space complexity.

This lesson concludes our module on linear data structures like linked lists, stacks, and queues. You've built a strong foundation in manipulating these fundamental building blocks. In our next lesson, we will pivot to an entirely new and powerful way of thinking about problems: recursion.