Exercise 5.19. Modify undcl so that it does not add redundant parentheses to declarations.

Exercise 5.19. Modify undcl so that it does not add redundant parentheses to declarations.


#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define MAXTOKEN 100

enum {NAME, PARENS, BRACKETS};
enum {NO, YES};

void dcl(void);
void dirdcl(void);

int gettoken(void);
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 out[1000];
int posttoken(void);
int pretoken = NO;

/* undcl: convert word descriptions to declarations */
int main()
{
    int type;
    char temp[MAXTOKEN];
    
    while(gettoken() != EOF)        //1st token on line
    {
        strcpy(out, token);
        while((type = gettoken()) != '\n')
            if(type == PARENS || type == BRACKETS)
                strcat(out, token);
            else if(type == '*')
            {
                if((type = posttoken()) == PARENS || type == BRACKETS)
                    sprintf(temp, "(*%s)", out);
                else
                    sprintf(temp, "*%s", out);
                strcpy(out, temp);
            }
            else if(type == NAME)
            {
                sprintf(temp, "%s %s", token, out);
                strcpy(out, temp);
            }
            else
                printf("invalid input at %s\n", token);
        printf("%s\n", out);
    }
    return 0;
}

/* dcl: parse a declarator */
void dcl(void)
{
    int ns;
    
    for(ns = 0; gettoken() == '*';) //count stars
        ns++;
    dirdcl();
    while(ns-- > 0)
        strcat(out, " pointer to");
}

/* dirdcl: parse a direct declarator */
void dirdcl(void)
{
    int type;
    
    if(tokentype == '(') //(dcl)
    {
        dcl();
        if(tokentype != ')')
            printf("error: missing )\n");
    }
    else if(tokentype == NAME) //variable name
        strcpy(name, token);
    else
        printf("error: expected name or (dcl)\n");
    while((type = gettoken()) == PARENS || type == BRACKETS)
        if(type == PARENS)
            strcat(out, " function returning");
        else
        {
            strcat(out, " array");
            strcat(out, token);
            strcat(out, " of");
        }
}

int getch(void);
void ungetch(int c);


int gettoken(void)
{
    int c, getch(void);
    void ungetch(int);
    char *p = token;
    
    if(pretoken == YES)
    {
        pretoken = NO;
        return tokentype;
    }    
    while((c = getch()) == ' ' || c == '\t')
        ;
    if(c == '(')
    {
        if((c = getch()) == ')')
        {
            strcpy(token, "()");
            return tokentype = PARENS;
        }
        else
        {
            ungetch(c);
            return tokentype = '(';
        }
    }
    else if(c == '[')
    {
        for(*p++ = c; (*p++ = getch()) != ']';)
            ;
        *p = '\0';
        return tokentype = BRACKETS;
    }
    else if(isalpha(c))
    {
        for(*p++ = c; isalnum(c = getch());)
            *p++ = c;
        *p = '\0';
        ungetch(c);
        return tokentype = NAME;
    }
    else
        return tokentype = c;
}

#define BUFSIZE 100

char buf[BUFSIZE];  //buffer for ungetch;
int bufp = 0; //next free position in buf

int getch(void) // get a (possibly pushed-back) character  
{
   return (bufp > 0) ? buf[--bufp] : getchar();
}

void ungetch(int c) // push character back on input
{
    if(bufp >= BUFSIZE)
        printf("ungetch: too many characnters\n");
    else
        buf[bufp++] = c;
}

int posttoken(void)
{
    int nexttype;
    
    nexttype = gettoken();
    pretoken = YES;
    return nexttype;
}

Result:

Exercise 5.18. Make dcl recover from input errors.

Exercise 5.18. Make dcl recover from input errors.

#include <stdio.h>

#include <string.h>

#include <ctype.h>

#define MAXTOKEN 100

#define YES 1

#define NO 0

enum {NAME, PARENS, BRACKETS};

void dcl(void);

void dirdcl(void);

int gettoken(void);

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 out[1000];

int errtoken = NO;

