Infix to Postfix Conversion and Evaluation

Why Different Notations?

We write math expressions in infix notation, where the operator is in between the operands (e.g., 3 + 4). While this is natural for humans, it's ambiguous for computers without rules for operator precedence (is 3 + 4 * 5 equal to 35 or 23?) and parentheses.

To solve this, we can use postfix notation, where the operator comes after its operands (e.g., 3 4 +). The expression 3 + 4 * 5 becomes 3 4 5 * +. This format is unambiguous and can be evaluated efficiently with a single left-to-right scan.

Our task is twofold:

1. Conversion: Transform a human-readable infix string into a computer-friendly postfix string.
2. Evaluation: Calculate the final value from the postfix string.

Part 1: Infix to Postfix Conversion

The core of this conversion is an algorithm often called the Shunting-yard algorithm, developed by Edsger Dijkstra. It uses a stack to correctly reorder operators based on their precedence and associativity.

Key Concepts: Precedence and Associativity

• Precedence: Determines which operators are applied first. In most systems, exponentiation (^) has the highest precedence, followed by multiplication (*) and division (/), and finally addition (+) and subtraction (-).
• Associativity: Determines the order for operators with the same precedence. Most operators (+, -, *, /) are left-associative (e.g., 10 - 5 - 2 is (10 - 5) - 2). Exponentiation is typically right-associative (2 ^ 3 ^ 2 is 2 ^ (3 ^ 2)).

To learn the algorithm and see how these rules are implemented in Java, the following article is an excellent resource.

The Conversion Algorithm at a Glance

As you read in the article, the process involves iterating through the infix expression and using a stack to manage operators and parentheses. Here is a summary of the rules:

1. Operand: If you see an operand (like A, B, or a number), append it directly to your output string.
2. Opening Parenthesis (: Push it onto the stack.
3. Closing Parenthesis ): Pop operators from the stack and append them to the output until you find an opening parenthesis (. Pop and discard the (.
4. Operator: This is the most complex step.
   • While the stack is not empty, its top is not (, AND the operator at the top of the stack has higher or equal precedence (for left-associative operators), pop from the stack and append to the output.
   • After the loop, push the current operator onto the stack.
5. End of Expression: After scanning the entire infix string, pop any remaining operators from the stack and append them to the output.

The following video provides a visual, step-by-step walkthrough of this process.

Here's an image that traces the algorithm for a complex expression, which can be a helpful reference.

Part 2: Postfix Expression Evaluation

Now that we have an unambiguous postfix expression, evaluating it is much simpler. We again use a stack, but this time, it will hold operands (numbers).

The Evaluation Algorithm

1. Initialize an empty stack of integers/doubles.
2. Scan the postfix expression from left to right.
3. If the token is an operand (a number), parse it and push it onto the stack.
4. If the token is an operator, pop the top two operands from the stack. Let's say you pop val2 first, then val1.
5. Perform the operation: result = val1 operator val2. Note the order! The second value popped is the first operand.
6. Push the result back onto the stack.
7. After iterating through all tokens, the stack will have exactly one value: the final result of the expression.

This image clearly illustrates the evaluation process.

Let's watch a video explanation before looking at the code.

Java Implementation

Now, let's look at a clean Java implementation for this algorithm.

As you can see from the code, the logic is very direct. The use of a Stack<Integer> simplifies the process immensely. You just need to handle the operators and push/pop values accordingly.

Conclusion

In this lesson, you've mastered two fundamental stack-based algorithms that are classics in computer science and frequently appear in technical interviews. You learned not just the "how" but also the "why"—understanding that converting to postfix notation removes ambiguity and makes evaluation trivial for a computer.

Key Takeaways:

• Infix to Postfix Conversion: Uses a stack to manage operators and parentheses based on precedence and associativity rules. The time complexity is O(N), where N is the length of the expression.
• Postfix Evaluation: Uses a stack to store operands. When an operator appears, it pops its required operands, computes the result, and pushes it back. This is also an O(N) process.
• Stacks are the perfect data structure for these problems due to their Last-In, First-Out (LIFO) nature, which naturally handles the nested structure of expressions.

Preview of the next lesson:
We are now at a turning point in our course. We've built a strong foundation with linear data structures like arrays, linked lists, stacks, and queues. In the next module, we will venture into the world of non-linear data structures, starting with Trees. Our first lesson will cover the fundamental ways to traverse a binary tree: preorder, inorder, and postorder traversals.