Question

Use the algorithm below to evaluate the following infix expression: a) a + 3 * 4 – 9 b) ( 2 + 6 ) / ( 3 – 5 ) . Algorithm

WRITE STEP BY STEP

Scan the characters in the infix expression. While there are characters left in the infix expression: Check the next character in the expression.

1. If the next character is operand, remove it from the expression and push it onto the operand stack.

2. If the next character is the operator ‘^’, remove it from the expression and push it onto the operator stack.

3. If the next character is one of the operators ‘+’, ‘-‘, ‘*’ and ‘/’: check its precedence.

3.1. While the operator stack is not empty and the operator in the expression has a lower or same precedence than that at the top of the operator stack: - Pop an item from the operator stack. If it is ‘(‘, discard it, otherwise place the operator in the ‘Calculator’. - Pop two operands from the operand stack and place them in the ‘Calculator’. Note that the first popped value will be the second operand in the ‘Calculator’. - Push the result from the ‘Calculator’ onto the operand stack.

3.2. Remove the operator from the expression and push it onto the operator stack.

4. If the next character is ‘(‘, remove it from the expression and push it onto the operator stack. Note: when comparing the precedence of operators in the operator stack, a ‘(‘ has a lower precedence than any operator.

5. If the next character is ‘)‘, remove x it from the expression and discard it, and repeat the steps in 3.1 until ‘(‘ pops. Discard ‘(‘. When there are no more characters in the expression string, check the operator stack. While the operator stack is not empty: - Pop an item from the operator stack. - If it is ‘(‘, discard it, - Otherwise: - Place the operator in the ‘Calculator’. - Pop two operands from the operand stack and place them in the ‘Calculator’. Note that the first popped value will be the second operand in the ‘Calculator’. - Push the result from the ‘Calculator’ onto the operand stack. Upon completion, there should be only one value left in the stack and this is the value of the expression

Answer 1

a + 3 * 4 – 9

# indicate to empty

Symbol	Operand stack	Operator Stack	Pop operator	Operand 1	Operand 2	Calculate
a	a	#
+	a	#, +
3	a,3	#,+
*	a,3	#,+,*
4	a,3,4	#,+,*
-	a,	#,+	*	3	4	34*
	a, 34*	#	+	a	34*	a34*+
	a34*+	#, -
9	a34*+,9	#, -	-	a34*+	9	a34*+9-
	a34*+9-	#

( 2 + 6 ) / ( 3 – 5 )

# indicate to empty

Symbol	Operand stack	Operator Stack	Pop operator	Operand 1	Operand 2	Calculate
(		#,(
2	2	#, (
+	2	#,( ,+
6	2,6	#,(, +
)		#,(,+	+	2	6	26+
	26+	#
/	26+	#,/
(	26+	#,/,(
3	26+, 3	#, / , (
-	26+, 3	#, / , (, -
5	26+, 3,5	#, / , (, -
)	26+	#, /	-	3	5	35-
	26+,35-	#, /
		#	/	26+	34-	26+34-/
	26+34-/

---------------------------------------------------------------------------------------------

If you have any query, please feel free to ask.

Thanks a lot.