Code:
/* 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 */