Полезная информация

Server for Information Technologies Сервер поддерживается
Центром Информационных Технологий
(095) 932-9212, 932-9213, 939-0783
E-mail: info@citforum.ru
Сервер содержит море(!) аналитической информации CIT Forum CD-ROM

7.60.

Разработайте простую версию препроцессора для обработки операторов #include. В качестве прототипа такой программы можно рассматривать такую (она понимает директивы вида #include имяфайла - без <> или "").

    #include <stdio.h>
    #include <string.h>
    #include <errno.h>
    char KEYWORD[] = "#include ";   /* with a trailing space char */
    void process(char *name, char *from){
            FILE *fp;
            char buf[4096];
            if((fp = fopen(name, "r")) == NULL){
                    fprintf(stderr, "%s: cannot read \"%s\", %s\n",
                                     from, name, strerror(errno));
                    return;
            }
            while(fgets(buf, sizeof buf, fp) != NULL){
                    if(!strncmp(buf, KEYWORD, sizeof KEYWORD - 1)){
                            char *s;
                            if((s = strchr(buf, '\n')) != NULL) *s = '\0';
                            fprintf(stderr, "%s: including %s\n",
                                             name, s = buf + sizeof KEYWORD - 1);
                            process(s, name);
                    } else  fputs(buf, stdout);
            }
            fclose(fp);
    }
    int main(int ac, char *av[]){
            int i;
            for(i=1; i < ac; i++)
                    process(av[i], "MAIN");
            return 0;
    }

7.61.

Разработайте простую версию препроцессора для обработки операторов #define. Сначала реализуйте макросы без аргументов. Напишите обработчик макросов вида

    #macro имя(аргу,менты)
      тело макроса - можно несколько строк
    #endm

7.62.

Напишите программу, обрабатывающую определения #ifdef, #else, #endif. Учтите, что эти директивы могут быть вложенными:

    #ifdef    A
    # ifdef   B
       ...             /*  defined(A) && defined(B) */
    # endif /*B*/
       ...             /*  defined(A) */
    #else   /*not A*/
       ...             /* !defined(A) */
    # ifdef   C
       ...             /* !defined(A) && defined(C) */
    # endif /*C*/
    #endif  /*A*/

7.63.

Составьте программу моделирования простейшего калькулятора, который считывает в каждой строчке по одному числу (возможно со знаком) или по одной операции сложения или умножения, осуществляет операцию и выдает результат.

7.64.

Составьте программу-калькулятор, которая производит операции сложения, вычитания, умножения, деления; операнды и знак арифметической операции являются строковыми аргументами функции main.

7.65.

Составьте программу, вычисляющую значение командной строки, представляющей собой обратную польскую запись арифметического выражения. Например, 20 10 5 + * вычисляется как 20 * (10 + 5) .

7.66.

Составьте функции работы со стеком:

Используйте два варианта: стек-массив и стек-список.

7.67.