int errbrack = NO;

/* convert declaration to words */

int main()

{

    while(gettoken() != EOF)        //1st token on line

    {

        strcpy(datatype, token);    //is the datatype

        out[0] = '\0';

        dcl();      //parse rest of line

        if(tokentype != '\n')

            printf("syntax error\n");

        printf("%s: %s %s\n", name, out, datatype);

    }

    return 0;

}

/* dcl: parse a declarator */

void dcl(void)

{

    int ns;

    

    for(ns = 0; gettoken() == '*';) //count stars

        ns++;

    dirdcl();

    while(ns-- > 0)

        strcat(out, " pointer to");

}

/* dirdcl: parse a direct declarator */

void dirdcl(void)

{

    int type;

    

    if(tokentype == '(') //(dcl)

    {

        dcl();

        if(tokentype != ')')

        {

            printf("error: missing )\n");

            errtoken = YES;

        }

    }

    else if(tokentype == NAME) //variable name

        strcpy(name, token);

    else

    {

        printf("error: expected name or (dcl)\n");

        errtoken = YES;

    }

    while((type = gettoken()) == PARENS || type == BRACKETS)

        if(type == PARENS)

            strcat(out, " function returning");

        else

        {

            strcat(out, " array");

            strcat(out, token);

            strcat(out, " of");

        }

}

int getch(void);

void ungetch(int c);

int gettoken(void)

{

    int c, getch(void);

    void ungetch(int);

    char *p = token;

    

    if(errtoken == YES)

    {

        errtoken = NO;

        return tokentype;

    }    

    while((c = getch()) == ' ' || c == '\t')

        ;

    if(c == '(')

    {

        if((c = getch()) == ')')

        {

            strcpy(token, "()");

            return tokentype = PARENS;

        }

        else

        {

            ungetch(c);

            return tokentype = '(';

        }

    }

    else if(c == '[')

    {

        for(*p++ = c; *p != ']';)

        {

            *p = getch();

            if(*p != ']')

            {

                if(*p == '\n' || *p == ')' || *p == '(')

                {

                    printf("error: missing ]\n");

                    ungetch(*p);

                    *p = ']';

                }

                else

                    *p++;

            }

        }

        *++p = '\0';

        return tokentype = BRACKETS;

    }

    else if(isalpha(c))

    {

        for(*p++ = c; isalnum(c = getch());)

            *p++ = c;

        *p = '\0';

        ungetch(c);

        return tokentype = NAME;

    }

    else

        return tokentype = c;

}

#define BUFSIZE 100

char buf[BUFSIZE];  //buffer for ungetch;

int bufp = 0; //next free position in bud

int getch(void) // get a (possibly pushed-back) character  

{

   return (bufp > 0) ? buf[--bufp] : getchar();

}

void ungetch(int c) // push character back on input

{

    if(bufp >= BUFSIZE)

        printf("ungetch: too many characnters\n");

    else

        buf[bufp++] = c;

}

Result:

Exercise 5.17. Add a field-searching capability

Exercise 5.17. Add a field-searching capability, so sorting may bee done on fields within lines, each field sorted according to an independent set of options. (The index for this book was sorted with -df for the index category and -n for the page numbers.)


#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

#define MAXLINES 5000 //max lines to be sorted
#define BUFSIZE 5000


char *lineptr[MAXLINES];

int readlines(char *lineptr[], char *buf, int maxlines);
void writelines(char *lineptr[], int nlines, int order);
void sort(void *v[], int left, int right, 
            int (*comp) (void *, void *));
int numcmp(char *s1, char *s2);
int regcmp(char *r1, char *r2);

int numeric, order, reg, dir;
int pos1 = 0;
int pos2 = 0;

