/* This program uses a form of recursion known as a recursive chain to
   evaluate whether a given string is a valid expression.  The definition
   of a valid expression is as follows:

   a valid expression is either a term + term or a term alone
   a valid term is either a factor * factor or a factor alone
   a valid factor is either a single letter or an expression in parentheses

   It is in the definition of a valid factor that the recursion is introduced.
   The main function will call the function expression, which in turn will
   begin the recursive chain by calling exp.  The need for expression is
   so be able to check for the end of the line upon concluding that an
   expression is valid.

   This program does not evaluate the expression under consideration.  It
   only ascertains whether the expression is or is not valid as defined by
   the rules of the "grammar".  White space between characters in the string
   causes the evaluation to fail.

  */

#include <stdio.h>

#define TRUE 1                  /* boolean true */
#define FALSE 0                 /* boolean false */

int exp(char [], int *) ;       /* global prototypes for recursion */
int term(char [], int *) ;      /* is input string a term */
int factor(char [], int *) ;    /* is input string a factor */

int main(void)
{
   int expression(char [], int *);  /* start/end evaluation here */

   char str[80] ;               /* hold candidate expression string */

   printf("Enter a string to be checked for validity ");  /* prompt */
   printf("as an expression\n--> ") ;                     /* user for */
   fgets(str, 80, stdin) ;                                /* string */
   if (expression(str, 0 ))             /* if str is a valid expresion */
      printf("%s is a valid expression.\n", str);       /* print OK */
   else
      printf ("%s is not a valid expression.\n", str) ; /* else exp no good */
}                                                       /* end main */


/* --------------------------- EXPRESSION ----------------------------------
   INPUT: the expression string and an index position
   OUTPUT:
   RETURNS: TRUE if the string represents a valid expression; FALSE otherwise
   ASSUMPTIONS:
   DESCRIPTION:
   This function is called from main and in turn calls the recursive
   function to see is the string is a valid expression.  Upon returning
   from the recursive calls, if we are also at the end of the string,
   then the input string is a valid expression
   ------------------------------------------------------------------------- */
int expression(char str[], int pos)
{
   if (exp(str,&pos)) {         /* call to check if valid expression */
      pos++;                    /* move to next character */
      if (str[pos] == '\n')     /* if end of string, then */
         return(TRUE);          /* expression is valid */
      else return(FALSE);       /* else extra stuff at end of string */
   } else                       /* else invalid expression */
      return(FALSE);            /* return negative indicator */
}                               /* end function exp */


/* ----------------------------- EXP ----------------------------------------
   INPUT: the string containing the expression under consideration, and
          the current index position
   OUTPUT: the index position is shifted by this function to the end of the
           expression under evaluation.
   RETURNS: TRUE if the string represents a valid expression; FALSE otherwise
   ASSUMPTIONS:
   DESCRIPTION:  This function, first called by expression(), verifies that
   the input string is (or is not) a valid expression by following the rules
   as outlined in the documentation above.  A valid expression is either a
   term+term or a term alone.

   To evaluate whether this is a valid expression, check first for a term.
   If a valid term is found, move to the next index position.  If the
   next char is a '+', then another valid term must follow.  If the next
   char is not a '+', then move the index back one space and return to
   the caller with TRUE.

   This function is the first in the recursive chain, since a term is a
   factor * factor or a factor alone, and a factor can be an expression.
   ------------------------------------------------------------------------- */
int exp(char str[], int *pos)
{
   int flag;                    /* boolean flag for validity */

   if (term(str,pos)) {         /* if a term is found */
      flag = TRUE;              /* set marker to true */
      (*pos)++;                 /* examine next position */
      if (str[*pos] == '+') {   /* check for plus sign */
         (*pos)++;              /* if there, skip over it */
         flag = term(str,pos);  /* and check for another term */
      } else                    /* if no plus sign, */
         (*pos)--;              /* move position pointer back to first term */
   } else flag = FALSE;         /* else not a valid term */
   return flag;                 /* return flag to caller */
}                               /* end function exp1 */


/* ------------------------------- TERM ---------------------------------------
   INPUT: the string containing the expression under consideration, and
          the current index position
   OUTPUT: the index position is shifted by this function to the end of the
           term under evaluation.
   RETURNS: TRUE if the substring starting at index pos contains a valid term;
            FALSE otherwise
   ASSUMPTIONS:
   DESCRIPTION: Check if the input is a valid term, starting at index location
   'pos'.  The function stops when it has found a valid term or when it
   ascertains that the term is not valid.  A valid term is either a
   factor*factor or a factor alone.

   First check whether there is a valid factor.  If yes, check if the next
   char is a '*'.  If it is, then another valid factor must follow.  If
   it is not, move pos back one spot and return to the caller.

   This function is called from the function exp() as the second part of the
   recursive chain.
   -------------------------------------------------------------------------- */
int term(char str[], int *pos)
{
   int flag;                    /* boolean flag for validity */

   if (factor(str,pos)) {       /* if a factor is found */
      flag = TRUE;              /* set marker to true */
      (*pos)++;                 /* examine next position */
      if (str[*pos] == '*') {   /* if a * found */
         (*pos)++;              /* skip over it */
         flag = factor(str,pos);/* and check for another factor */
      } else                    /* else no * symbol, so point back to */
         (*pos)--;              /* previous factor */
   } else flag = FALSE;         /* else not a valid factor */
   return flag;                 /* return flag to caller */
}                               /* end function term */


/* --------------------------- FACTOR -----------------------------------------
   INPUT: the string containing the expression under consideration, and
          the current index position
   OUTPUT: the index position is shifted by this function to the end of the
           factor under evaluation.
   RETURNS: TRUE if the substring starting at index pos contains a valid
            factor; FALSE otherwise
   ASSUMPTIONS:
   DESCRIPTION: his function checks for a valid factor starting at the
   position pointed at by pos.  Note that a factor is either a letter alone
   or an expression enclosed in parentheses.  This last part of the
   definition of a valid factor is what makes the entire definition
   recursive.

   First check if the current substring is a single letter.  If yes,
   return true.  If not, the only other legal character is '('.  If
   found, then there must be a valid expression next, followed by a
   ')'.
   ------------------------------------------------------------------------- */
int factor(char str[], int *pos)
{
   int flag;                                    /* boolean flag for validity */

   if (str[*pos] >= 'A' && str[*pos] <= 'Z')    /* if a valid letter */
      return(TRUE);                             /* return positive flag */
   else if (str[*pos] == '(') {                 /* else if a ( char */
      (*pos)++;                                 /* skip over it */
      flag = exp(str,pos);                      /* and look for expression */
      (*pos)++;                                 /* move to next space */
      if (flag && str[*pos] == ')')             /* verify matching ) */
         return(TRUE);                          /* if ok, return flag */
      else return(FALSE);                       /* else non-matching () */
   } else
      return(FALSE);                            /* else non-factor */
}                                               /* end function factor */