Составьте программу, которая использует функции работы со стеком для перевода арифметических выражений языка Си в обратную польскую запись.

    /*#!/bin/cc $* -lm
     * Калькулятор. Иллюстрация алгоритма превращения выражений
     * в польскую запись по методу приоритетов.
     */
    #include <stdio.h>
    #include <stdlib.h> /* extern double atof();            */
    #include <math.h>   /* extern double sin(),  ...        */
    #include <ctype.h>  /* isdigit(), isalpha(), ...        */
    #include <setjmp.h> /* jmp_buf                          */
    jmp_buf AGAIN;             /* контрольная точка */
    err(n){ longjmp(AGAIN,n);} /* прыгнуть в контрольную точку */
    /* ВЫЧИСЛИТЕЛЬ --------------------------------------- */
    /* Если вместо помещения операндов в стек stk[] просто
     * печатать операнды, а вместо выполнения операций над
     * стеком просто печатать операции, мы получим "польскую"
     * запись выражения:
     *      a+b       ->      a b +
     *      (a+b)*c   ->      a b + c *
     *      a + b*c   ->      a b c * +
     */
    /* стек вычислений */
    #define MAXDEPTH 20 /* глубина стеков */
    int sp;             /* указатель стека (stack pointer) */
    double stk[MAXDEPTH];
    double dpush(d) double d; /* занести число в стек */
    {
       if( sp == MAXDEPTH ){ printf("Стек операндов полон\n");err(1);}
       else return( stk[sp++] = d );
    }
    double dpop(){            /* взять вершину стека */
       if( !sp ){ printf("Стек операндов пуст\n"); err(2); }
       else return stk[--sp];
    }
    static double r,p; /* вспомогательные регистры */
    void add()    { dpush( dpop() + dpop()); }
    void mult()   { dpush( dpop() * dpop()); }
    void sub()    { r = dpop(); dpush( dpop() - r); }
    void divide() { r = dpop();
      if(r == 0.0){ printf("Деление на 0\n"); err(3); }
      dpush( dpop() / r );
    }
    void pwr() { r = dpop(); dpush( pow( dpop(), r )); }
    void dup() { dpush( dpush( dpop())); }
    void xchg(){ r = dpop(); p = dpop(); dpush(r); dpush(p); }
    void neg() { dpush( - dpop()); }
    void dsin(){ dpush( sin( dpop())); }
    void dcos(){ dpush( cos( dpop())); }
    void dexp(){ dpush( exp( dpop())); }
    void dlog(){ dpush( log( dpop())); }
    void dsqrt(){ dpush( sqrt( dpop())); }
    void dsqr(){ dup(); mult(); }
    /* M_PI и M_E определены в <math.h> */
    void pi()  { dpush( M_PI /* число пи */ ); }
    void e()   { dpush( M_E  /* число e  */ ); }
    void prn() { printf("%g\n", dpush( dpop())); }
    void printstk(){
      if( !sp ){ printf("Стек операндов пуст\n"); err(4);}
      while(sp) printf("%g ", dpop());
      putchar('\n');
    }
    /* КОМПИЛЯТОР ---------------------------------------- */
    /* номера лексем */
    #define END        (-3)         /* = */
    #define NUMBER     (-2)         /* число */
    #define BOTTOM      0           /* псевдолексема "дно стека" */
    #define OPENBRACKET   1         /* (  */
    #define FUNC          2         /* f( */
    #define CLOSEBRACKET  3         /* )  */
    #define COMMA         4         /* ,  */
    #define PLUS          5         /* +  */
    #define MINUS         6         /* -  */
    #define MULT          7         /* *  */
    #define DIV           8         /* /  */
    #define POWER         9         /* ** */
    /* Приоритеты */
    #define NOTDEF    333   /* не определен */
    #define INFINITY 3000   /* бесконечность */
    /* Стек транслятора */
    typedef struct _opstack {
            int cop;        /* код операции */
            void (*f)();    /* "отложенное" действие */
    } opstack;
    int osp;        /* operations stack pointer */
    opstack ost[MAXDEPTH];
    void push(n, func) void (*func)();
    {
       if(osp == MAXDEPTH){ printf("Стек операций полон\n");err(5);}
       ost[osp].cop = n;  ost[osp++].f = func;
    }
    int pop(){
       if( !osp ){ printf("Стек операций пуст\n"); err(6); }
       return ost[--osp].cop;
    }
    int top(){
       if( !osp ){ printf("Стек операций пуст\n"); err(7); }
       return ost[osp-1].cop;
    }
    void (*topf())(){
       return ost[osp-1].f;
    }
    #define drop()          (void)pop()
    void nop(){ printf( "???\n" ); } /* no operation */
    void obr_err(){ printf( "Не хватает )\n" ); err(8); }
    /* Таблица приоритетов */
    struct synt{
            int inp_prt;    /* входной приоритет     */
            int stk_prt;    /* стековый приоритет    */
            void (*op)();   /* действие над стеком вычислений */
    } ops[] = {
      /* BOTTOM       */  {NOTDEF,   -1,     nop    },
      /* OPENBRACKET  */  {INFINITY,  0,     obr_err},
      /* FUNC         */  {INFINITY,  0,     obr_err},
      /* CLOSEBRACKET */  {1,        NOTDEF, nop    },  /* NOPUSH */
      /* COMMA        */  {1,        NOTDEF, nop    },  /* NOPUSH */
      /* PLUS         */  {1,         1,     add    },
      /* MINUS        */  {1,         1,     sub    },
      /* MULT         */  {2,         2,     mult   },
      /* DIV          */  {2,         2,     divide },
      /* POWER        */  {3,         3,     pwr    }
    };
    #define stkprt(i)    ops[i].stk_prt
    #define inpprt(i)    ops[i].inp_prt
    #define perform(i) (*ops[i].op)()
    /* значения, заполняемые лексическим анализатором */
    double value; void (*fvalue)();
    int tprev;  /* предыдущая лексема */
    /* Транслятор в польскую запись + интерпретатор */
    void reset(){ sp = osp = 0; push(BOTTOM, NULL); tprev = END;}
    void calc(){
      int t;
      do{
            if( setjmp(AGAIN))
                    printf( "Стеки после ошибки сброшены\n" );
            reset();
            while((t = token()) != EOF && t != END){
                    if(t == NUMBER){
                            if(tprev == NUMBER){
                                 printf("%g:Два числа подряд\n",value);
                                 err(9);
                            }
                            /* любое число просто заносится в стек */
                            tprev = t; dpush(value); continue;
                    }
                    /* иначе - оператор */
                    tprev = t;
            /* Выталкивание и выполнение операций со стека */
                    while(inpprt(t) <= stkprt( top()) )
                            perform( pop());
            /* Сокращение или подмена скобок */
                    if(t == CLOSEBRACKET){
                            if( top() == OPENBRACKET || top() == FUNC ){
                                    void (*ff)() = topf();
                                    drop(); /* схлопнуть скобки */
                                    /* обработка функции */
                                    if(ff)        (*ff)();
                            }else{ printf( "Не хватает (\n"); err(10); }
                    }
            /* Занесение операций в стек (кроме NOPUSH-операций) */
                    if(t != CLOSEBRACKET && t != COMMA)
                            push(t,   t == FUNC ? fvalue : NULL );
            }
            if( t != EOF ){
              /* Довыполнить оставшиеся операции */
                while( top() != BOTTOM )
                    perform( pop());
                printstk();     /* печать стека вычислений (ответ) */
            }
      } while (t != EOF);
    }
    /* Лексический анализатор ---------------------------- */
    extern void getn(), getid(), getbrack();
    int token(){    /* прочесть лексему */
            int c;
            while((c = getchar())!= EOF && (isspace(c) || c == '\n'));
            if(c == EOF) return EOF;
            ungetc(c, stdin);
            if(isdigit(c)){  getn(); return NUMBER; }
            if(isalpha(c)){ getid(); getbrack(); return FUNC; }
            return getop();
    }
    /* Прочесть число (с точкой) */
    void getn(){
            int c, i;  char s[80];
            s[0] = getchar();
            for(i=1; isdigit(c = getchar()); i++ )  s[i] = c;
            if(c == '.'){   /* дробная часть */
               s[i] = c;
               for(i++; isdigit(c = getchar()); i++)  s[i] = c;
            }
            s[i] = '\0'; ungetc(c, stdin); value = atof(s);
    }
    /* Прочесть операцию */
    int getop(){
            int c;
            switch( c = getchar()){
            case EOF:       return EOF;
            case '=':       return END;
            case '+':       return PLUS;
            case '-':       return MINUS;
            case '/':       return DIV;
            case '*':       c = getchar();
                            if(c == '*') return POWER;
                            else{ ungetc(c, stdin); return MULT; }
            case '(':       return OPENBRACKET;
            case ')':       return CLOSEBRACKET;
            case ',':       return COMMA;
            default:        printf( "Ошибочная операция %c\n", c);
                            return token();
            }
    }
    struct funcs{   /* Таблица имен функций */
            char *fname; void (*fcall)();
    } tbl[] = {
            { "sin", dsin }, { "cos",   dcos  },
            { "exp", dexp }, { "sqrt",  dsqrt },
            { "sqr", dsqr }, { "pi",    pi    },
            { "sum", add  }, { "ln",    dlog  },
            { "e",   e    }, { NULL,    NULL  }
    };
    char *lastf;    /* имя найденной функции */
    /* Прочесть имя функции */
    void getid(){
            struct funcs *ptr = tbl;
            char name[80]; int c, i;
            *name = getchar();
            for(i=1; isalpha(c = getchar()); i++) name[i] = c;
            name[i] = '\0'; ungetc(c, stdin);
            /* поиск в таблице */
            for( ; ptr->fname; ptr++ )
                    if( !strcmp(ptr->fname, name)){
                            fvalue = ptr->fcall;
                            lastf =  ptr->fname; return;
                    }
            printf( "Функция \"%s\" неизвестна\n", name ); err(11);
    }
    /* прочесть открывающую скобку после имени функции */
    void getbrack(){
      int c;
      while((c = getchar()) != EOF && c != '(' )
      if( !isspace(c) && c != '\n' ){
          printf("Между именем функции %s и ( символ %c\n", lastf, c);
          ungetc(c, stdin); err(12);
      }
    }
    void main(){ calc();}
    /* Примеры:
            ( sin( pi() / 4 + 0.1 ) + sum(2, 4 + 1)) * (5 - 4/2) =
                    ответ: 23.3225
            (14 + 2 ** 3 * 7 + 2 * cos(0)) / ( 7 - 4 ) =
                    ответ: 24
    */

© Copyright А. Богатырев, 1992-95
Си в UNIX

Назад | Содержание | Вперед

Comments: info@citmgu.ru
Designed by Andrey Novikov
Copyright © CIT