#include #include #include using namespace std;

class Node{ private: int data; Node* nextNodePtr; public: Node(){} void setData(int d){ data = d; } int getData(){ return data; } void setNextNodePtr(Node* nodePtr){ nextNodePtr = nodePtr; } Node* getNextNodePtr(){ return nextNodePtr; } };

class Stack{

private: Node *headPtr; public: Stack(){ headPtr = new Node(); headPtr->setNextNodePtr(0); } Node* getHeadPtr(){ return headPtr; } bool isEmpty(){ if (headPtr->getNextNodePtr() == 0) return true; return false; } void push(int data){ Node* currentNodePtr = headPtr->getNextNodePtr(); Node* prevNodePtr = headPtr; while (currentNodePtr != 0){ prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr->getNextNodePtr(); } Node* newNodePtr = new Node(); newNodePtr->setData(data); newNodePtr->setNextNodePtr(0); prevNodePtr->setNextNodePtr(newNodePtr); } int peek(){ Node* currentNodePtr = headPtr->getNextNodePtr(); Node* prevNodePtr = headPtr; if (currentNodePtr == 0){ return -1000000; // stack is empty } while (currentNodePtr->getNextNodePtr() != 0) currentNodePtr = currentNodePtr->getNextNodePtr(); return currentNodePtr->getData(); }

int pop(){ Node* currentNodePtr = headPtr->getNextNodePtr(); Node* prevNodePtr = headPtr; if (currentNodePtr == 0){ return -1000000; // stack is empty } while (currentNodePtr->getNextNodePtr() != 0){ prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr->getNextNodePtr();

} prevNodePtr->setNextNodePtr(0); return currentNodePtr->getData(); }

};

int main(){

Stack stack;

string expression; cout 2 - 35 pts) You are given the code (including the main function) for evaluating an expression in post-fix format using Stack. Your task is to modify the code in the main function to input an expression in pre-fix format, reverse it (as discussed in class) and then evaluate the value of the reversed expression (scanned from left to right) using Stack. You test your code with an expression string in pre-fix format that comprises of all the four operators (at least once) in a randomly chosen order with randomly chosen values in the range1 to 9. For example, a sample expression string (pre-fix notation) could be input as+,1,5,2,3, 4,8 for the expression (infix-notation) 5/2 3+4-8. You need to submit the following for this question: (1) The complete code (including the modification to evaluate an expression in pre-fix format) of the Stack class, Node class and the main function. (2) Screenshot of the execution of the code for a sample pre-fix expression, like the one given above