in Compiler Design
25 votes

To evaluate an expression without any embedded function calls

  1. One stack is enough
  2. Two stacks are needed
  3. As many stacks as the height of the expression tree are needed
  4. A Turing machine is needed in the general case
in Compiler Design


In case of with embedded function calls, we need stack of size >=2, not exactly two, bcoz the functions can be recursive also.

Subscribe to GO Classes for GATE CSE 2022

3 Answers

30 votes
Best answer
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.
edited by


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;



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.


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



For expression with embedded function 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..!
0 votes
ans a)

1 comment

postfix .is done by one stack. computer like postfix evalution.. .so ans is (a)...
0 votes
To evaluate an expression without any embedded function calls we just need one stack if expression is infix stack will be used to convert it into post fix and then same stack can be used in its evaluation.

To evaluate an expression with any embedded function calls we need atleast two stack 1 to evaluate expression and other to keep record of function calls and related stuff.

Option (A)

correct me if I am wrong.

Related questions