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

Kathleen
asked
in Compiler Design
Sep 16, 2014

5,745 views
## 3 Answers

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.

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.

### 17 Comments

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?

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

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.

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.