Question

Show, step by step, how the stack-based algorithm will transform the expression (1 + 2) * (7 − 2) into a postfix expression, and then how a second stack-based algorithm will compute the value of this postfix expression.

Answer 1

Answer:

Token #1 Evaluation

Infix: (1+2)*(7-2)

Since ( is an opening parenthesis, push it to the top of the stack.

Postfix:

Stack:

(

Token #2 Evaluation

Infix: (1+2)*(7-2)

Since 1 is an operand, append it to the postfix expression.

Postfix: 1

Stack:

(

Token #3 Evaluation

Infix: (1+2)*(7-2)

Since + is an operator and has greater precedence than the ( on the top of the stack, push + to the top of the stack.

Postfix: 1

Stack:

+ (

Token #4 Evaluation

Infix: (1+2)*(7-2)

Since 2 is an operand, append it to the postfix expression.

Postfix: 1 2

Stack:

+ (

Token #5 Evaluation

Infix: (1+2)*(7-2)

Since the ) is a closing parenthesis, pop each operator from the stack one at a time and append to the postfix expression. Keep popping from the stack until an opening parenthesis is encountered.

Pop + from the top of the stack and append to the postfix expression.

Postfix: 1 2 +

Stack:

(

Since we are done with the expression inside the current parenthesis, pop the opening parenthesis from the top of the stack and discard.

Postfix: 1 2 +

Stack:

Token #6 Evaluation

Infix: (1+2)*(7-2)

Since the * is an operator and the stack is empty, push the * to the stack.

Postfix: 1 2 +

Stack:

*

Token #7 Evaluation

Infix: (1+2)*(7-2)

Since ( is an opening parenthesis, push it to the top of the stack.

Postfix: 1 2 +

Stack:

( *

Token #8 Evaluation

Infix: (1+2)*(7-2)

Since 7 is an operand, append it to the postfix expression.

Postfix: 1 2 + 7

Stack:

( *

Token #9 Evaluation

Infix: (1+2)*(7-2)

Since - is an operator and has greater precedence than the ( on the top of the stack, push - to the top of the stack.

Postfix: 1 2 + 7

Stack:

- ( *

Token #10 Evaluation

Infix: (1+2)*(7-2)

Since 2 is an operand, append it to the postfix expression.

Postfix: 1 2 + 7 2

Stack:

- ( *

Token #11 Evaluation

Infix: (1+2)*(7-2)

Since the ) is a closing parenthesis, pop each operator from the stack one at a time and append to the postfix expression. Keep popping from the stack until an opening parenthesis is encountered.

Pop - from the top of the stack and append to the postfix expression.

Postfix: 1 2 + 7 2 -

Stack:

( *

Since we are done with the expression inside the current parenthesis, pop the opening parenthesis from the top of the stack and discard.

Postfix: 1 2 + 7 2 -

Stack:

*

All 11 Token Evaluations Completed

Since we are done processing the infix expression, pop the remaining operator from top of the stack and append it to the postfix expression.

Pop * from the stack and append it to the postfix expression.

Postfix: 1 2 + 7 2 - *

Stack:

Final Conversion:

Infix:	(1+2)*(7-2)
to
Postfix:	1 2 + 7 2 - *

//if you have any doubt please comment ....