「C4_koizumi」の編集履歴（バックアップ）一覧はこちら

「C4_koizumi」(2010/01/15 (金) 00:01:32) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

#comment()

&bold(){Exersixe 4-10.}An alternate organization uses getline to read an entire input line; this makes getch and ungetch unnecessary. Revise the calculator to use this approach.
#highlight(linenumber.c){{
//ぐちゃぐちゃですみません。。
//一行入力をバッファに取り込み、それをトークンに変換しながらキューに入れていき、
//トークンを要求されたら、キューから一つ取り出して返すようにしています。
#include<stdio.h>
#include<stdlib.h> //for atof
#include<ctype.h> //for getop
#include<math.h>

static enum { MAXOP = 100, NUMBER = 0, OP = 1, COM = 2, VAL = 3, OTHER = 4, MAXLINE = 100, MAXVAL = 100, BUFSIZE = 100, MAXSIZE = 100, IDT_SIZE = 13};

static int getop(char []);
static void push(double);
static double pop();

static int getSp(void);
static void setSp(int);

int pr4_10()
{
    int type;
    double op1,op2;
    double tmp1, tmp2;
    char s[MAXOP];
    double val[26] = {0};
    double recentVal;

    while((type = getop(s)) != EOF) {
        //printf("type: %d\n", type);
        //printf("s: %s\n", s);
        switch (type) {
        case NUMBER:
            push(atof(s));
            break;
        case OP:
            if(!strcmp(s, "sin")) push(sin(pop()));
            else if(!strcmp(s, "cos")) push(cos(pop()));
            else if(!strcmp(s, "tan")) push(tan(pop()));
            else if(!strcmp(s, "exp")) push(exp(pop()));
            break;
        case COM:
            if(!strcmp(s, "print")) { //print the top element of the stack without popping
                 tmp1 = pop();
                 push(tmp1);
                 printf("\t%.8g\n", tmp1);
            }
            else if(!strcmp(s, "dup")) { //duplicate the top element of the stack
                tmp1 = pop();
                push(tmp1);
                push(tmp1);
            }
            else if(!strcmp(s, "swap")) { //swap the top two elements
                tmp1 = pop();
                tmp2 = pop();
                push(tmp1);
                push(tmp2);
            }
            else if(!strcmp(s, "clear")) { //clear the stack
                setSp(0);
            }
            else if(!strcmp(s, "set")) { //set number to variable
                double value = pop();
                int addr = (int)pop();
                val[addr] = value;
                push(value);
            }
            else if(!strcmp(s, "get")) { //get number of variable
                int addr = (int)pop();
                push(val[addr]);
                recentVal = val[addr]; //set recentVal
            }
            break;
        case 'a': case 'b': case 'c': case 'd': case 'e':
            push(type-'a'); //set addr
            break;
        case '+':
            push(pop() + pop());
            break;
        case '*':
            push(pop() * pop());
            break;
        case '-':
            op2 = pop();
            push(pop() - op2);
            break;
        case '/':
            op2 = pop();
            if(op2 != 0.0)
                push(pop() / op2);
            else
                printf("error: zero divisor\n");
            break;
        case '%':
            op2 = pop();
            if(op2 != 0.0)
                push(fmod(pop(), op2));
            else
                printf("error: zero modulus\n");
            break;
        case '\n':
            printf("\t%.8g\n", pop());
            break;
        default:
            printf("error: unknown command %s\n", s);
            break;
        }
    }
    return 0;
}

static int sp = 0;
static double val[MAXVAL];

static int getSp(void)
{
    return sp;
}

static void setSp(int val)
{
    sp = val;
}

// push: push f to val of stack
void push(double f)
{
    if (sp < MAXVAL)
        val[sp++] = f;
    else
        printf("error: stack full, can't push %g\n", f);
}

//pop: pop the top of val of stack and return
double pop(void)
{
    if(sp > 0)
        return val[--sp];
    else {
        printf("error: stack empty\n");
        return 0.0;
    }
}

