Question

Question 1:

Given the infix arithmetic expression as follows:

Exp = Z * ((B + C * D) / S + F)

            Where the values of the variables are:

                        Z = 3, B = 6, C = 2, D = 5, S = 4 , F = 21

            Evaluate the expression using a stack. Shows the logical representation of the evaluation process.

..............................................................................

Answer 1

The infix expression: 3 * ((6 + 2 * 5) / 4 + 21)
For this, we need to maintain two stacks, Operator and operand stacks respectively.

Steps:

• If the character is an operand, we will push it to the operand stack.
• If the character is an operator and the operator stack is empty, we will push it to the operator stack.
• If the operator stack isn't empty, we will check:
  1. if input character's precedence is greater than the top of the operand stack, then we will simply push it.
  2. In the other case, we will pop two elements from the operand stack and one operator from the operator stack, perform the required operation and then push the result back to the operand stack.
• If the input character is "(" then we will simply push it to the operator stack.
• If it is ")", then we will pop two operand from operand stack, one operator from the operator stack, perform the operation and store the result to the operand stack. We will keep on doing this until we encounter "(" on top of the operator stack.

For your reference, the order of precedence from the highest to the lowest is shown here:

1. ^
2. * /
3. + -

Character	Action	Operand stack	Operator stack	A little explanation
3	Push it to the operand stack	3
*	Push it to the operator stack	3	*
(	Push it to the operator stack	3	( *
(	Push it to the operator stack	3	( ( *
6	Push it to the operand stack	6 3	( ( *
+	Push it to the operator stack	6 3	+ ( ( *
2	Push it to the operand stack	2 6 3	+ ( ( *
*	Push it to the operator stack	2 6 3	* + ( ( *	As the top of the operator stack is containing the operator with lower precedence, we will just push it to this stack.
5	Push it to the operand stack	5 2 6 3	* + ( ( *
)	Pop two operands from the top of the operand stack and pop one operator from the operator stack and perform the operation until "(" is encountered.	6 3	+ ( ( *	5 and 2 will be popped out and * operation will be performed.
same as above	Do 5 * 2 = 10	6 3	+ ( ( *
same as above	Push 10 to the operand stack	10 6 3	+ ( ( *
same as above	We haven't encountered "(" yet. So we will pop 10 and 6 from operand stack and pop + from operator stack.	3	( ( *
same as above	Do 6 + 10 = 16	3	( ( *
same as above	Push result 16 to the operand stack	16 3	( ( *
same as above	Now that we have encountered "(", top of the operator stack will be popped and then we will scan the next input.	16 3	( *
/	Push it to the operator stack	16 3	/ ( *
4	Push it to the operand stack	4 16 3	/ ( *
+	Pop two elements from the top of operator stack and pop operator from the operator stack	3	( *	Top of operator stack is containing operator with higher precedence so we will perform the mentioned action
same as above	Do 16 / 4 = 4	3	( *
same as above	Push 4 to the operand stack	4 3	( *
same as above	Now push + to the operator stack	4 3	+ ( *	As there is no operator on top of the operator stack, we don't to do any comparison
21	Push it to the operand stack	21 4 3	+ ( *
)	Pop 2 operands from operand stack and one operator from the operator stack	3	( *
same as above	Do 21 + 4 = 25	3	( *
same as above	Push 25 to the operator stack	25 3	( *
)	Pop "(" from the operator stack	25 3	*	Top of the stack is not containing any operator. So we will simply pop "(".
	Pop 2 operands from operand stack and one operator from the operator stack			These are the only things left inside both the stacks
	Do 25 * 3 = 75
	Push 75 to the operand stack			And this is the required answer.