2,915 views
3 votes
3 votes
  1. Time required to evaluate a. prefix, b. infix, c. postfix_____O(n) ?

  2. for expression evaluation (infix, prefix, postfix) operand stack needed____True?
  3. for conversion from one to another notation operator stack needed_____True?
  4. time required for conversion from infix to postfix___O(n)  //  infix to prefix___? // prefix to {infix and postfix}___?               postfix to { prefix and infix }__?
  5. which among { infix, prefix, postfix } require more scan__?
    PS: i googled for all this but not found anthing exact..

1 Answer

Best answer
8 votes
8 votes

1.Time required to evaluate a. prefix O(n)b. infix, O(n)c. postfix O(n).  In worst case.

Why infix O(n)?

It takes O(n) time to convert a infix expression into the postfix expression and only one left to right scan is enough to compute the value of the expression which will take O(n) again.

So totally its O(n)

Ref:http://faculty.cs.niu.edu/~hutchins/csci241/eval.htm

Ref:https://gateoverflow.in/20715/evaluation-of-prefix-expression-takes-o-n-2-true

2.For expression evaluation (infix, prefix, postfix) operand stack needed.TRUE

Ref: http://quiz.geeksforgeeks.org/stack-set-4-evaluation-postfix-expression/

3.For conversion from one to another notation operator stack needed : TRUE

4.Time required for conversion from infix to postfix O(n)

Ref: http://quiz.geeksforgeeks.org/stack-set-2-infix-to-postfix/

5.NO,postfix need one scan but infix and prefix need more scan.

Why Postfix One scan?

For Postfix->Scan the expression from Left to Rightwhile scanning add the operand to operand stack and when you encounter operator pop the top 2 elements and perform operation and push the result onto the stack 

Ref:http://quiz.geeksforgeeks.org/stack-set-4-evaluation-postfix-expression/

Why Prefix 2 scan?

For Prefix-> Follow the same procedure from Right to Left, but till we reach Right most symbol we need one more scan

Why Infix 2 scan?

There is no straight forward method to evaluate Infix expression,The approach is Convert from Infix to postfix and then evaluate postfix expression 

Can Infix done in One Scan?

One more approach is there that is using 2 stacks namely operator stack and operand stack simultaneously.

In this approach Infix evaluation can be done in 1 Scan 

Ref:http://stackoverflow.com/questions/13421424/how-to-evaluate-an-infix-expression-in-just-one-scan-using-stacks

edited by

Related questions

0 votes
0 votes
1 answer
1
akash28 asked Feb 23, 2023
761 views
Convert the following infix expression to postfix and prefixA^B^C^D
2 votes
2 votes
2 answers
2
Amit puri asked Sep 29, 2016
2,696 views
Convert the infix to postfix and prefix expression1) log3! ^log4 *log log 6/7*4!2)log3!^sin 2*cos 3
2 votes
2 votes
3 answers
3
Tushar Shinde asked Jan 28, 2016
3,640 views
Consider the following expression with infix notationA * B - (C + D) * (E / 5) ^ F What is the maximum height of the operator stack during conversion from infix to postfi...
1 votes
1 votes
0 answers
4
PEKKA asked Nov 10, 2016
1,259 views
Conver the following infix to Postfix and Prefix $log ( 3 ! )^ {log4} *log log ((6/7)*4+x)!$$ sin 2x cos (3x+4) $ Please use stack method to solve . Diagram would be app...