GATE CSE 1995 | Question: 2.21

Question

The postfix expression for the infix expression $A+B*(C+D)/F+D*E$ is:

• A. $AB + CD + *F/D +E*$

• B. $ABCD + *F/DE* ++$

• C. $A * B + CD/F *DE ++$

• D. $A + *BCD/F* DE ++$

Comments

The correct ans is  ABCD + * F/+DE * +
No option matches...
By default arithmatic operators are left associative.

If it is right associative, then they should mention it. So qsn/option  should be edited then only ans is B

---

@Ahwan getting same answer as yours

---

I am getting answer as ABCD+/F*+DE*+. I have given division higher priority than multiplication as per bodmas rule,plus no associativity and precedence rule is specified.

---

@Arjun or anyone with edit privileges, please edit the options.

---

@Ahwan

Not all are left-associative.

---

I don't know by the people here are talking about $\mathbf{By-Default}$ thing. 

According to me $\underline{\text{associativity is a rule}}$ and the operators are either $\mathbf{Left\;Associative}$ or $\mathbf{Right\;Associative}$.

@Satbir

@Verma Ashish

@techbd123

@ankitgupta.1729

 

Can you people please verify the correctness of this statement.

---

i've done mistake when division (/) operator comes then in the stack there're { +,* } where TOP is * (mul op) and i've popped multiplication 

(F) came and ignored 

when + came on top of stack it's *( mul) and as it has higher priority so popped * but here done the mistake that i've also popped Plus(+) also as same priority operator .

And this is the mistake and solution is that we should not pop two operators at the same time.And if there's any mistake in my understanding then please rectify it.

---

guys the options are worng in my opinion. you cant just change the associativity. may be misprinted

---

All options are wrong

(A B C D + * F / + D E * +) is the right postfix expression. Option B is  misprinted version of it.

---

yes u are correct @Honey badger

---

if asked prefix expression then  ++A/*B+CDF*DE

---

yes i agree

 

Answer 1

Thus before considering + which has the least priority, we get  $A + (BCD+*F/) + (DE*)$

Now if we assume left associativity for $+$ (default), we get $ABCD+*F/ + DE*+$ but this is not among the options.

So, considering right associativity for $+$ we get $ABCD+*F/DE*++$

Correct Answer: $B$

Comments

At a time how many operators can be there in stack ?

The reason for this question is just take this scenario that stack contains {+,*} and top of stack is mul (*) and then again + operator came then how do we pop out both operators from stack and push +

or

do we only pop * operator and push + so that stack contains {+,+}

---

@Surya Pratap Singh This is because you will be arriving at           A       +        BCD+*F/          +         DE*

now the associativity is being taken as right to left for "+"

so  A       +        BCD+*F/          +         DE*

=  A       +        BCD+*F/DE*+

= ABCD+*F/DE*++

---

yea through out que we followed left associativity, which infact is the actual associativity for infix, lets now at end try right also just to match option.

Answer 2

it is 4 level stak and postfix is: ABCD+*F/+DE*+
 

Comments

No, it will go upto a maximum level of 4 => {+, *, (, +}, then we will encounter ')', and '+' will be popped and printed and '(' will also be popped off from the stack, and the stack will never reach a level of 4 again.

---

How to find levels

---

This might be useful..

https://www.geeksforgeeks.org/stack-set-2-infix-to-postfix/

---

@Arjun sir

Please edit the answer.

Answer 3

Infix to Postfix using Stack :

If (  ‘(‘  ) 

  push in stack 


If (  ‘)‘  ) 

  pop until left parenthesis is popped  
 

If ( operator ) 

    1. Lower priority (w.r.t to Stack Top ) is in input then pop 
    2. Higher priority input in input then push
    3. Same priority then pop


If ( operand ) 

     ignore 

 

Now using the above algorithm , let us evaluate   A + B * (C + D) / F + D * E  :

 

Steps	Stack Element	Output
Step 1 : Ignore A (as it’s operand )		A
Step 2: Since Stack is empty push ‘+’	+	A
Step 3: Ignore B (as it’s operand )		AB
Step 4 : * has Higher priority than + so push	* +	AB
Step 5 : push ‘ ( ‘ in stack	( * +	AB
Step 6 : Ignore C (as it’s operand )	( * +	ABC
Step 7 : push ‘+’ in stack	+ ( * +	ABC
Step 8 : Ignore D (as it’s operand )	+ ( * +	ABCD
Step 9 : pop until left parenthesis is popped	*+	ABCD+
Step 10 : ‘/’  has same priority as ‘*’  , so pop ‘*’ and push ‘/’  into stack as ‘/’ has higher priority than ‘+’	/+	ABCD+*
Step 11 : Ignore F (as it’s operand )	/+	ABCD+*F
Step 12 : ‘+’ has lower priority than ‘/’ , so pop ’/’ and push ’+’	++	ABCD+*F/
Step 13 : Ignore D (as it’s operand )	++	ABCD+*F/D
Step 14 : push ‘*’ as it has higher preceedence than ‘+’	*++	ABCD+*F/D
Step 15 : Ignore E (as it’s operand )	*++	ABCD+*F/DE
Step 16 : We have ‘*’ , ‘+’ , ‘+’ in the stack . Just empty the stack		ABCD+*F/DE*++

 

 

Correct Ans : Option ( B )  ABCD+*F/DE*++

 

 

 

 

 

 

 

 

 

 

 

 

Comments

Thanks! Definitely It’s the best answer.

---

how in step 11, two ++ exist together? nowhere it is mentioned + operator is right associative.

---

since options are not matching,we assume it to be right associative.

That's the only thing we can do.

Atleast they should have mentioned it in the question to assume + to be right associative but they didn't mentioned causing ambiguity.

Answer 4

$Top\ of\ stack$	$Next$
$Low\ priority$	$High\ priority$	$PUSH$
$High\ priority$	$Low\ priority$	$POP$
$Same\ priority\ (Left-to-Right\ associativity)$		$POP$
$Same\ priority\ (Right-to-Left\ associativity)$		$PUSH$

According to this answer should be : $ABCD+*F/+DE*+$

We are getting this answer because in the operator stack when $+$ is on the top of the stack and the next symbol is $+$ we are doing a pop operation which has to be done.

But in order to get one of the options as an answer we need to change the associativity of $+$ and when $+$ is on the top of the stack and the next symbol is $+$ we will do a push operation and hence we will get an expression :  $ABCD+*F/DE*++$  which is leading to option $B$

Answer 5

It will be B.

It will use a maximum 4 level stack.

Comments

But $+$ is left associative , So postfix should be  $$\matrix{ A & B & C & D & + & * & F & / & + & D & E & * &+}$$

---

Yes this should be the correct answer.

Either options are wrong or it is miss typed ?

---

yes , this will be correct ans. Now, in GATE question such error will not be found.

---

abhi doosri galtiyaan karte hai ambigous questions dene ki

Answer 6

B is the answer if you want to verify just push the symbols into the stack whenever you get an operator just pop last two symbols and operate them with the oprator and then check with the infix.You will get your answer.