9,784 views
28 votes
28 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

6 Answers

Best answer
37 votes
37 votes
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
1 votes
1 votes

we need only one stack....(here input to stack is POSTFIX expression)

the process is like this ....when we see the operands then we simply push them into stack.... and when operator comes/read by algorithm we simply pop operands from stack....evaluate them and again push the result into stack..

if current operator needs 2 operands like +,/,-....we pop 2 operand from stack evaluate them and push result back into stack....

like

532*+

here we read 5,3,2 we push it into stack...now we read * hence pop 2 operands ...we pop 2,3 ...now perform the operation 

2*3=6....now 6 is push into stack..

now we read +..so pop 2 operands that is 6,5..and do addition we get the result =11...

SO WE NEED ALWAYS 1 STACK TO SOLVE IT..

1 votes
1 votes

Generally infix expressions are harder to evaluate in computers

So, one way is to convert into postfix expression and evaluate it.

So, we can convert into and evaluate a postfix expression by using 2 stacks

one is operator stack and other is operand stack. (algorithm is given below)

So, I think option B (2 stacks) 

1. While there are still tokens to be read in,
   1.1 Get the next token.
   1.2 If the token is:
       1.2.1 A number: push it onto the value stack.
       1.2.2 A variable: get its value, and push onto the value stack.
       1.2.3 A left parenthesis: push it onto the operator stack.
       1.2.4 A right parenthesis:
         1 While the thing on top of the operator stack is not a 
           left parenthesis,
             1 Pop the operator from the operator stack.
             2 Pop the value stack twice, getting two operands.
             3 Apply the operator to the operands, in the correct order.
             4 Push the result onto the value stack.
         2 Pop the left parenthesis from the operator stack, and discard it.
       1.2.5 An operator (call it thisOp):
         1 While the operator stack is not empty, and the top thing on the
           operator stack has the same or greater precedence as thisOp,
           1 Pop the operator from the operator stack.
           2 Pop the value stack twice, getting two operands.
           3 Apply the operator to the operands, in the correct order.
           4 Push the result onto the value stack.
         2 Push thisOp onto the operator stack.
2. While the operator stack is not empty,
    1 Pop the operator from the operator stack.
    2 Pop the value stack twice, getting two operands.
    3 Apply the operator to the operands, in the correct order.
    4 Push the result onto the value stack.
3. At this point the operator stack should be empty, and the value
   stack should have only one value in it, which is the final result.
edited by
1 votes
1 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.
Answer:

Related questions

29 votes
29 votes
3 answers
1
Kathleen asked Sep 15, 2014
11,391 views
The performance of a pipelined processor suffers if:the pipeline stages have different delaysconsecutive instructions are dependent on each otherthe pipeline stages share...
28 votes
28 votes
4 answers
3
Kathleen asked Sep 15, 2014
6,795 views
Dynamic linking can cause security concerns becauseSecurity is dynamicThe path for searching dynamic libraries is not known till runtimeLinking is insecureCryptographic p...
22 votes
22 votes
5 answers
4
Kathleen asked Sep 15, 2014
10,447 views
Four fair coins are tossed simultaneously. The probability that at least one head and one tail turn up is$\frac{1}{16}$$\frac{1}{8}$$\frac{7}{8}$$\frac{15}{16}$