// Chapter 5, pp 229 - 231

// ********************************************************
// RECOGNIZES A PREFIX EXPRESSION.
// Input: An expression (string of 50 or fewer characters).
// An operand is a single uppercase letter; an operator is
// one of +, -, *, and /.
// Output: Writes a message that indicates whether the
// string is a prefix expression. Note that valid prefix
// expressions do not contain embedded blanks.
// Calls: IsPre, EndPre, IsBlank, and ReadWriteExpr.
// ********************************************************
#include <iostream.h>
#include <iomanip.h>
#include <string.h>
#include <ctype.h>
#include "boolean.h"

const int MAX_STRING = 50;
const int NOT_PRE = -1;  // return value for EndPre (<0)

typedef char expressionType[MAX_STRING+1];

boolean IsBlank(const char String[], int First, int Last)
// ---------------------------------------------------------
// Determines whether a substring is all blank or empty.
// Precondition: String[First..Last] specifies a substring.
// Postcondition: Returns TRUE if the substring is either
// all blanks or empty (First > Last); else returns FALSE.
// Assumption: The substring is small, so it is searched
// sequentially.
// ---------------------------------------------------------
{
   for (int Index = First; (Index <= Last) && (String[Index] == ' ');
        ++Index);

   return boolean(Index > Last);
}  // end IsBlank

int EndPre(const char Expression[], int First, int Last)
// ---------------------------------------------------------
// Finds the end of the legal prefix expression that
// begins at a given character. Uses the grammar
//   <pre> = <letter> | <operator><pre><pre>
//   where <letter> is a single uppercase letter.
// Precondition: Expression[First..Last] specifies a
// character string.
// Postcondition: Returns the index of the last character
// in the prefix expression that begins at First,
// or returns the constant NOT_PRE if no such prefix expression 
// exists.
// ---------------------------------------------------------
{
   int FirstEnd;  // index of end of first prefix expr.

   // test the bounds of the string
   if ( (First < 0) || (First > Last) )
      return NOT_PRE;  // empty string

   // base case - a single letter }
   else if (isupper(Expression[First]))
      return First;

   // general case - apply the recursive definition
   else if ( (Expression[First] == '+') ||
             (Expression[First] == '-') ||
             (Expression[First] == '*') ||
             (Expression[First] == '/') )
   {  // find end of the first prefix expression
      FirstEnd = EndPre(Expression, First+1, Last);

      if (FirstEnd > -1)
         // first prefix expression found,
         // so find end of the second prefix expression
         return EndPre(Expression, FirstEnd+1, Last);

      else 
         return NOT_PRE;  // expression is not prefix
   }  // end else if operator

   else
      return NOT_PRE;  // expression is not prefix
}  // end EndPre

boolean IsPre(const char Expression[])
// ---------------------------------------------------------
// Determines whether an expression is a valid prefix
// expression. Note that valid prefix expressions do not 
// contain embedded blanks.
// Precondition: Expression is a character string.
// Postcondition: Returns TRUE if Expression is in prefix
// form; otherwise returns FALSE. Expression is unchanged.
// Calls: EndPre and IsBlank.
// ---------------------------------------------------------
{
   int LastChar;  // index to last char of prefix expr

   // the end of the prefix expression that begins at 
   // index 0 must be the last nonblank character of the
   // input string
   int Size = strlen(Expression);  // length of input string
   LastChar = EndPre(Expression, 0, Size-1);
   if ( (LastChar >= 0) &&
        (IsBlank(Expression, LastChar+1, Size-1)) )
      return TRUE;
   else
      return FALSE;
}  // end IsPre

void ReadWriteExpr(char Expression[], int ExprLength)
// ---------------------------------------------------------
// Reads and then displays an expression.
// Precondition: ExprLength is the maximum desired
// expression length.
// Postcondition: Expression contains input expression,
// which is displayed, but is not followed by a carriage
// return. Expression can contain embedded blanks.
// ---------------------------------------------------------
{
   cout << "Enter expression of no more than "
	<< ExprLength << " characters:\n";
   cin.getline(Expression, ExprLength+1);

   cout << Expression;
}  // end ReadWriteExpr

main()  // demonstrate function IsPre
{  expressionType Expression;

   ReadWriteExpr(Expression, MAX_STRING);  // read and display expression
   if (IsPre(Expression))      // test expression
      cout << " is a legal prefix expression.\n";
   else
      cout << " is NOT a legal prefix expression.\n";
   return 0;
}  // end Program