The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+16 votes
1.6k views

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
asked in Compiler Design by Veteran (59.6k points) | 1.6k views
0
In case of with embedded function calls, we need stack of size >=2, not exactly two, bcoz the functions can be recursive also.

2 Answers

+16 votes
Best answer
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)$;

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

Then we can evaluate that expression using Single stack.
answered by Boss (43k points)
edited by
0
how will you multiply using single stack ?
0
Does answer makes more sense now ? Amar ? I updated it .
0
what u think , embedded calls mean here ? I think, it mean like mul(a,b)   , add(5,6) .. mean operations itself..
+2
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);
0
Ok, now it makes sense.. :)

And in general , when embedded calls allowed  ?   2 stacks ?
0
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?
0
What if questions says "WITH EMBEDDED FUNCTION CALLS"?
+3

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
0
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.
0

@saxena0612

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

0

@Himanshu1

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

2 or 1

–2 votes
ans a)
answered by Loyal (5.3k points)
0
postfix .is done by one stack. computer like postfix evalution.. .so ans is (a)...
Answer:

Related questions



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

42,658 questions
48,639 answers
156,229 comments
63,953 users