3 votes 3 votes Time required to evaluate a. prefix, b. infix, c. postfix_____O(n) ? for expression evaluation (infix, prefix, postfix) operand stack needed____True? for conversion from one to another notation operator stack needed_____True? time required for conversion from infix to postfix___O(n) // infix to prefix___? // prefix to {infix and postfix}___? postfix to { prefix and infix }__? which among { infix, prefix, postfix } require more scan__? PS: i googled for all this but not found anthing exact.. DS data-structures infix-prefix + – 2018 asked Nov 26, 2016 2018 2.9k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
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 Prajwal Bhat answered Nov 26, 2016 edited Nov 26, 2016 by Prajwal Bhat Prajwal Bhat comment Share Follow See all 12 Comments See all 12 12 Comments reply Show 9 previous comments Prajwal Bhat commented Nov 26, 2016 reply Follow Share @Hradesh I have added everything to answer itself check it. 0 votes 0 votes Hradesh patel commented Nov 26, 2016 reply Follow Share @Prajwal thks br0 1 votes 1 votes rajatmyname commented Jun 17, 2018 reply Follow Share In the 3rd point it is written that we always need an operator stack for conversion from one expression to another but while converting infix to prefix we don't need operator stack. Please explain this point in detail 0 votes 0 votes Please log in or register to add a comment.