The C Programming Language (K&R) Chapter 5 Ex 10-20

Exercise
5-10. Write the program expr, which evaluates a reverse Polish expression from the command line, where each operator or operand is a separate argument. For example, expr 2 3 4 + * evaluates 2 * (3+4).
Solution posted here

5-11. Modify the program entab and detab (written as exercises in Chapter 1) to accept a list of tab stops as arguments. Use the default tab settings if there are no arguments.
5-12. Extend entab and detab to accept the shorthand entab -m +n to mean tab stops every n columns, starting at column m. Choose convenient (for the user) default behavior.

- entab and detab are used to handle problems on copy-and-paste from text files (ref)

- the requirement of 5-12 is not clear enough to know what is column. handling m and n is coded here

- entab: just change the argument and eliminate getline

stdio.h
#define TABSTOP 4

int main(int argc, char *argv[]){
	int c, count = 0, n = (argc>1)?atoi(*++argv):TABSTOP, isblank = 1;

	while((c = getchar())!=EOF){
		if(c == ' '){
			isblank = 1;
			if (++count == n){
				putchar('\t');
				count = 0;
			}
		}
		else{
			if(isblank){
				while(count>0){
					putchar(' ');
					count--;
				}
			}
			isblank = 0;
			putchar(c);
		}
	}

	return 0;
}

- detab: to test, we add some tabs from arguments

