Table of contents
1.
Introduction
2.
Evaluation of Postfix Expression using Stack
3.
Illustration
4.
Postfix Evaluation for Multi-digit Numbers
4.1.
Reading the Expression
4.2.
Pushing Numbers onto the Stack
4.3.
Operators Work the Same
5.
Frequently Asked Questions
5.1.
Why use postfix notation instead of the more common infix notation?
5.2.
Can postfix evaluation handle operations beyond basic arithmetic like addition and subtraction?
5.3.
How does the stack help in evaluating postfix expressions?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

Evaluation of Postfix Expression

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

When we interact with computers & mathematical expressions, we often use the standard infix notation like 3 + 4 or a - b. However, computers find it easier to understand & process expressions when they're in postfix form, such as 3 4 + or a b -. This format, known as postfix notation, puts the operator after the operands. It's not just a quirky computer preference; this notation eliminates the need for parentheses & significantly simplifies the computation process.

Evaluation of Postfix Expression

This article takes you through the evaluation of postfix expressions, a fundamental concept in computer science that helps in understanding how expressions are processed by computers. 

Evaluation of Postfix Expression using Stack

A stack is a basic data structure that follows a particular order in which operations are performed. Think of it as a stack of books; you can only add (push) a book on top or remove (pop) the top book. This "last in, first out" (LIFO) principle is key in evaluating postfix expressions.

Here's how it works for postfix expressions:

  • Start Scanning: Read the postfix expression from left to right.
     
  • Operands Encounter: Whenever an operand (a number or variable) comes up, push it onto the stack. This is like adding a book to your stack.
     
  • Operator Encounter: When you see an operator (like +, -, *, /), pop the top two operands from the stack. These two operands are what the operator will work on.
     
  • Perform Operation: Carry out the operation based on the operator you encountered in step 3. The result of this operation is like getting a new book that's the sum or result of the two books (operands) you just took off your stack.
     
  • Push Result Back: The result from step 4? Push it back onto the stack. It's now the new top of the stack, ready to be used in future operations.
     
  • Repeat: Keep doing this until you've gone through the entire postfix expression.
     

Final Result: In the end, your stack will have one element left. This is the result of the postfix expression evaluation.

Illustration

To get a real feel for evaluating postfix expressions using a stack, let's walk through a simple example. Imagine we have the postfix expression 6 5 2 3 + - *. Here's how we'd evaluate it step by step:

Start with an empty stack: Imagine a clean slate, ready to be written on.

  • Scan 6: It's an operand, so push 6 onto the stack. Our stack now has one element: [6].
     
  • Scan 5: Another operand. Push 5 onto the stack, making it [6, 5].
     
  • Scan 2: Again, an operand. Our stack grows to [6, 5, 2].
     
  • Scan 3: Operand. The stack becomes [6, 5, 2, 3].
     
  • Scan +: An operator. Pop 3 & 2 (the top two elements) off the stack & add them. 2 + 3 = 5. Push this result back onto the stack, leaving us with [6, 5, 5].
     
  • Scan -: Operator time. Pop the top two elements (5 & 5), subtract the second from the first (5 - 5 = 0), & push the result (0) back. The stack now looks like [6, 0].
     
  • Scan *: Last operator. Pop 0 & 6, multiply them (6 * 0 = 0), & push the result back. Our stack, now just [0], holds the final result.
     

So, the result of the postfix expression 6 5 2 3 + - * is 0. By breaking it down step by step, we can see how each part of the expression affects the stack & leads to the final answer.

Postfix Evaluation for Multi-digit Numbers

When dealing with multi-digit numbers in postfix expressions, the approach remains largely the same, but with a slight twist. The key difference is in how we interpret the numbers during the scanning phase. Here's how it goes:

Reading the Expression

As we scan the expression, we need to be mindful of spaces or delimiters that separate numbers. Unlike single-digit numbers, multi-digit numbers can't be read one character at a time.

Pushing Numbers onto the Stack

Whenever we come across a number (now it could be more than one digit long), we read the entire number, treating spaces as the separator. This whole number is then pushed onto the stack as a single entity.

Operators Work the Same

When we encounter an operator, the process is the same as with single-digit expressions. We pop the top two numbers from the stack, perform the operation, and push the result back onto the stack.

For example, let's evaluate the postfix expression 23 8 7 + *. Here's the step-by-step breakdown:

  • Start with an empty stack.
     
  • Scan and push 23: The stack now has [23].
     
  • Scan and push 8: The stack becomes [23, 8].
     
  • Scan and push 7: Now, the stack is [23, 8, 7].
     
  • Encounter +: Pop 8 and 7, add them (8 + 7 = 15), and push 15 back. The stack updates to [23, 15].
     

Encounter *

  • Pop 23 and 15, multiply (23 * 15 = 345), and push the result 345 back onto the stack.
     
  • With the final stack being [345], we conclude that 345 is the result of the expression 23 8 7 + *.
     

This method extends the utility of postfix expressions to accommodate more complex and realistic numerical computations, making them even more powerful in practical applications.

Frequently Asked Questions

Why use postfix notation instead of the more common infix notation?

Postfix notation simplifies the computation process for computers. It eliminates the need for parentheses, making the order of operations clear & straightforward, which is not always the case with infix notation.

Can postfix evaluation handle operations beyond basic arithmetic like addition and subtraction?

Absolutely. Postfix evaluation is versatile & can handle a wide range of operations, including multiplication, division, exponentiation, & even more complex functions, as long as the operation involves taking a certain number of operands from the stack & pushing the result back.

How does the stack help in evaluating postfix expressions?

The stack provides an organized way to manage operands & operators. By following the "last in, first out" principle, it ensures that the most recent operands are used with the most recent operator, maintaining the correct order of operations without needing parentheses.

Conclusion

In this article, we've learned the essentials of evaluating postfix expressions, a fundamental concept that's instrumental in understanding computer arithmetic operations. Starting with the basics of using a stack for evaluation, we looked into the process step by step, even tackling multi-digit numbers to show the method's applicability to more complex expressions.

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure and AlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, DBMSSystem Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.

Live masterclass