#include <stdio.h> // printf() etc
#include <malloc.h> // for malloc()
#include <ctype.h> // for tolower()
#define FALSE 0
#define TRUE 1
#define VERIFY( cond, msg ) \
if ( ! cond ) { \
printf( " <><> Error. %s\n", msg );\
}
// node has 1 of these class states: literal, identifier, or operator.
// Parenthesized expressions have been reduced; no need to store ().
typedef enum { Literal, Identifier, Operator } NodeClass;
typedef struct NodeType * NodePtr; // forward announcement
// now comes the actual node structure; using the forward declared pointers.
typedef struct NodeType
{
NodeClass Class; // 1 of the 3 classes.
char Symbol; // stores ident or literal
int LitVal; // if Class == Literal, this is its value
NodePtr Left; // subtrees
NodePtr Right; // subtrees
} s_node_tp;
char NextChar;
s_node_tp OneNode = { Literal, '1', 1, NULL, NULL };
s_node_tp NullNode = { Literal, '0', 0, NULL, NULL };
void GetNextChar( )
{ // GetNextChar
if ( NextChar != '$' ) {
NextChar = getchar( );
if ( NextChar == ' ' )
GetNextChar();
//end if
} //end if*/
} //end GetNextChar
unsigned IsDigit( char c )
{ // IsDigit
return ( c >= '0' ) && ( c <= '9' );
} //end IsDigit
unsigned IsLetter( char c )
{ // IsLetter
return ( c >= 'a' && c <= 'z' ) || ( c >= 'A' && c <= 'Z' );
} //end IsLetter
// malloc a new node off the heap. All fields passed in
// and pass the pointer to the node to caller
NodePtr Make( NodeClass Class, char Symbol, int value, NodePtr Left, NodePtr Right )
{ // Make
NodePtr Node = (NodePtr) malloc (sizeof( struct NodeType ) );
Node->Class = Class;
Node->Symbol = Symbol;
Node->LitVal = value;
Node->Left = Left;
Node->Right = Right;
return Node;
} //end Make
NodePtr Expression( ); // forward
NodePtr Factor( )
{ // Factor
char Symbol;
NodePtr Temp;
Symbol = NextChar;
GetNextChar();
if ( IsDigit( Symbol ) )
return Make( Literal, Symbol, (int)( Symbol - '0' ), NULL, NULL );
else if ( IsLetter( Symbol ) )
return Make( Identifier, tolower( Symbol ), 0, NULL, NULL );
else if ( Symbol == '(' ) {
Temp = Expression();
if ( NextChar != ')' )
printf( ") expected.\n" );
//end if
GetNextChar();
return Temp;
}else if ( Symbol == '&' ) {
return Make( Operator, '&', 0, NULL, Factor() );
}else{
printf( "Illegal character '%c'.\n", Symbol );
} //end if
} //end Factor
NodePtr Primary( )
{ // Primary
NodePtr Left = Factor();
if ( NextChar == '^' ) {
GetNextChar();
Left = Make( Operator, '^', 0, Left, Factor() );
} //end if
return Left;
} //end Primary
NodePtr Term( )
{ // Term
NodePtr Left;
char Op;
Left = Primary();
while ( NextChar == '*' || NextChar == '/' ) {
Op = NextChar;
GetNextChar();
Left = Make( Operator, Op, 0, Left, Primary() );
} //end while
return Left;
} //end Term
NodePtr Expression( )
{ // Expression */
NodePtr Left;
char Op;
Left = Term();
while ( NextChar == '-' || NextChar == '+' ) {
Op = NextChar;
GetNextChar();
Left = Make( Operator, Op, 0, Left, Term() );
} //end while*/
return Left;
} //end Expression*/
/******* T r e e P r i n t i n g M o d u l e ******/
void PrintTree( NodePtr Root )
{ // PrintTree
if ( Root != NULL ) {
if ( Root->Class == Operator ) {
printf( "(" );
} //end if
PrintTree( Root->Left );
if ( Root->Class == Literal ) {
printf( "%d", Root->LitVal );
}else{
printf( "%c", Root->Symbol );
} //end if
PrintTree( Root->Right );
if ( Root->Class == Operator ) {
printf( ")" );
} //end if
} //end if*/
} //end PrintTree
int main ()
{ // main: Differentiation
NodePtr root = NULL;
NextChar = ' ';
printf( " Enter f(x), ended with '$':\t" );
GetNextChar();
// after initialization, this is key: call Expression()
root = Expression();
VERIFY( ( NextChar == '$' ), "$ expected, not found\n" );
printf( " Tree with explicit ( ) added:\t" );
PrintTree( root );
printf( "\n" );
// all done
return 0;
} //end main