/* addtab: put tabs into argv input */
void addtab(int argc, char* argv[], char* tab){
	int i;
	int pos;

	if(argc0){
			pos = atoi(*++argv);
			if(pos>0 && pos

5-13. Write the program tail , which prints the last n lines of its input. By default, n is set to 10, let us say, but it can be changed by an optional argument so that “tail -n” prints the last n lines. The program should behave rationally no matter how unreasonable the input or the value of n. Write the program so it makes the best use of available storage; lines should be stored as in the sorting program of Section 5.6, not in a two-dimensional array of fixed size.

stdio.h, string.h
# define MAXLEN 1000	 // maximum input line size
# define MAXSTOR 5000    // size of available storage space
# define BUFFSIZE 10000  // buffer size to store to character strings
# define DEFAULT_LINE_SIZE 10

char *lineptr[MAXLEN];	// pointers to text lines
int getline(char *, int);
int readlines(char *lineptr[], char*, int nlines);
void writelines1(char *lineptr[], int nlines, int);

// sort input lines
int main(int argc, char *argv[]){
    int nlines, n = DEFAULT_LINE_SIZE;
	char line[BUFFSIZE];   // line of character strings

	while (--argc > 0 && **++argv == '-')
        if(**argv == '-')
            if ((n = atoi(*argv + 1)) <= 0)
                n = DEFAULT_LINE_SIZE;

	if((nlines = readlines(lineptr, line, MAXLEN))>=0){
		writelines1(lineptr, nlines, nlines-n);
		return 0;
	}
	else{
		printf("error: input too big to sort\n");
		return 1;
	}
}
/* writelines1: write output lines */
void writelines1(char *lineptr[], int nlines, int start){
	int i;

	for(i=start; i<nlines; i++)
		printf("%s\n", lineptr[i]);
} ...

5-14. Modify the sort program to handle a -r flag, which indicates sorting in reverse (decreasing) order. Be sure that -r works with -n.
5-15. Add the option -f to fold upper and lower case together, so that case distinctions are not made during sorting; for example, a and A compare equal.
- up to here, we still can make use of existing functions in library

stdio.h, string.h ...
int main(int argc, char* argv[]){
    int nlines;			// number of input lines read
	int numeric = 0;	// 1 if numeric sort
	int order = 0;		// 1 if sort in reverse order
	int casesen = 0;	// 1 if case insensitive

	if(argc>1){
		while(--argc>0){
			if(strcmp(argv[argc], "-n")==0)
				numeric = 1;
			if(strcmp(argv[argc], "-r")==0)
				order = 1;
			if(strcmp(argv[argc], "-f")==0)
				casesen = 1;
		}
	}
	if((nlines = readlines(lineptr, MAXLINES))>=0){
		quicksort((void**)lineptr, 0, nlines-1, (int (*)(void*, void*))(numeric?numcmp:(cassesen?stricmp:strcmp)), order);
		// pointer to a function that has two void* arguments and returns n int
		// void* can refer to any data types of pointer
		// numcmp and strcmp are address of functions
		writelines(lineptr, nlines);
		return 0;
	}
	else{
		printf("error: input too big to sort\n");
		return 1;
	}
}
/* quicksort: sort v[0]...v[n-1] into increasing order, for any data type */
void quicksort(void *v[], int left, int right, int (*comp)(void*, void*), int order){
     int i, last;

     if(left>=right)
        return;
     swap(v, left, (left+right)/2);
     last = left;
     for(i=left+1; i<=right; i++)
        if(((*comp)(v[i],v[left])<0 && order==0) || ((*comp)(v[i],v[left])>0 && order==1))
           swap(v, ++last, i);
     swap(v, left, last);
     quicksort(v, left, last-1, comp);
     quicksort(v, last+1, right, comp);
} ...

5-16. Add the -d (“directory order”) option, which makes comparisons only on letters, numbers and blanks. Make sure it works in conjunction with -f.
5-17. Add a field-searching capability, so sorting may be done on fields within lines, each field sorted according to an independent set of options. (The index for this book was sorted with -df forthe index category and -n for the page numbers.)
- we need to write our string compare function here
- the int variables for sorting requirements are made public

- Ex. 5-17 is actually simulating field-sorting function of csv files in MS EXCEL: each fields are separated by a comma and a tab, to sort it, we code a fieldcmp function that compares the field and ignore other items

stdio.h, string.h
int numeric = 0;	// 1 if numeric sort
int order = 0;		// 1 if sort in reverse order
int casesen = 0;	// 1 if case insensitive
int dirorder = 0;	// 1 if sort in direct order
int main(int argc, char* argv[]){
    int nlines;			// number of input lines read

	if(argc>1){
		while(--argc>0){
			if(strcmp(argv[argc], "-n")==0)
				numeric = 1;
			if(strcmp(argv[argc], "-r")==0)
				order = 1;
			if(strcmp(argv[argc], "-f")==0)
				casesen = 1;
			if(strcmp(argv[argc], "-d")==0)
				dirorder = 1;
		}
	}
	if((nlines = readlines(lineptr, MAXLINES))>=0){
		quicksort((void**)lineptr, 0, nlines-1, (int (*)(void*, void*))(numeric?numcmp:strcmp1), order);
		writelines(lineptr, nlines);
		return 0;
	}
	else{
		printf("error: input too big to sort\n");
		return 1;
	}
}
/* strcmp1: compare s1 and s2 under different command */
int strcmp1(char *s1, char *s2){
	if(dirorder){
		while (!isalpha(*s1) && !isdigit(*s1) && !isspace(*s1) && *s1)
			s++;
		while (!isalpha(*s2) && !isdigit(*s2) && !isspace(*s2) && *s2)
			t++;
	}
	while(){
		if(*s1!=*s2)
			return *s1-*s2;
		if(casesen && (tolower(*s1)-'a')!=(tolower(*s2)-'a'))
			return (tolower(*s1)-'a')-(tolower(*s2)-'a');
		if(dirorder){
			while (!isalpha(*s1) && !isdigit(*s1) && !isspace(*s1) && *s1)
				s++;
			while (!isalpha(*s2) && !isdigit(*s2) && !isspace(*s2) && *s2)
				t++;
		}
		if(*s1=='' || *s2=='')
			break;
	}
	return 0;
}
/* Ex. 5-17 fieldcmp: compare s1 and s2 in the same field */
int fieldcmp(char* s1, char* s2){
	int i=0;
	char p1[MAXLEN], p2[MAXLEN];

	while(i<sortfield){
		if(*s1==',' || *s1=='\t')
			i++;
		if(*s1==''){
			printf("Cannot fild column %d\n", sortfield);
			exit(1);
		}
		s1++;
	}

	for(i = 0; *s1!=',' && *s1 != ''; i++)
		p1[i] = *s1++;
	p1[i] = '';

	i = 0;
	while(i<sortfield){
		if (*s2==',' || *s2=='\t')
			i++;
		if (*s2==''){
			printf("Cannot fild column %d\n", sortfield);
			exit(1);
		}
		s2++;
	}

	for(i = 0; *s2!=',' && *s2 != ''; i++)
		p2[i] = *s2++;
	p2[i] = '';

	return numeric?numcmp(p1, p2):strcmp(p1, p2);
} ...

5-18. Make dcl recover from input errors
- the problem wants to deal with errors when changing lines
- add a function parseerror to skip the \n
5-20. Expand dcl to handle declarations with function argument types, qualifiers like const, and so on

stdio.h, ctype.h, string.h
# define MAXTOKEN 100
# define BUFSIZE 100

enum{NAME, PARENS, BRACKETS, FUNARGS};

void dcl(void);
void dirdcl(void);
int gettoken(void);
void parseerror(void);
void findqualifier(char*);

int tokentype;				// type of last token
char token[MAXTOKEN];		// last token string
char name[MAXTOKEN];		// identifier name
char datatype[MAXTOKEN];	// data type = char, int, etc.
char qtype[MAXTOKEN];		// type of qualifier
char out[1000];				// output string
char buf[BUFSIZE];			// buffer for ungetch
int bufp = 0;				// next free position in buf
int iserror = 0;			// 1 when error occurrs
char *qualifiers[] = {"extern", "static", "auto", "register", "const", "volatile", "signed", "unsigned", "short", "long"};	// list of qualifiers to be matched

int main(void){
	while(gettoken()!=EOF){
		if(findqualifier(token)>0) {
			strcpy(qtype, strcat(token, " "));
			gettoken();
		}
		else
			qtype[0] = '';
		strcpy(datatype, token);
		out[0]='';
		dcl();
		if(tokentype!='\n'){
			fprintf(stderr, "syntax error\n");
			parseerror();
		}
		if (iserror)
            iserror = 0;
        else
			printf("%s: %s %s%s\n", name, out, qtype, datatype);
	}

	return 0;
}
// dirdcl: paarse a direct declarator
void dirdcl(void){
	int type;

	if(tokentype=='('){
		dcl();
		if(tokentype!=')'){
			fprintf(stderr, "error: missing )\n");
			parseerror();
			return;
		}
	}
	else if(tokentype==NAME)
		strcpy(name, token);
	else{
		fprintf(stderr, "error: expected name or (dcl)\n");
		parseerror();
		return;
	}
	while((type=gettoken())==PARENS || type==BRACKETS)
		if(type==PARENS)
			strcat(out, " function returning");
		else if(type==FUNARGS){
			strcat(out, " function ");
			strcat(out, token);
			strcat(out, " returning");
		}
		else{
			strcat(out, " array");
			strcat(out, token);
			strcat(out, " of");
		}
}

// gettoken: return next token, skipping blanks and tabs
int gettoken(void){
	int c, getch(void);
	void ungetch(int);
	char* p = token;

	while((c=getch())==' ' || c=='\t')
		;
	if(c=='('){
		if((c=getch())==')'){
			strcpy(token, "()");
			return tokentype=PARENS;
		}
		else{
			if(c='*'){
				ungetch(c);
				return tokentype='(';
			}
			else{
				*p++ = '(';
				for(*p++ = c; (*p++ = getch())!=')'; )
					;
				*p = '';
				return tokentype = FUNCARGS;
			}
		}
	}
	else if(c=='['){
		for(*p++=c; (*p++=getch())!=']' ;  )
			;
		*p='';
		return tokentype=BRACKETS;
	}
	else if(isalpha(c)){
		for(*p++=c; isalnum(c=getch()); )
			*p++=c;
		*p = '';
		ungetch(c);
		return tokentype=NAME;
	}
	else
		return tokentype=c;
}
// parseerror: handle \n
void parseerror(void){
	int c;

	if(tokentype!='\n')
	while((c=getch())!='\n')
		;
	tokentype = '\n';
	iserror = 1;
}

// findqualifier: find out is s matches one of the qualifiers, and 0 otherwise
int findqualifier(char *s){
	int i, len = sizeof(qualifiers)/sizeof(qualifiers[0]);

	for(i=0; i<len; i++)
		if(strcmp(qualifiers[i], s)==0)
			return 1;

	return 0;
} ...

5-19. Modify undcl so that it does not add redundant parentheses to declarations

- handle to problem caused on pointer variables, which having * before the variable name

stdio.h, ctype.h, string.h
...
int main(void){
	int type, prevtype = PARENS;
	char temp[MAXTOKEN];

	while(gettoken()!=EOF){
		strcpy(out, token);
		while((type=gettoken())!='\n'){
			if(prevtype == '*'){
				if(type == PARENS || type == BRACKETS)
					sprintf(temp, "(*%s)", out);
				else
					sprintf(temp, "*%s", out);
				strcpy(out, temp);
			}
			if(type==PARENS || type==BRACKETS)
				strcat(out, token);
			else if(type==NAME){
				sprintf(temp, "%s %s", token, out);
				strcpy(out, temp);
			}
			else
				fprintf(stderr, "invalid input at %s\n", token);
			prevtype = type;
		}
		printf("%s\n", out);
	}

	return 0;
} ...

About these ads