GATE CSE 2002 | Question: 2.19

Question

To evaluate an expression without any embedded function calls

• A. One stack is enough
• B. Two stacks are needed
• C. As many stacks as the height of the expression tree are needed
• D. A Turing machine is needed in the general case

Comments

only one stack

---

https://gateoverflow.in/275510/nielit-2018-54

---

What is context of function call?

Answer 1

Expression without any calls in it $\implies 1+2\ast3-4$

Expression with embedded calls $\implies 1 + \text{fun}1(a,b,c) \ast  \text{fun}2(3.4,58) - \text{fun}3(x,yz)$;

First we can convert Infix to Postfix using single stack (Using it as operator stack)

Then we can evaluate that expression using Single stack.

Correct Answer: A.

Comments

how will you multiply using single stack ?

---

Does answer makes more sense now ? Amar ? I updated it .

---

what u think , embedded calls mean here ? I think, it mean like mul(a,b)   , add(5,6) .. mean operations itself..

---

Expression without any calls in it => 1+2*3-4

Expression with embedded calls => 1 + fun1(a,b,c) *fun2(3.4,58) - fun3(x,yz);

---

Ok, now it makes sense.. :)

And in general , when embedded calls allowed  ?   2 stacks ?

---

Why Turing machine is not needed, a TM can also perform required function i.e it can evaluate the expression  1+2*3-4 also, by Turing Thesis.

Is this the fact that, a stack is used for postfix evaluation of expression and also each function will have there own stack, so option A is correct?

How to decide here, a TM also does the job for us right?

---

What if questions says "WITH EMBEDDED FUNCTION CALLS"?

---

@ rahul sharma 5 : In that case Two stacks $First \ one \ works \ as \ Operator  \ stack$ and second one will be used to resolve function calls : 
Example : main(){                                     

int x=3,y=4,result;

result=addvalues(3,4)

}

addvalues(int v1,int v2)

return v1+v2;

functions                                          |  Operator    \

addvalues()                                        |    4              \

main()                                                 |3                 \                        7

---

Hello Anil

It's job of Pushdown automata (PDA) to evaluate an expression.

When you can do it using PDA. So in general case PDA is used not TM.

---

@saxena0612

i did not understand how you built table? In table why there is 4 in addvalues and 3 in main?

---

@Himanshu1

For expression with embedded function calls..how many stacks required ??

2 or 1

---

@jatin khachane 1

already saxena0612, explained it... but still you are asking same,

didn't you read the comments before commenting ?

---

What would be answer "with embedded function calls"

---

@anchitjindal just read all the comments you will get what you want

---

any expression can be converted into Postfix or Prefix form.

Prefix and postfix evaluation can be done using a single stack.

For example : Expression ’10 2 8 * + 3 -‘ is given.
PUSH 10 in the stack.
PUSH 2 in the stack.
PUSH 8 in the stack.
When operator ‘*’ occurs, POP 2 and 8 from the stack.
PUSH 2 * 8 = 16 in the stack.
When operator ‘+’ occurs, POP 16 and 10 from the stack.
PUSH 10 * 16 = 26 in the stack.
PUSH 3 in the stack.
When operator ‘-‘ occurs, POP 26 and 3 from the stack.
PUSH 26 – 3 = 23 in the stack.
So, 23 is the answer obtained using single stack.

 
Thus, option (A) is correct.

---

$2$ stacks not needed?

---

one stack is enough..!

Answer 2

we need only one stack....(here input to stack is POSTFIX expression)

the process is like this ....when we see the operands then we simply push them into stack.... and when operator comes/read by algorithm we simply pop operands from stack....evaluate them and again push the result into stack..

if current operator needs 2 operands like +,/,-....we pop 2 operand from stack evaluate them and push result back into stack....

like

532*+

here we read 5,3,2 we push it into stack...now we read * hence pop 2 operands ...we pop 2,3 ...now perform the operation 

2*3=6....now 6 is push into stack..

now we read +..so pop 2 operands that is 6,5..and do addition we get the result =11...

SO WE NEED ALWAYS 1 STACK TO SOLVE IT..

Comments

In question they have given arithmetic expression, So how can we directly give postfix expression?

My doubt is we have to at a time convert into postfix and evaluate it using 2 stacks( operatoe and operand)?

Please explain.

---

in that way yes 2 are needed...one for conversion and one for evaluation .....but question just says evaluation so i write answer as 1 ....question doesnt specify ...how we have given input...

Answer 3

Generally infix expressions are harder to evaluate in computers

So, one way is to convert into postfix expression and evaluate it.

So, we can convert into and evaluate a postfix expression by using 2 stacks

one is operator stack and other is operand stack. (algorithm is given below)

So, I think option B (2 stacks) 

1. While there are still tokens to be read in,
   1.1 Get the next token.
   1.2 If the token is:
       1.2.1 A number: push it onto the value stack.
       1.2.2 A variable: get its value, and push onto the value stack.
       1.2.3 A left parenthesis: push it onto the operator stack.
       1.2.4 A right parenthesis:
         1 While the thing on top of the operator stack is not a 
           left parenthesis,
             1 Pop the operator from the operator stack.
             2 Pop the value stack twice, getting two operands.
             3 Apply the operator to the operands, in the correct order.
             4 Push the result onto the value stack.
         2 Pop the left parenthesis from the operator stack, and discard it.
       1.2.5 An operator (call it thisOp):
         1 While the operator stack is not empty, and the top thing on the
           operator stack has the same or greater precedence as thisOp,
           1 Pop the operator from the operator stack.
           2 Pop the value stack twice, getting two operands.
           3 Apply the operator to the operands, in the correct order.
           4 Push the result onto the value stack.
         2 Push thisOp onto the operator stack.
2. While the operator stack is not empty,
    1 Pop the operator from the operator stack.
    2 Pop the value stack twice, getting two operands.
    3 Apply the operator to the operands, in the correct order.
    4 Push the result onto the value stack.
3. At this point the operator stack should be empty, and the value
   stack should have only one value in it, which is the final result.

Comments

video lecture on postfix expression evaluation using stack.

https://www.youtube.com/watch?v=rnNsrbUIPIY&t=14s

Answer 4

ans a)

Comments

postfix .is done by one stack. computer like postfix evalution.. .so ans is (a)...