/**********************************************************************
 * expr.cc --- Convert infix expression to postfix form and indicate
 * if the infix expression was properly formed.
 *
 * This is a recursive descent parser, implementing the following
 * grammar:
 *    <expr>=<term>{+|-<term>}
 *    <term>=<factor>{*|/<factor}
 *    <factor>=(<expr>)|<letter>
 *    <letter>=a|b|c|...|z
 **********************************************************************/


#include <iostream.h>
#include <ctype.h>


void GetToken(void);
int Expression(void);
int Term(void);
int Factor(void);


char Token;   // Next character in the input stream --- one character 
              // lookahead.


/**********************************************************************
 * main()
 **********************************************************************/

int main()
{
   cout << "Type return on an otherwise empty line to exit.\n\n";

   while (1)
   {
      cout << "Expression: ";   // Read infix expression.
      GetToken();

      if (Token == '\n')   //
         return 0;

      // Parse the expression; if sucessful and we've read the entire line,
      // then we saw a valid expression

      if (Expression() && Token == '\n')
         cout << "\nValid expression\n";
      else
      {
         cout << "\nInvalid expression\n";
         while (Token != '\n')   // finish off the line
            GetToken();
      }
   }

   return 0;
}


/**********************************************************************
 * Expression() --- Parse an expression
 * This implements the production <expr>=<term>{+|-<term>}
 **********************************************************************/

int Expression(void)
{
   char Operator;

   if (!Term())
      return 0;

   while (Token == '+' || Token == '-')
   {
      Operator = Token;
      GetToken();   // Remove operator from input stream.
      if (!Term())
         return 0;
      cout << Operator;   // The operator is output following the
                          // operands --- converting the expression
                          // to postfix.
   }
   return 1;
}


/**********************************************************************
 * Term() --- Parse an term
 * This implements the production <term>=<factor>{*|/<factor>}
 **********************************************************************/

int Term(void)
{
   char Operator;

   if (!Factor())
      return 0;

   while (Token == '*' || Token == '/')
   {
      Operator = Token;
      GetToken();   // Remove operator from input stream.
      if (!Factor())
         return 0;
      cout << Operator;   // Postfix formulation.
   }
   return 1;
}


/**********************************************************************
 * Factor() --- Parse an factor
 * This implements the productions <factor>=(<expr>)|<letter>
 * and <letter>=a|b|c|...|z
 **********************************************************************/

int Factor(void)
{
   if (islower(Token))
   {
      cout << Token;   // Operands output immediately
      GetToken();   // Remove operand from input stream.
      return 1;
   }
   else if (Token == '(')
   {
      GetToken();   // Remove '(' from input stream.
      if (Expression() && Token == ')')   // check for parenthesized
                                          // expression
      {
         GetToken();   // Remove ')' from input stream.
         return 1;
      }
      else return 0;
   }
   else
      return 0;
}


/**********************************************************************
 * GetToken() --- read the next token from cin into the global variable
 * Token.
 **********************************************************************/

void GetToken(void)
{
   cin.get(Token);
}