/*
For this program you will implement another very small subset of the
LISP
programming language using binary trees; namely, arithmetic expressions.
You
may write your code in C or C++. In addition to correctness, programming
style is also important, so please write modular, well-documented code.
For this program a LISP arithmetic expression is of the form (op expr1
expr2), where op is one of + (addition), - (subtraction) or *
(multiplication). The arguments expr1 and expr2 are either integers in
the
range 1-999 or valid arithmetic expressions. Note that unlike PGM2, the
only
spaces in an expression are one between op and expr1 and one between
expr1
and expr2. You may assume that the final and all intermediate results
fall
within the range of the int type.
Your program will read in and print each expression, parse the
expression
into a binary parse tree, print out the indented tree, print out the
infix
representation of the expression, and print the final result. Your
program
cannot use global variables. Specifically:
1. Implement data structures for the binary tree as shown in class.
Note
that a tree object will need to store either an operator or an
integer.
2. Implement procedures for creating a binary parse tree from the
input
expression, printing the tree using indentation to note
parent-child
relationships, printing the infix representation of the expression,
evaluating the tree, and freeing the tree.
3. The main part of your program will read in data from a file whose
name
is given as the first argument to your executable. The file will
consist of one or more lines, each containing a valid arithmetic
expression. Your main program should process each line one at a
time
and for each line, output the expression, the indented binary parse
tree, the infix notation and the result.
*/
/* Name: Anan Tongprasith */
/* Compile: cc tree.c */
#include
#include
/********************** New structure type *******************/
struct mytree { char *myval; /* node value */
struct mytree *left; /* pointer to left child */
struct mytree *right; /* pointer to right child */
};
/*************************************************************/
/********************** List of all functions *****************/
/* This function puts expression into tree structure */
struct mytree *stufftree(char *readin);
/* This function evaluates result from a tree */
int evaltree(struct mytree *temptree);
/* This function prints inorder output */
int inorderwalk(struct mytree *temptree);
/* This function prints the indented tree */
int printtree(struct mytree *temptree,int n);
/* This function frees the given tree */
int freetree(struct mytree *temptree);
/***************************************************************/
int main(int argc,char *argv[])
{ char myread[400];FILE *fp;
struct mytree *mypointer;
fp=fopen(argv[1],"r");
while(fgets(myread,400,fp) != NULL) /* read one line */
{ printf("Expression: %s\n",myread);
mypointer=stufftree(myread); /* put into a tree */
printf("Tree:\n");
printtree(mypointer,2); /* print the indented tree */
printf("\n");
printf("Result: ");
inorderwalk(mypointer); /* print the inorder expression */
printf(" = %d\n\n",evaltree(mypointer)); /* print result */
freetree(mypointer);
}
fclose(fp);
}
/*******************************************************/
struct mytree *stufftree(char *readin)
{ char myopr,buf1[200],buf2[200];
struct mytree *temptree;
int i,count=0,third;
if(readin[0]!='(') /* Check if it is number or expression? */
{ temptree=malloc(16+strlen(readin)+1);/* number!, need 2pointer+value */
temptree->myval=malloc(strlen(readin)+1); /*need strlen + 1 length*/
sprintf(temptree->myval,"%s",readin);
temptree->left=0; /* leave node, no child */
temptree->right=0;
return(temptree);
}
else
{ /* it is another expression */
/****** First arg, operator *******/
myopr=readin[1];
/****** Second arg, number or subexpression ******/
i=3;
if(readin[i]=='(') /* check if it is number or expression*/
{ do /* reading subexpression */
{ buf1[i-3]=readin[i];
if(readin[i]=='(') count+=1;
if(readin[i]==')') count-=1; /*tracking parenthesis*/
i+=1;
} while(count>0);
}
else
{ do /* reading number */
{ buf1[i-3]=readin[i];
i+=1;
} while(readin[i]!=' ');
}
buf1[i-3]='\0'; /* close the string */
/***** Third arg, number or subexpression *****/
i+=1;third=i;count=0;
if(readin[i]=='(') /* check if it is number or expression */
{ do /* reading subexpression */
{ buf2[i-third]=readin[i];
if(readin[i]=='(') count+=1;
if(readin[i]==')') count-=1;
i+=1;
} while(count>0);
}
else
{ do /* reading number */
{ buf2[i-third]=readin[i];
i+=1;
} while(readin[i]!=')');
}
buf2[i-third]='\0'; /* close the string */
/***** Now stuffing the tree *****/
temptree=malloc(18); /* 1 operator + 2 pointers */
temptree->myval=malloc(2);
sprintf(temptree->myval,"%s",&myopr);
temptree->left=stufftree(buf1);
temptree->right=stufftree(buf2);
return(temptree);
}
}
/***********************************************************/
int evaltree(struct mytree *temptree)
{
if(temptree->myval[0]=='+')
/* returning left child + right child */
return(evaltree(temptree->left)+evaltree(temptree->right));
if(temptree->myval[0]=='-')
return(evaltree(temptree->left)-evaltree(temptree->right));
if(temptree->myval[0]=='*')
return(evaltree(temptree->left)*evaltree(temptree->right));
if(temptree->myval[0]=='/')
return(evaltree(temptree->left)/evaltree(temptree->right));
/* returning the number (leave node) */
return(atoi(temptree->myval));
}
/********************************************************/
int inorderwalk(struct mytree *temptree)
{
if(temptree->left==0)
printf("%i",atoi(temptree->myval)); /* print number(leave node)*/
else
{ printf("("); /* print expression */
inorderwalk(temptree->left); /* left child */
printf(" %s ",temptree->myval); /* operator */
inorderwalk(temptree->right); /* right child */
printf(")");
}
}
/***************************************************/
int printtree(struct mytree *temptree,int n)
{ int i=n;
if(temptree->left==0)
{ while(i>0) /* print indent */
{ printf(" ");i--;
}
printf("%s\n",temptree->myval); /*print number (leave node)*/
}
else
{ while(i>0) /* print indent */
{ printf(" ");i--;
}
printf("%s\n",temptree->myval); /*print operator */
printtree(temptree->left,n+2); /*left child with more indent*/
printtree(temptree->right,n+2); /*right child with more indent*/
}
}
int freetree(struct mytree *temptree)
{
if(temptree->left!=0)
{ freetree(temptree->left);
freetree(temptree->right);
}
free(temptree->myval);
free(temptree);
} (
geocities.com/vienna/7079) (
geocities.com/vienna)