edited by
8,546 views
28 votes
28 votes

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

  1. An operator stack
  2. An operand stack
  3. An operand stack and an operator stack
  4. A parse tree
edited by

3 Answers

Best answer
7 votes
7 votes

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.

selected by
45 votes
45 votes

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.

edited by
27 votes
27 votes
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.
Answer:

Related questions

4 votes
4 votes
0 answers
2
33 votes
33 votes
4 answers
3
2 votes
2 votes
2 answers
4
go_editor asked Jul 4, 2016
3,752 views
The postfix expression AB + CD -* can be evaluated using astacktreequeuelinked list