/* sort input lines */
int main(int argc, char *argv[])
{
    int nlines; //number of input lines read
    int c, wk; // 1 if numeric sort & order sort
    char buf[BUFSIZE];
    int (*pFunc)(int *);
    numeric = 0;
    order = 0;
    reg = 0;
    dir = 0;
    

    while(--argc > 0 && (c = (*++argv)[0]) == '-' || c == '+')
    {
        if(c == '-' && !isdigit(*(argv[0] +1)))
            while(c = *++argv[0])
                switch(c)
                {
                    case 'd'://directory order
                        dir = 1;
                        break;
                    case 'n': //numerically sort
                        numeric = 1;
                        break;
                    case 'f'://sort upper & lower case together
                        reg = 1;
                        break;
                    case 'r'://sorting in reverse
                        order = 1;
                        break;
                    default:
                        printf("wrong key\n");
                        wk = -1;
                        argc = 1;
                        break;
                }
        else if(c == '-')
            pos2 = atoi(argv[0] + 1);
        else if((pos1=atoi(argv[0] + 1)) < 0)
        {
            printf("ERROR\n");
            exit (1);
        }
    }
    if(argc || pos1 > pos2)
    {
        printf("ERROR\n");
        exit(1);
    }
    else
    {
        if((nlines = readlines(lineptr,buf, MAXLINES)) >= 0)
        {
            if(numeric == 1)
                pFunc = numcmp;
            else if(reg == 1 || dir == 1)
                pFunc = regcmp;
            else
                pFunc = strcmp;        
            sort((void **)lineptr, 0, nlines - 1, 
                (int (*) (void*, void*)) *pFunc);
            writelines(lineptr, nlines, order);
        }
        else
        {
            printf("input too big to sort\n");
            wk = -1;
        }
    }
    return wk;
}



/* sort: sort v[left]...v[right] into increasing order */
void sort(void *v[], int left, int right,
            int (*comp) (void *, void *))
{
    int i, last;
    void swap(void *v[], int i, int j);
    
    if(left >= right) //do nothing if array contains
        return;       //fewer than two elements
    swap(v, left, (left + right)/2);
    last = left;
    for(i = left + 1; i <= right; i++)
        if((*comp) (v[i], v[left]) < 0)
            swap(v, ++last, i);
    swap(v, left, last);
    sort(v, left, last - 1, comp);
    sort(v, last + 1, right, comp);
}

#include <stdlib.h>
#include <math.h>

#define MAXSTR 5000

void sortstr(char *s, char *t, int maxstr);

/* numcmp: compare s1 and s2 numericalli */
int numcmp(char *s1, char *s2)
{
    double v1, v2;
    char str[MAXSTR];
    
    sortstr(s1, str, MAXSTR);    
    v1 = atof(str);
    sortstr(s2, str, MAXSTR);
    v2 = atof(str);
    if(v1 < v2)
        return -1;
    else if(v1 > v2)
        return 1;
    else
        return 0;
}

void sortstr(char *s, char *t, int maxstr)
{
    int i, j, len;
    
    len=strlen(s);
    if(pos2 > 0 && len > pos2)
        len = pos2;
    else if(pos2>0 && len < pos2)
    {
        printf("ERROR\n");
        exit (1);
    }
    for(i = 0, j = pos1; j < len; i++, j++)
        t[i] = s[j];
    t[i] = '\0';
}

void swap(void *v[], int i, int j)
{
    void *temp;
    
    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}

#define MAXLEN 1000 //max lenght of any input line


int getlin(char *, int);

/* readlines: read input lines */
int readlines(char *lineptr[], char *buf, int maxlines)
{
    int len, nlines;

    char line[MAXLEN];
    
    char *p = buf;     
    char *bufstop = buf + BUFSIZE;
    
    nlines = 0;
    while((len = getlin(line, MAXLEN)) > 0)
    {
        if(nlines >= maxlines || p + len > bufstop)
            return -1;
        else
        {
            line[len - 1] = '\0'; //delete newline
            strcpy(p, line);
            lineptr[nlines++] = p;
            p += len;
        }
    }
    return nlines;
}

/* writelines: write output lines */
void writelines(char *lineptr[], int nlines, int order)
{
    int i;
    
    printf("\n");
    if(order == 0)
        for(i = 0; i < nlines; i++)
            printf("%s\n", lineptr[i]);
    else 
        for(i = nlines-1;i >= 0; i--)
            printf("%s\n", lineptr[i]);
}

