C++ -- Data Structures

The stack class needed:

#include  #include  using namespace std; template class Stack { public: Stack();//creates the stack bool isempty(); // returns true if the stack is empty T gettop();//returns the front of the list void push(T entry);//add entry to the top of the stack void pop();//remove the top of the stack private: vector stack; }; // Stack template Stack::Stack() { } template bool Stack::isempty() { if (stack.size() == 0) return true; else return false; } template T Stack::gettop() { return stack[stack.size()-1]; } template void Stack::push(T entry) { stack.push_back(entry); } template void Stack::pop() { stack.pop_back(); }

2. Consider the following algorithm X is an arithmetic expression written in infix notation This algorithm finds the equivalent postfix expression Y 1. Push [onto Stack, and add] to the end of X. 2. Scan X from left to right and repeat Step 3 to 6 for each element of X untl the Stack is empty 3. If (is encountered, push it onto Stack. 4. If an operator is encountered, then: 1. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) which has the same precedence as or higher precedence than operator 2. Add operator to Stack. 5. If a) or] is encountered, then: 1. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) until a respective (or [ is encountered 2. Remove the ( or [ from Stack. 6. If an operand is encountered, add it to Y 7. END 1. First make sure you understand the algorithm by converting the string (A+B)*CD (J+D) to postfix. 2. Now write a function infix-to-postfix that accepts an infix expression (string) and returns a string containing the expression in postfix. You will need the Stack class which is here 3. Test your program on the string (A+B)*C-(D (J+D) by writing a main program