Question 2 [25 Marks Given a C++ program file. Test2_Q2.cpp, which contains a linked list implementation of stack to convert infix expression to postfix expression and to evaluate the postfix expression. The infix expression (8 * (3 + 4) / 2 - 3 * 5) and the definition of the class nodeStack and stack are given in the program file. The variable top in the class stack is a pointer which points to the top node of the stack. The implementation of the method createStack(), isEmpty(), stackTop(), push() and pop () of the class stack are also given in the Test2_Q2.cpp. You must not change any line of code regarding the definition of the class nodeStack and stack. The method isoperator() is used to check if a character is an operator or not, whereas the method precedence () is used to determine the precedence of the operator Complete the implementation of main function by appending the appropriate lines of code at the space provided in Test2_Q2.cpp to accomplish each of the following tasks: Conversion of infix expression to postfix expression using stack: Task 1: If a left parentheses is encountered, push it into a stack (2 marks) Task 2: If an operator is encountered, then (a) Repeatedly pop from stack and add to postfix expression each operator on the top of stack, which has the same precedence as or higher precedence than the encountered operator. (6) Add the encountered operator to stack. (8 marks) Task 3: If a right parentheses is encountered then (a) Repeatedly pop from stack and add to postfix expression each operator on the top of stack until a left parentheses is encountered. (6) Remove the left parentheses. 5 marks) Evaluation of postfix expression using stack: Task 4: If an operator is encountered then (a) Pon the first two onerands in start- Evaluation of postfix expression using stack: Task 4: If an operator is encountered, then (a) Pop the first two operands in stack 4 (b) Evaluate the encountered operator using both operands. c) Push the result of the evaluation to stack (10 marks) Figure 7 and 8 show table of converting infix to postfix and table of evaluating postfix expression Figure 9 shows the expected output when the program runs. Postfix Stack # # #* #* Infix 8*(3+4)/2-3*5 * (3+4)2-345 (3+4)/2-3*5 3+4)/2-3*5 +4)2-3*5 4)/2-3*5 7/2-3*5 12-3*5 2-3*5 -385 3*5 *5 #*(+ #*(+ ######## 8 8 8 83 83 834 834+ 834+* 834+*2 834+*21 834+*2/3 834+*2/3 834+*2/35 834+*2/35* 834+*2/35 Figure 7: Table of converting infix to postfix #* #*( #*(+ #*(+ 3+4)/2-3*5 +4)2-3*5 4)/2-3*5 1/2-35 12-3*5 2-3*5 -3*5 3*5 *5 5 8 83 83 834 834+ 834+* 834+*2 834+*2/ 834+*2/3 834+*2/3 834+*2/35 834+*2/35* 834+*2/35%. Figure 7: Table of converting infix to postfix Character Operator Operand 1 Operand 2 Result 8 3 4 Postfix 834+*2/35*. 34+*2/35*. 4+*2/35%. +*2/35* *2/35*- 2/35*. /35. 35*. 5*. Stack 8 83 834 87 56 562 + 3 8 7 56 * 7 2 56 28 28 2 1 3 5 283 2835 2815 13 5 15 3 28 15 13 Figure 8: Table of evaluating postfix expression 5 Convert infix to postfix Infix: 8 (3+2)/2-3-5 Postfix: 834-*2/35*- Evaluating postfix expression Postfix expression: 824+*2/25 - Result = 13 Figure 9: The output of the program
