//////////////////////////////////////////////////////////////////////////////// // Faculty of Computing, Universiti Teknologi Malaysia // SCSJ2013- Data Structures and Algorithms // Semester 1, 2018/2019 // Lab Test - Question 2 Stack (25 marks) ////////////////////////////////////////////////////////////////////////////////

#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 [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