The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+17 votes

Assume that the operators $+, -, \times$ are left associative and $^\hat{}$ is right associative. The order of precedence (from highest to lowest) is $^\hat{}, \times, +, -$. The postfix expression corresponding to the infix expression $a+ b \times c-d^\hat{}e^\hat{}f$ is

  1. $abc\times+def^\hat{}{} ^\hat{}-$

  2. $abc\times+de^\hat{}f^\hat{}-$

  3. $ab+c\times d-e^\hat{}f^\hat{}$

  4. $-+a\times bc^\hat{}{}^\hat{}def$


asked in DS by Veteran (69k points)
edited by | 2.4k views

3 Answers

+29 votes
Best answer

Ans : (A)

Here is the procedure first :
Scan Infix Expression from left to right whenever you see operand just print it.
But In case of operator
if(stack is empty) then push it.
if(precedence(tos) $<$ precedence(current operator) ) push it.
else if (precedence(tos) $>$ precedence(current operator) ) pop and print.
else if (precedence(tos) $==$  precedence(current operator) ) then check for associativity.In case Operators are Left to right then pop and print it otherwise push the current operator (Right to Left Associativity)
And once you have scanned infix expression completely. Make sure pop all the element and print it in same order.

Here the infix expression is $a+b \times c−d ^\hat{} e ^\hat{}f$
$a$ : print it
$+$ : push into the Operator Stack
$b$ : print it
$*$ : its having higher precedence than $+$ then push into Operator Stack
$c$ : print it
$'-'$ : $'-'$ is having less precedence than $'*'$ so pop from operator stack and print $'*'$.after this stack will be having $'+'$ on top.which is having same precedence as $'-'$ but both are left to right associative then just pop $+$ and print it. Now stack is empty. Push $'-'$ to it.
$d$ : print it
'$^\hat{}$' : top of the stack is having $'-'$ which has lower precedence than '$^\hat{}$' so simply push '$^\hat{}$' into stack
$e$ : print it.
'$^\hat{}$' : Now top of the stack is '$^\hat{}$' and has same precedence so associativity will come to picture. Since '$^\hat{}$' is right associative as given in question. So '$^\hat{}$' will be pushed.
$f$ : print it.

Now we have scanned entire infix expression.Now pop the stack untill it becomes empty.This way you will get $a b c * + d e f ^\hat{} \ ^\hat{}-$

answered by Junior (519 points)
edited by
+4 votes

Use Bracket according to precedance 

^  - Precedance from Right to Left and others left to right

((a + (b * c )) - (d ^ (e ^ f))) then solve it 

answered by Veteran (11.2k points)
0 votes
answer - A
answered by Boss (9.3k points)
One easy way is:

1. Add brackets as per precedence and order of evaluation

2. Move operators to the right of immediate paranthesis for postfix.


Here, after adding brackets,


Now after moving operators to immediate right paranthesis, we obtain,


Sorry for typos.

Related questions

+13 votes
6 answers
asked Sep 19, 2014 in DS by Kathleen Veteran (69k points) | 2.4k views
+5 votes
2 answers
asked Jun 10, 2016 in DS by jothee Veteran (112k points) | 2.9k views
+12 votes
5 answers
asked Sep 19, 2014 in DS by Kathleen Veteran (69k points) | 2.2k views

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

34,266 questions
40,978 answers
39,885 users