#include #include #include

using namespace std;

class nodeStack { public: char data; nodeStack *next; };

class stack { nodeStack *top; public: //To initialize top void createStack() { top = NULL; } //To check either a stack is empty or not bool isEmpty() { return top == NULL; } //To get the item at the top of stack char stackTop() { return top->data; } void push(char); void pop(); };

//To insert a new item into a stack void stack::push(char newItem) { nodeStack *node = new nodeStack; if (node == NULL) cout data = newItem; node->next = top; top = node; } }

//To delete the item from a stack void stack::pop() { nodeStack *delNode; delNode = top; top = delNode->next; delete delNode; }

//Check if a character is an operator bool isOperator(char ch) { if ((ch == '+') || (ch == '*') || (ch == '-') || (ch == '/')) return true; else return false; }

//Determine the precedence of the operator int precedence(char ch) { switch (ch) { case '+': case '-': return 1; case '*': case '/': return 2; } return -1; }

int main() { char ch; stack s; //Stack string infix = "8 * (3 + 4) / 2 - 3 * 5"; //Infix expression string postfix = ""; //Postfix expression cout

//------------------------------------------------- //Task 1: If a left parentheses is encountered, push //it into a stack. (2 marks)

//------------------------------------------------- //Task 2: If an operator is encountered, then //(1) 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 encountered operator. //(2) Add operator to stack. (8 marks)

//------------------------------------------------- //Task 3: If a right parentheses is encountered, then: //(1) Repeatedly pop from stack and add to postfix expression // each operator on the top of stack until a left // parentheses is encountered. //(2) Remove the left parentheses. (5 marks)

} while (s.stackTop() != '#') { postfix += s.stackTop(); s.pop(); } cout

int operand1, operand2, result; s.createStack();

//Evaluate postfix expression for (int i = 0; i

//If operand is encountered, push it onto stack if (isdigit(ch)) s.push(ch - '0'); else { //------------------------------------------------- //Task 4: If an operator is encountered, then //(1) Pop the first two operands in stack //(2) Evaluate the encountered operator using both operands //(3) Push the result of the evaluation to stack. (10 marks)

} }

cout

return 0; }

Question 2 125 Marks Given a C++ program file, Test2_Q2.epp, 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 cach 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 cach operator on the top of stack until a left parentheses is encountered. (6) Remove the left parentheses. (5 marks) Ewaluation of postfix expression using stacki Task 4: If an operator is encountered, then (a) Pop the first two operands in stack. 4 (6) 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-395 *(3+4)/2-35 (3+4)2-315 3+4)2-35 +4)2-35 4)2-35 V2-35 /2-3*5 2-3*5 -35 395 *5 5 #*(+ #*(+ #* 8 8 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 Operand 2 Result Character Operator Operand 1 8 3 4. Postfix 834+2/35 34+*2/35*- 4+*2/35 +*2/35. *2/35- 2/35%. /35*. 35. 5. 3 8 7 56 7 Stack 8 83 834 87 56 562 28 283 2835 2815 13 2 56 28 2 1 3 5 5 15 3 28 15 13 Figure 8: Table of evaluating postfix expression Convert infix to postfix Infix: 8 (3+4)/2-3-5 Postfix: 834+*2/35.- Evaluating postfix expression Postfix expression: 834+*2/35*- Result - 13 Figure 9: The output of the program