3.3k views

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
in DS
edited | 3.3k views

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

edited
0

Hello Rajesh

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

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

+3

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)

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.
0

@

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.

+1 vote