/*
For this program you will implement a very small subset of the LISP
programming language using singly-linked lists. 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.
LISP stands for ``list processing'' and is used to define, query and
modify
lists of symbols. For us, a symbol is a string of no more than 32
uppercase
alphanumeric characters (A-Z, 0-9). A list is denoted by a
space-separated
sequence of symbols surrounded by parentheses, e.g., ( CSE 2320 SECTION
501
), with one space between each symbol and surrounding parentheses. The
empty
list is denoted by ( ).
The three LISP commands you are to implement are SETF, NTH and NTHREST
as
described in the following table, where n is a positive integer less
than
100.
Sets variable var to list for
( SETF var list ) possible future reference.
Variable
var can be any valid symbol. SETF
returns the list.
Returns the nth symbol in the
given
list or the list stored in
variable
var. If the list has fewer than n
( NTH n [$\{list \vert var\}$] ) elements, then NTH returns the
empty
list ( ). If the variable var is
undefined, then NTH returns
``Error:
undefined variable''.
Returns the list remaining after
removing the first n symbols from
the given list or the list stored
in
variable var. If the list has
fewer
( NTHREST n [$\{list \vert var\}$] ) than n symbols, then NTHREST
returns
the empty list ( ). If the
variable
var is undefined, then NTHREST
returns ``Error: undefined
variable''.
1. Implement data structures for the singly-linked list used to store
the
lists of symbols.
2. You may implement a global array to store the variables, but this
is
the only global variable allowed. There will be no more than 100
different vairables.
3. Be sure to garbage-collect the existing list when a variable is
redefined. Garbage-collect all lists allocated just for NTH and
NTHREST
commands. Before ending the program, garbage-collect all other
allocated memory.
4. 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 command from
among the three described above. Your main program should process
each
line one at a time and for each line, output the command read in,
the
result and a newline.
*/
/*name:Anan Tongprasith*/
/*compile: cc sll.c*/
#include
#include
/* A new structure type is defined as "mylist": */
/* ( name, pointer ) . */
/* A global array named "namelist" is defined as type "mylist". */
/*--------------------------------------------------------------*/
/* Place in array| variable names| pointer */
/*--------------------|---------------|-------------------------*/
/* namelist[0] | X | pointer-to-X-head */
/* namelist[1] | Y | pointer-to-Y-head */
/* : | : | : */
/* namelist[99] | DOE | pointer-to-DOE-head */
/*--------------------------------------------------------------*/
/* A variable is linked to a singly linked-list: */
/* namelist[0] namelist[1] */
/* X:head-ptr Y:head-ptr */
/* | */
/* \|/ */
/* X(1):nextptr--->X(2):nextptr--->...--->X(n):0 */
/* Main function reads command from a file, calls functions, */
/* and clear the variable array. */
/* Function "mysetf" carries on the "SETF" command. */
/* Function "mynth" carries on the "NTH" command. */
/* Function "mynthrest" carries on the "NTHREST" command. */
/* Function "myfree" frees the memory blocks allocated for a */
/* linked-list, given the head of the list. */
/* Function "findplace" find the location of the specified variable */
/* from the "namelist" array. If it isn't found, a new available*/
/* location is returned (for a new variable).*/
/* Define a new structure data type*/
struct mylist{
char *myname;
struct mylist *next;
};
/*Array of variables'names and head-ptr's of the linked-lists */
struct mylist *namelist[100];
int main(int argc, char *argv[])
{ struct mylist *info,*nextinfo;
char mycommand[10],myparam[5],buf[100],newline[100];
int mycount;long i;FILE *fp;
/* Initialize the "namelist" array */
for(mycount=0;mycount<100;mycount++)
{
/* 2 pointers need 16 bytes */
namelist[mycount]=malloc(16);
namelist[mycount]->myname=malloc(8);
/* Put an empty string into every name */
sprintf(namelist[mycount]->myname,"%s","\0");
namelist[mycount]->next=0;
}
fp=fopen(argv[1],"r");
/* Read the lines */
while(fgets(newline,100,fp) != NULL)
{
/* Read in command and parameters */
sscanf(newline,"( %s %s %s",mycommand,myparam,buf);
/* Reread if the final parameter is a list */
if(strcmp(buf,"(")==0)
sscanf(newline,"( %s %s %100c",mycommand,myparam,buf);
/* Checking which function to run*/
printf("%s",newline);
if(strcmp(mycommand,"SETF")==0)
mysetf(myparam,buf);
if(strcmp(mycommand,"NTH")==0)
mynth(atoi(myparam),buf);
if(strcmp(mycommand,"NTHREST")==0)
mynthrest(atoi(myparam),buf);
}
/* Clear all the variables, free memory blocks, and exit */
for(mycount=0;mycount<100;mycount++)
{
if(strlen(namelist[mycount]->myname)!=0)
/* Clear every available variable in the array */
myfree(namelist[mycount]->next);
/* Clear the array itself */
free(namelist[mycount]);
free(namelist[mycount]->myname);
free(namelist[mycount]->next);
}
fclose(fp);
}
int mysetf(char *myparam,char *mybuf)
{ struct mylist *info,*newinfo;
int myplace=0;
char myvalue[100]="a",mynewbuf[100]="a";
/* Find available place in the "namelist" array */
/* New variable is given a new place. Old variable is given the old one.*/
myplace=findplace(myparam);
/* Clear the old one (if exists) first */
myfree(namelist[myplace]->next);
/* Adding a new list */
sscanf(mybuf,"( %s %100c",myvalue,mynewbuf);
strcpy(mybuf,mynewbuf);
/* First entry */
/* 16 bytes for 2 pointers */
info=malloc(16);
/* Put the variable name in */
sprintf(namelist[myplace]->myname,"%s",myparam);
/* Put the head pointer in */
namelist[myplace]->next=info;
/* First entry of the linked-list */
info->myname=malloc(strlen(myvalue)+1);
sprintf(info->myname,"%s",myvalue);
sscanf(mybuf,"%s %100c",myvalue,mynewbuf);
strcpy(mybuf,mynewbuf);
/* Keep adding untill end of the list ")" */
while(strcmp(myvalue,")")!=0)
{ newinfo=malloc(16);
info->next=newinfo;
info=newinfo;
info->myname=malloc(strlen(myvalue)+1);
strcpy(info->myname,myvalue);
sscanf(mybuf,"%s %100c",myvalue,mynewbuf);
strcpy(mybuf,mynewbuf);
}
info->next=0;
/* Printing out a new variable's */
printf("( ");
info=namelist[myplace]->next;
do
{ printf("%s ",info->myname);
info=info->next;
}
while(info!=0);
printf(")\n\n");
}
int findplace(char *myparam)
{ int mycount=0,myplace=0;
/* Searching until finding an empty one */
while(strlen(namelist[mycount]->myname)!=0&&mycount<100)
{
/* Return the location we found the variable */
if(strcmp(namelist[mycount]->myname,myparam)==0)
{
return mycount;
}
else
{ mycount++;
}
}
/* The variable isn't found, return a new place in the "namelist" */
return mycount;
}
int mynth(int n,char *buf)
{ struct mylist *info,*newinfo,*head;
char newbuf[100],myvalue[30];
int mycount=1,myclear=0;
if(buf[0]=='(')
/* A list is passed in, let's put it into a linked-list */
{ sscanf(buf,"( %s %100c",myvalue,newbuf);
strcpy(buf,newbuf);
/* Clearing flag is set, the linked-list will be cleared later */
myclear=1;
while(strcmp(myvalue,")")!=0)
{
newinfo=malloc(16);
if(mycount==1)
{ head=newinfo;
info=head;
}
else { info->next=newinfo;
info=newinfo;
}
info->myname=malloc(strlen(myvalue)+1);
sprintf(info->myname,"%s",myvalue);
sscanf(buf,"%s %100c",myvalue,newbuf);
strcpy(buf,newbuf);
mycount++;
}
info->next=0;
}
/* A variable is passed in, look up the table first */
else
{ mycount=findplace(buf);
/* Check if it is a new place (string length=0) or not */
if(strlen(namelist[mycount]->myname)==0)
/* Findplace give you a new place, that means it can't find the variable*/
{ printf("Error: undefined variable\n\n");
return 0;
}
else
/* The variable is found */
head=namelist[mycount]->next;
}
/* Printing output */
mycount=1;info=head;
/* Skip (n-1) steps */
while(mycountnext;
info=newinfo;
mycount++;
}
if(head==0||info==0) printf("( )\n\n");
/* Printing the nth */
else printf("%s\n\n",info->myname);
/* If clearflag is set, clear the memory on temp variable */
if(myclear!=0)
myfree(head);
}
int mynthrest(int n,char *buf)
{ struct mylist *info,*newinfo,*head;
char newbuf[100],myvalue[30];
int mycount=1,myclear=0;
if(buf[0]=='(')
/* A list is passed in, let's put it into a linked-list */
{ sscanf(buf,"( %s %100c",myvalue,newbuf);
strcpy(buf,newbuf);
/* A clearflag is set */
myclear=1;
while(strcmp(myvalue,")")!=0)
{
newinfo=malloc(16);
if(mycount==1)
{ head=newinfo;
info=head;
}
else { info->next=newinfo;
info=newinfo;
}
info->myname=malloc(strlen(myvalue)+1);
sprintf(info->myname,"%s",myvalue);
sscanf(buf,"%s %100c",myvalue,newbuf);
strcpy(buf,newbuf);
mycount++;
}
info->next=0;
}
/* A variable is passed in, look up the table first */
else
{ mycount=findplace(buf);
if(strlen(namelist[mycount]->myname)==0)
/* Findplace give you a new place, that means it can't find the variable*/
{
printf("Error: undefined variable\n\n");
return 0;
}
else
/* The variable is found */
head=namelist[mycount]->next;
}
/* Printing output */
mycount=1;info=head;
/* Skipping the first n items */
while(mycount<=n&&info!=0)
{
newinfo=info->next;
info=newinfo;
mycount++;
}
printf("( ");
while(info!=0)
{ newinfo=info->next;
printf("%s ",info->myname);
info=newinfo;
}
printf(")\n\n");
/* Clear memory on temp variable */
if(myclear!=0)
{ myfree(head);
}
}
/* Free the memory blocks, given the head of the list */
int myfree(struct mylist *myinfo)
{ struct mylist *newinfo;
/* Repeat until the end of the list */
while(myinfo!=0)
{ newinfo=myinfo->next;
free(myinfo);
free(myinfo->myname);
free(myinfo->next);
myinfo=newinfo;
}
return 0;
} (
geocities.com/Vienna/7079) (
geocities.com/Vienna)