int getlin(char *l, int lim)
{
    int c;
    char *tmp = l;
    
    for(; --lim > 0 && (c=getchar()) != EOF && c!='\n'; l++)
        *l = c;
    if(c=='\n')
        *l++ = c;
    *l = '\0';
    return l - tmp;
}

int regcmp(char *r1, char *r2)
{
    int i, j, lastpos;
        
    i = j = pos1;
    if(pos2 > 0)
        lastpos = pos2;
    else if((lastpos = strlen(r1)) > strlen(r2))
        lastpos = strlen(r2);
    if(reg == 1 && dir == 0)
    {
        for(;tolower(r1[i]) == tolower(r2[j]) && i < lastpos && j <lastpos; i++, j++)
            if(r1[i] == '\0')
                return 0;
        return tolower(r1[i]) - tolower(r2[j]);
    }
    else if(reg == 0 && dir == 1)
    {
        while(r1[i] == r2[j] && i < lastpos && j < lastpos)
        {
            while(i < lastpos && !isalnum(r1[i]) && r1[i] != '\0' && r1[i] != ' ')
                i++;
            while(j < lastpos && !isalnum(r2[j]) && r2[j] != '\0' && r2[j] != ' ')
                j++;
        }
        if(r1[i] == r2[j] && r1[i] == '\0')
            return 0;
        else
            return r1[i] - r2[j];
    }
    else
    {
        while(r1[i] == r2[j] && i < lastpos && j < lastpos)
        {
            while(i < lastpos && !isalnum(tolower(r1[i])) && r1[i] != '\0' && r1[i] != ' ')
                i++;
            while(j < lastpos && !isalnum(tolower(r2[j])) && r2[j] != '\0' && r2[j] != ' ')
                j++;
        }
        if(tolower(r1[i]) == tolower(r2[j]) && r1[i] == '\0')
            return 0;
        else
            return tolower(r1[i]) - tolower(r2[j]);
    }
}

Result:

Exercise 5.16. Add the -d (``directory order'') option, which makes comparisons only on letters, numbers and blanks.

Exercise 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.


#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define MAXLINES 5000 //max lines to be sorted
#define BUFSIZE 5000


char *lineptr[MAXLINES];

int readlines(char *lineptr[], char *buf, int maxlines);
void writelines(char *lineptr[], int nlines, int order);
void sort(void *v[], int left, int right, 
            int (*comp) (void *, void *));
int numcmp(char *s1, char *s2);
int regcmp(char *r1, char *r2);

int numeric, order, reg, dir;

/* sort input lines */
int main(int argc, char *argv[])
{
    int nlines; //number of input lines read
    int c, wk; 
    char buf[BUFSIZE];
    int (*pFunc)(int *);
    numeric = 0;
    order = 0;
    reg = 0;
    dir = 0;
    

    while(--argc > 0 && (*++argv)[0] == '-')
        while(c = *++argv[0])
            switch(c)
            {
                case 'd'://directory order
                    dir = 1;
                    break;
                case 'n': //numerically sort
                    numeric = 1;
                    break;
                case 'f'://sort upper & lower case together
                    reg = 1;
                    break;
                case 'r'://sorting in reverse
                    order = 1;
                    break;
                default:
                    printf("wrong key\n");
                    wk = -1;
                    argc = 1;
                    break;
            }
    if(argc)
        printf("ERROR\n");
    else
    {
        if((nlines = readlines(lineptr,buf, MAXLINES)) >= 0)
        {
            if(numeric == 1)
                pFunc = numcmp;
            else if(reg == 1 || dir == 1)
                pFunc = regcmp;
            else
                pFunc = strcmp;        
            sort((void **)lineptr, 0, nlines - 1, 
                (int (*) (void*, void*)) *pFunc);
            writelines(lineptr, nlines, order);
        }
        else
        {
            printf("input too big to sort\n");
            wk = -1;
        }
    }
    return wk;
}



