Study Sheet

Step by Step

1. 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 until the Stack is empty. (3)If ( is encountered, push it onto Stack. (4)If an operator is encountered, then: 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. Add operator to Stack. (5)If a ) or ] is encountered, then: Repeatedly pop from Stack and add to Y each operator (on the top of Stack) until a respective ( or [ is encountered. Remove the ( or [ from Stack. (6)If an operand is encountered, add it to Y. (7)END.

2. First make sure you understand the algorithm by converting the string (A+B)*C(D/(J+D)) to postfix. (1)Now write a function infix-to-postfix that accepts an infix expression (string) and returns a string containing the expression in postfix. (3)Test your program on the string (A+B)*C-(D/(J+D)) by writing a main program.

You will need the Stack class for step 2 on problem number 2. Here it is below.

#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(); }