GATE CSE 1997 | Question: 1.7

Question

Which of the following is essential for converting an infix expression to the postfix form efficiently?

• A. An operator stack
• B. An operand stack
• C. An operand stack and an operator stack
• D. A parse tree

Comments

What is meant by operator stack and operand stack?

Answer 1

First of all, this question must be clear in our mind and i.e. Why do we need to convert infix expression postfix expression?

Conventional notation is called infix notation. The arithmetic operators appears between two operands. Parentheses are required to specify the order of the operations. For example: a + (b * c).

 

Post fix notation (also, known as reverse Polish notation) eliminates the need for parentheses.

 

There are no precedence rules to learn, and parenthesis are never needed. Because of this simplicity, some popular hand-held calculators use postfix notation to avoid the complications of multiple sets of parentheses.

 

The operator is placed directly after the two operands it needs to apply. For example: a b c * +

 

You got the answer of Why?

Now, it's time to know what?

 

What is Operand Stack?

When we evaluate a given postfix expression, then we only push the operands into the stack but not any operator. So, the stack used in postfix evaluation called operand stack.
 

What is Operator Stack?

When we convert an infix notation into postfix notation, then we only push the operators into the stack but not any operand. So, stack used in the conversion from infix to postfix is called operator stack.

 

Algorithm to convert Infix into Postfix expression using operator stack:

---

Input is-

if( ‘(‘ )

    push in stack

if( ‘)’ )

     pop until left parenthesis is popped

if(operator)

    1.Lower priority is in input then pop

    2.Higher priority is in input then push

    3.Same r priority is pop except exponent Operator

if(Operand)

    Ignore

---

After conversion of Infix to postfix, we will evaluate postfix expression using Operand Stack only.

Comments

Example: Converting Infix A + B * C - D

\begin{array}{|c|c|c|c|}
\hline
\textbf{Symbol} & \textbf{Operator Stack (Top→Bottom)} & \textbf{Postfix Output} & \textbf{Explanation} \\
\hline
A & empty & A & Operand\; \Rightarrow \text{ add directly to output} \\
\hline
+ & + & A & Stack\; empty\; \Rightarrow \text{ push } + \\
\hline
B & + & A\,B & Operand\; \Rightarrow \text{ add to output} \\
\hline
* & +\,* & A\,B & *\text{ has higher precedence than }+\Rightarrow\text{ push }* \\
\hline
C & +\,* & A\,B\,C & Operand\; \Rightarrow \text{ add to output} \\
\hline
- & - & A\,B\,C\,*\, + & -\text{ has lower precedence than }*\Rightarrow\text{ pop }*,\text{ then }+,\text{ push }- \\
\hline
D & - & A\,B\,C\,*\, +\,D & Operand\; \Rightarrow \text{ add to output} \\
\hline
\text{End} & empty & A\,B\,C\,*\, +\,D\, - & Pop\; remaining\; operator\; (-)\text{ to output} \\
\hline
\end{array}
 

Answer 2

A. An operator stack    // Infix to ( Postfix or Prefix )

B. An operand stack    //Postfix or Prefix Evaluation

C. An operand stack and an operator stack //we never use two stacks

But for Prefix to (Infix or postfix)  OR   Postfix to (Infix or prefix)  We can use a stack where both operator and operand can present simultaneously

D. A parse tree  // Not relevant to this question

Hence, Option A is Answer.

http://condor.depaul.edu/ichu/csc415/notes/notes9/Infix.htm is a good read.

Comments

Hello Rajesh

Are you sure to evaluate prefix expression we need only one stack ?

Attaching source for detailed answer.

https://en.wikibooks.org/wiki/Data_Structures/Stacks_and_Queues

---

Parse tree is not irrelevant, it is relevant. Only thing is it occupies more space than a normal stack implementation. We can get a infix to postfix by doing a post order traversal of a parse tree. As the question is about efficiency 

Space(Parse-Tree) > Space(Stack)

 

---

Right.

They have explicitly mentioed the word ‘efficiently’, that’s why we don’t select this option.

---

But for Prefix to (Infix or postfix)  OR   Postfix to (Infix or prefix)  We can use a stack where both operator and operand can present simultaneously.

we can do the above thing using one stack also rt? then why two stacks are required and how to do it using two stacks? 

pls help in this!!

Answer 3

A.

we use operator stack (only operators are pushed as +, *, (, ), / ) for converting infix to postfix. And we use operand stack( operands such as 5,4,17 etc) for postfix evaluation.

Comments

@Gate Keeda 

Point to be noted: Right parenthesis ')' is pushed on to the stack neither print on to the screen. Left parenthesis '(' always go on to the stack but not printed. 

Answer 4

For better vizualiation