//ID_entry
typedef struct ID_entry {
    char *name_ptr;
    int len;
    struct ID_entry *next;
} ID_entry;
static ID_entry *IDTable[IDT_SIZE];

static int hash(char *sp)
{
    unsigned h, g;

    for(h = 0; *sp != '\0'; sp++) {
        h = (h << 4) + (unsigned)(*sp);
        if (g = h & 0xf0000000)
            h = (h ^ g>>24) ^ g;
    }
    return (h % IDT_SIZE);
}

char *IDentry(char *sp, int len)
{
    int hval = hash(sp);
    ID_entry *np;

    for (np = IDTable[hval]; np != NULL; np = np->next)
        if((np->len) == len && strcmp(np->name_ptr, sp) == 0)
            return np->name_ptr;
    np = (ID_entry *)malloc(sizeof(ID_entry));
    np->name_ptr = (char *)malloc(len+1);
    np->len = len;
    np->next = IDTable[hval];
    IDTable[hval] = np;
    return strcpy(np->name_ptr, sp);
}

//queue of Token
typedef struct _token{
    int symbol;
    char *name_ptr;
} Token;
Token queue[MAXSIZE];
int head = 0, tail = 0;

int queuein(int sym, char *name)
{
    if((tail+1) % MAXSIZE != head) {
        queue[tail].symbol = sym;
        queue[tail].name_ptr = name;
        tail++;
        tail = tail % MAXSIZE;
        return 0;
    }
    else
        return -1;
}

int queueout(int *sym, char **name)
{
    if (tail != head) {
        int i,n;
        n = strlen(queue[head].name_ptr);
        *sym = queue[head].symbol;
        *name = queue[head].name_ptr;
        head++;
        head = head % MAXSIZE;
        return 0;
    }
    else
        return -1;
}

static int getline(char s[], int lim)
{
    int c, i;

    i = 0;
    while(--lim > 0 && (c =getchar()) != EOF && c !='\n')
        s[i++] = c;
    if (c == '\n')
        s[i++] = c;
    s[i] = '\0';
    return i;
}

