STACK and POSTFIX Notation

Ravi Pun Ravi Pun
Oct 22, 2020 - 02:52 Updated: Oct 22, 2020 - 02:54
0 1289
STACK and POSTFIX Notation

Hello everyone this post is about two important concepts in Computer Science: Stack and Postfix notation. Lets first dive deep into stack and then we will learn about the postfix notation. Stack is a data structure in which the data is added or removed at only one end called the top.

The operations that can be done on a stack are fairly simple:

  1. (PUSH) meaning ADD TO Top Of  the Stack (T.O.S)
  2. (POP) meaning REMOVE FROM T.O.S

Thus the last item to be pushed is the first item to be popped. This is known as LIFO: Last In First Out, which is really common in many computer science concepts.


PUSH, POP Visualizaation

The video shows how stack operations: PUSH and POP works. If you want to play around with the visualization tool shown there, click here. The visualization is made by USFCA CS department and there are many visualizations available for data structures and algorithms. Check them out here

Applications of Stack:

Stack is used in many things, some of which are:

  • Page-visited history in a Web Browser
  • Undo Sequence in a text Editor
  • Evaluating POSTFIX Expressions

Now the first two applications sound cool, right? But I am going to talk about the last one and try to make it fun. Tough job.

POSTFIX notation

What is 2+3*5 ? Silly question to ask for any of our readers. We can easily evaluate the answer as 17. But what if I ask you, what is 2 5*3+ ? and say it is actually a valid expression? I’m not kidding.

We were able to answer 2+3*5  because that’s how we interpret 3 times 5 added to 2. This is actually known in Computer Science as INFIX expression. We also know something called the preceedence rule or as our Maths teacher put it BODMAS rule. Bracket-Oblique-Divide-Multiply-… you know what it is.

But the point is that 2 5*3+ is an actual expression in Computer Science and is known as the POSTFIX notation. The INFIX operation is easily readable by HUMANS, but POSTFIX notation is used by computers or shall I say compilers.

Actually there are 3 types of notations, INFIX, POSTFIX and yes you guessed it right PREFIX notation.

PREFIX notation is also known as POLISH NOTATION and POSTFIX  notation is also known as REVERSE POLISH NOTATION: RPN

Why need PREFIX and POSTFIX?

  • Easier to parse for Machines
  • No question for operator precedence
  • Less overhead of brackets (prefix and postfix are parenthesis free notation)
  • This is why used by compilers

POSTFIX explanation

An example of the postfix notation is  1 2 + 3 – which is equivalent to 1+2-3. The rule here is: Operator follows its operand. Then what is the postfix for 2+14*5 ?

Its 2 14 5 * + .

Exercise:

Try to evaluate postfix for the following expressions. Answers are listed below the questions in reverse order:

  1. 16 / 2
  2. (2+14) * 5 
  3. (6-2)*(5+4)
  1. 6 2 – 5 4 + *
  2. 2 14 + 5 *
  3. 16 2 /

If you still do not get this conversion, you can try this oneline tool.

Compilers don’t use precedence rules and parenthesis because they are COSTLY. They just use a left to right mechanism.

Lets say, infix is used and compilers don’t use precedence and parenthesis 1+2*3-1 now without precedence rules and using left to right, answer is 8.
But the correct answer is 6

So instead of using precedence rules and parenthesis, compilers  use the infix expression’s equivalent postfix expression.
Remember I said STACK is used to evaluate postfix operations? Lets see how

Algorithm for evaluating POSTFIX

  1. Maintain a stack and scan the postfix expression from left to right
  2. If the element is a number, push it into the stack
  3. If the element is an operator O, pop twice and get A and B respectively.
  4. Calculate B O A and push it back to the stack
  5. When the expression is ended, the number in the stack is the final answer

Example showing how to solve 10 2 8 * + 3 – using stack

We have the postfix expression: 10 2 8 * + 3 –

  1. Push 10
  2. Push 2
  3. Push 8
  4. Now operator *, so pop 2 operands from TOS and operate. 8*2, so T.O.S => 16
  5. Now operator +, so pop two operands 16 and 10 and operate .So we have T.O.S => 26
  6. Now push 3
  7. Operator – is met, so pop two operands 26 and 3, operate
    26-3 =23

STRANGE?

Well this is how computers work, in strange ways. But certainly in efficient ways.

Thank you for reading through and I hope you got some idea about stack and postfix expression. If anything here is out of place or if you did not get anything mentioned here, do let me know. Keep Learning.