/* sort: sort v[left]...v[right] into increasing order */
void sort(void *v[], int left, int right,
            int (*comp) (void *, void *))
{
    int i, last;
    void swap(void *v[], int i, int j);
    
    if(left >= right) //do nothing if array contains
        return;       //fewer than two elements
    swap(v, left, (left + right)/2);
    last = left;
    for(i = left + 1; i <= right; i++)
        if((*comp) (v[i], v[left]) < 0)
            swap(v, ++last, i);
    swap(v, left, last);
    sort(v, left, last - 1, comp);
    sort(v, last + 1, right, comp);
}

#include <stdlib.h>

/* numcmp: compare s1 and s2 numericalli */
int numcmp(char *s1, char *s2)
{
    double v1, v2;
    
    v1 = atof(s1);
    v2 = atof(s2);
    if(v1 < v2)
        return -1;
    else if(v1 > v2)
        return 1;
    else
        return 0;
}

void swap(void *v[], int i, int j)
{
    void *temp;
    
    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}

#define MAXLEN 1000 //max lenght of any input line


int getlin(char *, int);

/* readlines: read input lines */
int readlines(char *lineptr[], char *buf, int maxlines)
{
    int len, nlines;

    char line[MAXLEN];
    
    char *p = buf;     
    char *bufstop = buf + BUFSIZE;
    
    nlines = 0;
    while((len = getlin(line, MAXLEN)) > 0)
    {
        if(nlines >= maxlines || p + len > bufstop)
            return -1;
        else
        {
            line[len - 1] = '\0'; //delete newline
            strcpy(p, line);
            lineptr[nlines++] = p;
            p += len;
        }
    }
    return nlines;
}

/* writelines: write output lines */
void writelines(char *lineptr[], int nlines, int order)
{
    int i;
    
    printf("\n");
    if(order == 0)
        for(i = 0; i < nlines; i++)
            printf("%s\n", lineptr[i]);
    else 
        for(i = nlines-1;i >= 0; i--)
            printf("%s\n", lineptr[i]);
}

int getlin(char *l, int lim)
{
    int c;
    char *tmp = l;
    
    for(; --lim > 0 && (c=getchar()) != EOF && c!='\n'; l++)
        *l = c;
    if(c=='\n')
        *l++ = c;
    *l = '\0';
    return l - tmp;
}

int regcmp(char *r1, char *r2)
{
    if(reg == 1 && dir == 0)
    {
        for(;tolower(*r1) == tolower(*r2); r1++, r2++)
            if(*r1 == '\0')
                return 0;
        return tolower(*r1) - tolower(*r2);
    }
    else if(reg == 0 && dir == 1)
    {
        while(*r1 == *r2)
        {
            while(!isalnum(*r1) && *r1 != '\0' && *r2 != ' ')
                r1++;
            while(!isalnum(*r2) && *r1 != '\0' && *r2 != ' ')
                r2++;
        }
        if(*r1 == *r2 && *r1 == '\0')
            return 0;
        else
            return *r1 - *r2;
    }
    else
    {
        while(*r1 == *r2)
        {
            while(!isalnum(tolower(*r1)) && *r1 != '\0' && *r2 != ' ')
                r1++;
            while(!isalnum(tolower(*r2)) && *r1 != '\0' && *r2 != ' ')
                r2++;
        }
        if(tolower(*r1) == tolower(*r2) && *r1 == '\0')
            return 0;
        else
            return tolower(*r1) - tolower(*r2);
    }
}

Exercise 5.15. Add the option -f to fold upper and lower case together

Exercise 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.


#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define MAXLINES 5000 //max lines to be sorted
#define BUFSIZE 5000

char *lineptr[MAXLINES];

int readlines(char *lineptr[], char *buf, int maxlines);
void writelines(char *lineptr[], int nlines, int order);
void sort(void *v[], int left, int right, 
            int (*comp) (void *, void *));
