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

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+15 votes

To evaluate an expression without any embedded function calls

- One stack is enough
- Two stacks are needed
- As many stacks as the height of the expression tree are needed
- A Turing machine is needed in the general case

+16 votes

Best answer

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);

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

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?

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?

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

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.

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 22
- Job Queries 61
- Projects 13

39,695 questions

46,748 answers

140,526 comments

58,308 users