//getop: get next operator or number of operand
int getop(char s[])
{
    int i, c, next, index;
    int n;
    int sym;
    char tmp[MAXLINE];
    char *id;
    char buf[MAXLINE];

    if(queueout(&sym, &id) != -1) { //out queue
        if(sym == OTHER) {
            return id[0];
        } else {
            strcpy(s, id);
            return sym;
        }
    } else { //set queue
        //一行よみこみ、トークンの列にする
        n = getline(buf, BUFSIZE); //get input size

        if(n == 0) { //input EOF only
            return EOF;
        }

        for(index = 0; index < n; index++) {
            int tmpptr = 0;
            for(; (buf[index] == ' ' || buf[index] == '\t') && index < n; index++) //skip space and tab
                ;
            while((c = buf[index]) != ' ' && c != '\t' && c != '\n' && c != '\0' && c != EOF) {
                tmp[tmpptr++] = buf[index++];
            }
            if(c == '\n') {
                if(tmpptr == 0) { //'\n'　だけの場合
                    tmp[tmpptr++] = '\n';
                    tmp[tmpptr] = '\0';
                    id = IDentry(tmp, tmpptr+1); //名前表にとうろく
                    queuein(OTHER, id);
                    continue;
                } else { //別の文字列に'\n'がついていた場合
                    index--; //for next loop
                }
            } else if(c == EOF) {
                tmp[tmpptr++] = EOF;
                tmp[tmpptr] = '\0';
                id = IDentry(tmp, tmpptr+1);
                queuein(OTHER, id);
                continue;
            }

            tmp[tmpptr] = '\0';

            //only one alphabet
            if (!isdigit(tmp[0]) && tmpptr == 1) {
                id = IDentry(tmp, tmpptr+1);
                queuein(OTHER, id); //not number
                continue;
            }

            //command
            if(!strcmp(tmp, "dup") || !strcmp(tmp, "print") || !strcmp(tmp, "swap") ||
               !strcmp(tmp, "get") || !strcmp(tmp, "set")   || !strcmp(tmp, "clear")) {
                id = IDentry(tmp, tmpptr+1);
                queuein(COM, id);
                continue;
            }

            //operator
            if(!strcmp(tmp, "+")  || !strcmp(tmp, "-") || !strcmp(tmp, "*") ||
               !strcmp(tmp, "/")  || !strcmp(tmp, "%")) {
                id = IDentry(tmp, tmpptr+1);
                queuein(OTHER, id);
                continue;
            }
            if(!strcmp(tmp, "sin") || !strcmp(tmp, "cos") || !strcmp(tmp, "tan") ||
               !strcmp(tmp, "exp") || !strcmp(tmp, "set")   || !strcmp(tmp, "clear")) {
                id = IDentry(tmp, tmpptr+1);
                queuein(OP, id);
                continue;
            }

            //number
            id = IDentry(tmp, tmpptr+1);
            queuein(NUMBER, id);
            continue;
        }

        //トークンの値を一つ返す。
        queueout(&sym, &id);
        if(sym == OTHER) {
            return id[0];
        } else {
            int i, size;
            size = strlen(id);
            for(i = 0; i <= size; i++) { s[i] = id[i]; }
            return sym;
        }
    }
}
}}
&bold(){Exersixe 4-11.}Modify getop so that it doesn't need to use ungetch. Hint: use an internal static variable. 
#highlight(linenumber.c){{
}}
&bold(){Exersixe 4-12.}Adapt the ideas of printd to write a recursive version of itoa ; that is, convert an integer into a string by calling a recursive routine. 
#highlight(linenumber.c){{
}}
&bold(){Exersixe 4-13.}Write a recursive version of the function reverse(s) , which reverses the string s in place. 
#highlight(linenumber.c){{
}}
&bold(){Exersixe 4-14.}Define a macro swap(t,x,y) that interchanges two arguments of type t . (Block structure will help.) 
#highlight(linenumber.c){{
}}

#comment()

&bold(){Exersixe 4-10.}An alternate organization uses getline to read an entire input line; this makes getch and ungetch unnecessary. Revise the calculator to use this approach.
#highlight(linenumber.c){{
//ぐちゃぐちゃですみません。。
//一行入力をバッファに取り込み、それをトークンに変換しながらキューに入れていき、
//トークンを要求されたら、キューから一つ取り出して返すようにしています。
#include<stdio.h>
#include<stdlib.h> //for atof
#include<ctype.h> //for getop
#include<math.h>

static enum { MAXOP = 100, NUMBER = 0, OP = 1, COM = 2, VAL = 3, OTHER = 4, MAXLINE = 100, MAXVAL = 100, BUFSIZE = 100, MAXSIZE = 100, IDT_SIZE = 13};

static int getop(char []);
static void push(double);
static double pop();

static int getSp(void);
static void setSp(int);