int numcmp(char *s1, char *s2);
int regcmp(char *r1, char *r2);

/* sort input lines */
int main(int argc, char *argv[])
{
    int nlines; //number of input lines read
    int numeric, order, reg, c, wk; // 1 if numeric sort & order sort
    char buf[BUFSIZE];
    int (*pFunc)(int *);
    
    numeric = 0;
    order = 0;
    reg = 0;
    direct
    while(--argc > 0 && (*++argv)[0] == '-')
        while(c = *++argv[0])
            switch(c)
            {
                case 'd'://directory order
                    
                case 'n': //numerically sort
                    numeric = 1;
                    break;
                case 'f'://sort upper & lower case together
                    reg = 1;
                    break;
                case 'r'://sorting in reverse
                    order = 1;
                    break;
                default:
                    printf("wrong key\n");
                    wk = -1;
                    argc = 1;
                    break;
            }
    if(argc)
        printf("ERROR\n");
    else
    {
        if((nlines = readlines(lineptr,buf, MAXLINES)) >= 0)
        {
            if(numeric == 1)
                pFunc = numcmp;
            else if(reg == 1)
                pFunc = regcmp;
            else
                pFunc = strcmp;        
            sort((void **)lineptr, 0, nlines - 1, 
                (int (*) (void*, void*)) *pFunc);
            writelines(lineptr, nlines, order);
        }
        else
        {
            printf("input too big to sort\n");
            wk = -1;
        }
    }
    return wk;
}



/* sort: sort v[left]...v[right] into increasing order */
void sort(void *v[], int left, int right,
            int (*comp) (void *, void *))
{
    int i, last;
    void swap(void *v[], int i, int j);
    
    if(left >= right) //do nothing if array contains
        return;       //fewer than two elements
    swap(v, left, (left + right)/2);
    last = left;
    for(i = left + 1; i <= right; i++)
        if((*comp) (v[i], v[left]) < 0)
            swap(v, ++last, i);
    swap(v, left, last);
    sort(v, left, last - 1, comp);
    sort(v, last + 1, right, comp);
}

#include <stdlib.h>

/* numcmp: compare s1 and s2 numericalli */
int numcmp(char *s1, char *s2)
{
    double v1, v2;
    
    v1 = atof(s1);
    v2 = atof(s2);
    if(v1 < v2)
        return -1;
    else if(v1 > v2)
        return 1;
    else
        return 0;
}

void swap(void *v[], int i, int j)
{
    void *temp;
    
    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}

#define MAXLEN 1000 //max lenght of any input line


int getlin(char *, int);

/* readlines: read input lines */
int readlines(char *lineptr[], char *buf, int maxlines)
{
    int len, nlines;

    char line[MAXLEN];
    
    char *p = buf;     
    char *bufstop = buf + BUFSIZE;
    
    nlines = 0;
    while((len = getlin(line, MAXLEN)) > 0)
    {
        if(nlines >= maxlines || p + len > bufstop)
            return -1;
        else
        {
            line[len - 1] = '\0'; //delete newline
            strcpy(p, line);
            lineptr[nlines++] = p;
            p += len;
        }
    }
    return nlines;
}

/* writelines: write output lines */
void writelines(char *lineptr[], int nlines, int order)
{
    int i;
    
    printf("\n");
    if(order == 0)
        for(i = 0; i < nlines; i++)
            printf("%s\n", lineptr[i]);
    else 
        for(i = nlines-1;i >= 0; i--)
            printf("%s\n", lineptr[i]);
}

int getlin(char *l, int lim)
{
    int c;
    char *tmp = l;
    
    for(; --lim > 0 && (c=getchar()) != EOF && c!='\n'; l++)
        *l = c;
    if(c=='\n')
        *l++ = c;
    *l = '\0';
    return l - tmp;
}

int regcmp(char *r1, char *r2)
{
    for(;tolower(*r1) == tolower(*r2); r1++, r2++)
        if(*r1 == '\0')
            return 0;
    return tolower(*r1) - tolower(*r2);
}

Result: