Implement the following infix-to-postfix algorithm in C++. Make sure you understand the algorithm by going through a few examples with pencil and paper, only then start implementing it. Note the indentation implies the beginning and end of a block of code.

Determine the time complexity of the algorithm. This algorithm can be modified by adding one more stack to evaluate expressions. Think about how you would do that. Hand in a printout of your program and a typescript of sample runs.

// An algorithm for infix to postfix expression conversion. //Forexample, a+b-c translatesto ab+c-

// a+b*c translatesto abc*+

// (a+2)/(5-d) goesto a2+5d-/

// a+((b-c)*d)/e to abc-d*e/+ // Valid operands are single digits and characters: 0-9 a-z A-Z // Valid operators are: + - * / ( )

// Highest precedence: * / // Lowest precedence: + - // ( has lowest precedence on the stack and highest precedence outside of stack. // ) never goes on stack. // Bottom of the stack has the lowest precedence than any operator. // Use a prec() function to compare the precedence of the operators based on the above rules. // Note there is little error checking in the algorithm! 

while there is more input if input is an operand 

else

print input

if input is '(' // '(' has lowest precedence in the stack, highest outside push input on stack 

else if input is ')' while stack is not empty and top of stack is not '(' 

 print top of stack 

 pop stack if stack is not empty 

 pop stack else error // no matching '(' 

else if input is '*' or '/' or '+' or '-' if stack is empty or prec(top of stack) < prec(input) // bottom of stack has lower precedence than everything 

 push input on stack else // prec(top of stack) >= prec(input) 

 while stack is not empty and prec(top of stack) >= prec(input) print top of stack 

 pop stack push input on stack 

 else check for errors while stack is not empty 

 print top of stack pop stack