int pr4_10()
{
    int type;
    double op1,op2;
    double tmp1, tmp2;
    char s[MAXOP];
    double val[26] = {0};
    double recentVal;

    while((type = getop(s)) != EOF) {
        //printf("type: %d\n", type);
        //printf("s: %s\n", s);
        switch (type) {
        case NUMBER:
            push(atof(s));
            break;
        case OP:
            if(!strcmp(s, "sin")) push(sin(pop()));
            else if(!strcmp(s, "cos")) push(cos(pop()));
            else if(!strcmp(s, "tan")) push(tan(pop()));
            else if(!strcmp(s, "exp")) push(exp(pop()));
            break;
        case COM:
            if(!strcmp(s, "print")) { //print the top element of the stack without popping
                 tmp1 = pop();
                 push(tmp1);
                 printf("\t%.8g\n", tmp1);
            }
            else if(!strcmp(s, "dup")) { //duplicate the top element of the stack
                tmp1 = pop();
                push(tmp1);
                push(tmp1);
            }
            else if(!strcmp(s, "swap")) { //swap the top two elements
                tmp1 = pop();
                tmp2 = pop();
                push(tmp1);
                push(tmp2);
            }
            else if(!strcmp(s, "clear")) { //clear the stack
                setSp(0);
            }
            else if(!strcmp(s, "set")) { //set number to variable
                double value = pop();
                int addr = (int)pop();
                val[addr] = value;
                push(value);
            }
            else if(!strcmp(s, "get")) { //get number of variable
                int addr = (int)pop();
                push(val[addr]);
                recentVal = val[addr]; //set recentVal
            }
            break;
        case 'a': case 'b': case 'c': case 'd': case 'e':
            push(type-'a'); //set addr
            break;
        case '+':
            push(pop() + pop());
            break;
        case '*':
            push(pop() * pop());
            break;
        case '-':
            op2 = pop();
            push(pop() - op2);
            break;
        case '/':
            op2 = pop();
            if(op2 != 0.0)
                push(pop() / op2);
            else
                printf("error: zero divisor\n");
            break;
        case '%':
            op2 = pop();
            if(op2 != 0.0)
                push(fmod(pop(), op2));
            else
                printf("error: zero modulus\n");
            break;
        case '\n':
            printf("\t%.8g\n", pop());
            break;
        default:
            printf("error: unknown command %s\n", s);
            break;
        }
    }
    return 0;
}

static int sp = 0;
static double val[MAXVAL];

static int getSp(void)
{
    return sp;
}

static void setSp(int val)
{
    sp = val;
}

// push: push f to val of stack
void push(double f)
{
    if (sp < MAXVAL)
        val[sp++] = f;
    else
        printf("error: stack full, can't push %g\n", f);
}

//pop: pop the top of val of stack and return
double pop(void)
{
    if(sp > 0)
        return val[--sp];
    else {
        printf("error: stack empty\n");
        return 0.0;
    }
}

//ID_entry
typedef struct ID_entry {
    char *name_ptr;
    int len;
    struct ID_entry *next;
} ID_entry;
static ID_entry *IDTable[IDT_SIZE];

static int hash(char *sp)
{
    unsigned h, g;

    for(h = 0; *sp != '\0'; sp++) {
        h = (h << 4) + (unsigned)(*sp);
        if (g = h & 0xf0000000)
            h = (h ^ g>>24) ^ g;
    }
    return (h % IDT_SIZE);
}

char *IDentry(char *sp, int len)
{
    int hval = hash(sp);
    ID_entry *np;

    for (np = IDTable[hval]; np != NULL; np = np->next)
        if((np->len) == len && strcmp(np->name_ptr, sp) == 0)
            return np->name_ptr;
    np = (ID_entry *)malloc(sizeof(ID_entry));
    np->name_ptr = (char *)malloc(len+1);
    np->len = len;
    np->next = IDTable[hval];
    IDTable[hval] = np;
    return strcpy(np->name_ptr, sp);
}

//queue of Token
typedef struct _token{
    int symbol;
    char *name_ptr;
} Token;
Token queue[MAXSIZE];
int head = 0, tail = 0;

int queuein(int sym, char *name)
{
    if((tail+1) % MAXSIZE != head) {
        queue[tail].symbol = sym;
        queue[tail].name_ptr = name;
        tail++;
        tail = tail % MAXSIZE;
        return 0;
    }
    else
        return -1;
}

int queueout(int *sym, char **name)
{
    if (tail != head) {
        int i,n;
        n = strlen(queue[head].name_ptr);
        *sym = queue[head].symbol;
        *name = queue[head].name_ptr;
        head++;
        head = head % MAXSIZE;
        return 0;
    }
    else
        return -1;
}

static int getline(char s[], int lim)
{
    int c, i;

    i = 0;
    while(--lim > 0 && (c =getchar()) != EOF && c !='\n')
        s[i++] = c;
    if (c == '\n')
        s[i++] = c;
    s[i] = '\0';
    return i;
}

