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

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

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

+8

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?

+9

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

0

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

didn't you read the comments before commenting ?

+1

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.

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,833 questions

57,729 answers

199,453 comments

107,861 users