#Test series

Question

Evaluate the given prefix expression,And find the result the of the expression?
Say +-*+ABCD*AB ,Where A=4,B=3,C=2,D=5.

Answer is 3 or 21??

Comments

@himgta

what is the problem you are facing, while evaluating?

---

@Shaik Masthan.. brother I am using stack method....in the subtraction part it should be 5-14 then the answer should be 3...please clarify!

---

the evaluating process of Prefix expression is

+ - * + A B C D * A B

 

come from left to right, until the last operator.

 

1) $+\: -\: *\: +\: A\: B\: \: \: C\: D\: \underbrace{ *\: A\: B}$

 

2) $+\: -\: *\: \underbrace{+\: A\: B\: } \: \: C\: D\: \underbrace{ *\: A\: B}$

 

3) $+\: -\: \underbrace{ *\: \underbrace{+\: A\: B\: } \: \: C}\: D\: \underbrace{ *\: A\: B}$

 

4) $+\: \underbrace{ -\: \underbrace{ *\: \underbrace{+\: A\: B\: } \: \: C}\: D}\: \underbrace{ *\: A\: B}$

 

5) $\underbrace{ +\: \underbrace{ -\: \underbrace{ *\: \underbrace{+\: A\: B\: } \: \: C}\: D}\: \underbrace{ *\: A\: B}}$

---

---

---

if you want to do with stack

 

1) reverse the expression ==> B A * D C B A + * - +

 

2) push the operands, if Binary operator comes , pop two operands from stack apply operator, push the result back into stack. ===> Apply the operator as ( POP₁ of stack operator POP₂ of stack )

 

i) B ==> push the stack

ii) A ==> push the stack

iii) * ===> POP₁ of stack operator POP₂ of stack ===> A * B, let it as X ===> Push X

iv) D ==> push the stack

v) C ==> push the stack

vi) B ==> push the stack

vii) A ==> push the stack

viii) + ===> POP₁ of stack operator POP₂ of stack ===> A + B, let it as P ===> Push P

ix) * ===>  POP₁ of stack operator POP₂ of stack ===> P * C , let it as Q ===> Push Q

x) - ===>  POP₁ of stack operator POP₂ of stack ===> Q - D , let it as R ===> Push R

xi) + ===>  POP₁ of stack operator POP₂ of stack ===> R - X , let it as Y ===> Push Y

---

answer is 3

---

@Magma

How?

---

Shaik Masthan

by using Prefix to Postfix  conversion using stack

---

@Magma

did you read my comment, if it is wrong, tell me where i did mistake.

---

Shaik Masthan

I'm also  apply same approach that  you explained above in the comment section and  I got answer  3 

---

Shaik Masthan  i recheck the answer

answer 3 is correct

---

when we convert prefix to postfix using stack we get

Postfix :  B A * D C B A + * - +

now , and now convert Postfix to infix which is easy

---

@Magma

INFIX expression evaluation needs Priority and Associativity of Operators, that's why we are convert them in to either Prefix/Postfix notations. ( In Prefix/Postfix evaluation doesn't need Priority or Associativity of Operators )

But you are converting Prefix Expression into INFIX again....

---

Shaik Masthan  i Know that it's not easy to parse and evaluate an infix expression without ambiguity , that's why we came with the 2 others way of writing expressions that are parenthesis free and can be passed without ambiguity without take care of any of these operator precedence assosiativity rules ,

 

 now  we have

infix expression : a+b *c (Human readable)

prefix expression :  + a * b c

 postfix expression : abc*+ 

Now , I'm trying to saying that we choose prefix and postfix because it's easy for machines to compute and actually saving some memory that would be used to store parenthesis information   right ?

so, whether you find answer with infix or postfix or prefix ..  all answer is same

when we write code : we use infix notation which is converted into post fix notation which is  good for machines to compute

so if I got answer 3 by converting into infix expression that will be same as machine compute the value  B A * D C B A + * - +  or  +-*+ABCD*AB

what you say ??

---

@Magma

Every thing is correct in your comment.

Can you show step by step how you got 3?

---

@Shaik Masthan

brother I m also getting 3 ....if A is on top of the stack and B is the other element then we have to perform B (operator) A.......not A (operator) B

---

@himgta

Postfix evaluation :- A is on top of the stack and B is the other element then we have to perform B (operator) A.

Prefix evaluation :- A is on top of the stack and B is the other element then we have to perform A (operator) B.

---

ist convert prefix to postfix expression by stack we get :  B A * D C B A + * - +

     

 The ist one which comes out from the stack is is going to be 2nd operand and 2nd one which comes out from stack is going to be ist operand

---

check my previous comment.

you wrongly applied the operator between the operands... it is 14-5 but not 5-14

---

 but Shaik Masthan

I read it from book that , whenever you pop up 2 elements from the stack , ist element is going to be operand 2 and 2nd element is going to be operand 1,

 

---

ok... just check this

2-3 ===> INFIX

2 3 - ===> POSTFIX

- 2 3  ====> PREFIX

Now check your process.... and My process

---

2- 3 = - 1 in  infix

in Postfix  =

push 2 in stack    

push 3 in stack        

2(op₁) - 3(op₂) = -1  [ 3 pop ist from the stack therefore  '3' is 2nd operand and  then ' 2' pop up from the stack therefore 2 is the ist operand ]

both give -1 as result

what's the point ??

---

evaluate prefix with your approach

---

Now i know where I'm wrong

In case of prefix to postfix  (the ist element that you pop up from the stack is the ist operand and 2nd element that you pop up is the 2nd operand)

but In case of  postfix to infix (the ist element that you pop up from the stack is the 2nd operand and 2nd element that you pop from the stack is the ist operand)

Shaik Masthan   thank you

 

---

finally you got it...

those are evaluations, not conversions of prefix to postfix or postfix to infix .

---

hmm you're right

---

@Shaik Masthan

Thank u brother...I got it!

Answer 1

Answer is 21.

+-*+ABCD*AB after converting in infix expression = (A+B)*C-D+A*B

After putting A = 4,B = 3,C = 2,D = 5 in the infix expression

(4+3)*2-5+4*3 = 7*2-5+12 = 14-5+12 = 9+12 = 21

Comments

@Dharmendra Lodhi

misplaced your comment

---

+ - * + A B C D * A B

i) B ==> push the stack

3

ii) A ==> push the stack

4

3

iii) * ===> POP₁ of stack operator POP₂ of stack ===> A * B, let it as X ===> Push X

12

iv) D ==> push the stack

5

12

v) C ==> push the stack

2

5

12

vi) B ==> push the stack

3

2

5

12

vii) A ==> push the stack

4

3

2

5

12

viii) + ===> POP₁ of stack operator POP₂ of stack ===> A + B, let it as P ===> Push P

7

2

5

12

ix) * ===>  POP₁ of stack operator POP₂ of stack ===> P * C , let it as Q ===> Push Q

14

5

12

x) - ===>  POP₁ of stack operator POP₂ of stack ===> Q - D , let it as R ===> Push R

9

12

x) + ===>  POP₁ of stack operator POP₂ of stack ===> 

21

---

brother i said, you misplaced your comment ( i mean, on the question Magma reacted but you post your comment on rtiwari95 answer ). I didn't said you are made mistake.