//getop: get next operator or number of operand
int getop(char s[])
{
    int i, c, next, index;
    int n;
    int sym;
    char tmp[MAXLINE];
    char *id;
    char buf[MAXLINE];

    if(queueout(&sym, &id) != -1) { //out queue
        if(sym == OTHER) {
            return id[0];
        } else {
            strcpy(s, id);
            return sym;
        }
    } else { //set queue
        //一行よみこみ、トークンの列にする
        n = getline(buf, BUFSIZE); //get input size

        if(n == 0) { //input EOF only
            return EOF;
        }

        for(index = 0; index < n; index++) {
            int tmpptr = 0;
            for(; (buf[index] == ' ' || buf[index] == '\t') && index < n; index++) //skip space and tab
                ;
            while((c = buf[index]) != ' ' && c != '\t' && c != '\n' && c != '\0' && c != EOF) {
                tmp[tmpptr++] = buf[index++];
            }
            if(c == '\n') {
                if(tmpptr == 0) { //'\n'　だけの場合
                    tmp[tmpptr++] = '\n';
                    tmp[tmpptr] = '\0';
                    id = IDentry(tmp, tmpptr+1); //名前表にとうろく
                    queuein(OTHER, id);
                    continue;
                } else { //別の文字列に'\n'がついていた場合
                    index--; //for next loop
                }
            } else if(c == EOF) {
                tmp[tmpptr++] = EOF;
                tmp[tmpptr] = '\0';
                id = IDentry(tmp, tmpptr+1);
                queuein(OTHER, id);
                continue;
            }

            tmp[tmpptr] = '\0';

            //only one alphabet
            if (!isdigit(tmp[0]) && tmpptr == 1) {
                id = IDentry(tmp, tmpptr+1);
                queuein(OTHER, id); //not number
                continue;
            }

            //command
            if(!strcmp(tmp, "dup") || !strcmp(tmp, "print") || !strcmp(tmp, "swap") ||
               !strcmp(tmp, "get") || !strcmp(tmp, "set")   || !strcmp(tmp, "clear")) {
                id = IDentry(tmp, tmpptr+1);
                queuein(COM, id);
                continue;
            }

            //operator
            if(!strcmp(tmp, "+")  || !strcmp(tmp, "-") || !strcmp(tmp, "*") ||
               !strcmp(tmp, "/")  || !strcmp(tmp, "%")) {
                id = IDentry(tmp, tmpptr+1);
                queuein(OTHER, id);
                continue;
            }
            if(!strcmp(tmp, "sin") || !strcmp(tmp, "cos") || !strcmp(tmp, "tan") ||
               !strcmp(tmp, "exp") || !strcmp(tmp, "set")   || !strcmp(tmp, "clear")) {
                id = IDentry(tmp, tmpptr+1);
                queuein(OP, id);
                continue;
            }

            //number
            id = IDentry(tmp, tmpptr+1);
            queuein(NUMBER, id);
            continue;
        }

        //トークンの値を一つ返す。
        queueout(&sym, &id);
        if(sym == OTHER) {
            return id[0];
        } else {
            int i, size;
            size = strlen(id);
            for(i = 0; i <= size; i++) { s[i] = id[i]; }
            return sym;
        }
    }
}
}}
&bold(){Exersixe 4-11.}Modify getop so that it doesn't need to use ungetch. Hint: use an internal static variable. 
#highlight(linenumber.c){{
偶然ungetchを使わずに組んでいたので、4-10のプログラムと同様です。
}}
&bold(){Exersixe 4-12.}Adapt the ideas of printd to write a recursive version of itoa ; that is, convert an integer into a string by calling a recursive routine. 
#highlight(linenumber.c){{
}}
&bold(){Exersixe 4-13.}Write a recursive version of the function reverse(s) , which reverses the string s in place. 
#highlight(linenumber.c){{
}}
&bold(){Exersixe 4-14.}Define a macro swap(t,x,y) that interchanges two arguments of type t . (Block structure will help.) 
#highlight(linenumber.c){{
}}