// Chap 6, pp 275 - 280

// *********************************************************
// INFIX TO POSTFIX CONVERSION

// Input:  One legal infix expression, which contains at
//         most 30 characters and no embedded blanks,
//         on one line of input.

// Output: The given infix expression and the equivalent
//         postfix expression.

// Assumptions:
//      1. The input string is a legal infix expression, 
//         which can contain parentheses.
//      2. Only the binary operators +, -, *, / are allowed.
//      3. Every character that is not an operator or a
//         parenthesis is a legal operand.
//      4. The class stackClass for a stack of characters 
//         is available.
// *********************************************************

#include <iostream.h>
#include "StackP.cpp" // stack operations
#include <string.h>   // string operations

const int MAX_STRING = 30;
typedef char expressionType[MAX_STRING+1];

// categories of characters
enum category {Operand, Operator, OpenParen, CloseParen};

void ConvToPost(const char IEin[], char PEout[])
// --------------------------------------------------------
// Converts an infix expression to postfix form.
// Precondition: The input expression IEin is a string
// that represents a legal infix expression where:
//   Operators are +, -, *, or /.
//   Open and close parentheses are permitted.
//   All other characters are operands.
// Postcondition: PEout is the equivalent postfix
// expression.
// Calls: TypeOfChar, ProcessOperand, ProcessCloseParen,
// ProcessOperator, and stack operations.
// --------------------------------------------------------
{
   stackClass S;
   char       Ch, Top;
   boolean    Success;

   // headers for functions that this function calls:
   category TypeOfChar(char);
   void ProcessOperand(char, char[]);
   void ProcessCloseParen(stackClass&, char[]);
   void ProcessOperator(stackClass&, char, char[]);

   // prepare for conversion
   strcpy(PEout,"");  // output string is empty

   // process each character in the input expression
   for (int I = 0; I < strlen(IEin); ++I)
   {  Ch = IEin[I];
      switch (TypeOfChar(Ch))
      {  // operand - concatenate to the output string
         case Operand: 
            ProcessOperand(Ch, PEout); 
            break;

         // open paren - push onto the stack
         case OpenParen: 
            S.Push(Ch, Success); 
            break;

         // close paren - pop operators, appending
         // them to output string, until a matching
         // open paren is found
         case CloseParen: 
            ProcessCloseParen(S, PEout); 
            break;

         // operator - pop operators of >= precedence
         case Operator: 
            ProcessOperator(S, Ch, PEout);
      }  // end switch
   }  // end for

   // move the rest of the stack to the output string
   while (!S.StackIsEmpty())
   {  S.GetStackTop(Top, Success);
      S.Pop(Success);
      strncat(PEout, &Top, 1);  // concatenate
   }  // end while
}  // end ConvToPost

int Prec(char Op)
// --------------------------------------------------------
// Computes the precedence of an operator.
// Precondition: Op is an operator.
// Postcondition: Returns 1 for + and -, 2 for * and /,
// and 0 for any other character.
// --------------------------------------------------------
{
   enum precedence {LOWEST, MID, HIGHEST};
   switch (Op)
   {  case '+': case '-' : 
         return MID;
      case '*': case '/' : 
         return HIGHEST;
      default            : 
         return LOWEST;
   }  // end switch
}  // end Prec

category TypeOfChar(char Ch)
// --------------------------------------------------------
// Categorizes a character.
// Precondition: Ch is a legal character.
// Postcondition: Returns a value (Operand, Operator, 
// OpenParen, CloseParen) according to the category of the 
// character Ch.
// --------------------------------------------------------
{
   switch (Ch)
   {  case '+': case '-': case '*': case '/' :
         return Operator;
      case '(':
         return OpenParen;
      case ')':
         return CloseParen;
      default :
         return Operand;
   }  // end switch
}  // end TypeOfChar

void ProcessOperand(char Ch, char PEout[])
// --------------------------------------------------------
// Processes operands.
// Precondition: Ch is an operand. PEout is either empty
// or contains the first part of the postfix expression.
// Postcondition: Operand Ch is appended to the end of the
// postfix expression PEout.
// --------------------------------------------------------
{
   strncat(PEout, &Ch, 1);  // concatenate
}  // end ProcessOperand

void ProcessCloseParen(stackClass& S, char PEout[])
// --------------------------------------------------------
// Processes right parentheses.
// Precondition: Stack S is not empty.
// Postcondition: Pops operators from stack S and appends
// them to the end of the postfix expression PEout until a
// matching open paren is found.
// Calls: Stack operations.
// --------------------------------------------------------
{
   char    Top;
   boolean Success;

   S.GetStackTop(Top, Success);
   while (Top != '(')
   {  strncat(PEout, &Top, 1);  // concatenate
      S.Pop(Success);
      S.GetStackTop(Top, Success);
   }  // end while

   S.Pop(Success);
}  // end ProcessCloseParen

void ProcessOperator(stackClass& S, char Ch, char PEout[])
// --------------------------------------------------------
// Processes operators.
// Precondition: Stack S is not empty. Ch is an operator;
// PEout is either empty or contains the first part of
// the postfix expression.
// Postcondition: Pops operators from stack S whose
// precedence is >= present operator Ch and appends them
// to the end of the postfix expression PEout.
// Calls: Stack operations.
// --------------------------------------------------------
{
   char    Top;
   boolean Success;

   boolean Done = FALSE;
   while (!S.StackIsEmpty() && !Done)
   {  S.GetStackTop(Top, Success);
      if ( (Top != '(') && (Prec(Top) >= Prec(Ch)) )
      {  strncat(PEout, &Top, 1);  // concatenate
         S.Pop(Success);
      }
      else 
         Done = TRUE;
   }  // end while

   S.Push(Ch, Success);
}  // end ProcessOperator

void ReadExpr(char IEin[], int ExprLength)
// --------------------------------------------------------
// Reads an expression from standard input.
// Precondition: Exprlength is the maximum desired
// expression length.
// Postcondition: IEin contains the expression.
// --------------------------------------------------------
{
   cout << "Enter infix expression of no more than "
        << ExprLength << " characters:\n";
   cin.getline(IEin, ExprLength+1);
}  // end ReadExpr

main()  // demonstrate function ConvToPost
{
   expressionType IEin;       // infix expression - input
   expressionType PEout;      // postfix expression - output

   cout << "Enter QUIT instead of an expression "
        << "to exit program.\n";
   ReadExpr(IEin, MAX_STRING);  // read infix expression

   while (strcmp(IEin, "QUIT"))
   {  ConvToPost(IEin, PEout);  // convert to postfix form

      // write out the infix and postfix expressions
      cout << "\nInfix expression:   " << IEin << "\n"
           << "\nPostfix expression: " << PEout << "\n";

      ReadExpr(IEin, MAX_STRING);  // read infix expression
   }  // end while

   cout << "Done.\n";
   return 0;
}  // end main