Date Редакция Категория comp Теги C / K&R

Упражнение 4.1. Напишите функцию strrindex(s, t), которая выдает позицию самого правого вхождения t в s или -1, если вхождения не обнаружено.

В качестве основы в учебнике предложена функция strindex()

  /* strindex: вычисляет место t в s или выдает -1, если t нет в s */
  int strindex (char s[], char t[])
  {
      int i, j, k;
      for (i = 0; s[i] != '\0'; i++) {
          for (j = i, k = 0; t[k] != '\0' && s[j] == t[k]; j++, k++);
          if (k > 0 && t[k] == '\0')
              return i;
      }
      return -1;
  }

которая выдает позицию начала вхождения самого первого (левого) вхождения t в s. Если же дальше в строке будет еще одно вхождение t, она не будет его учитывать. Нам нужно написать функцию, возвращающую начало этого последнего (правого) вхождения t. Остановимся на такой трактовке задания.

Решение:

  #include <stdio.h>

  #define MAXLINE 1000 /* максимальный размер вводимой строки */

  int getl(char line[], int max);
  int strrindex(char source[], char searchfor[]);

  char pattern[] ="ould"; /* образец для поиска */

  /* найти все строки, содержащие образец */

  int main()
  {
      char line[MAXLINE];
      int found = 0;
      int rind;

      while (getl(line, MAXLINE) > 0)
          if ((rind = strrindex(line, pattern)) >= 0) {
                  printf ("%d-%s", rind, line);
                  found++;
          }
      return found;
  }

  /* getl: читает строку в s, возвращает длину */
  int getl(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;
  }

  /* strrindex: вычисляет выдает позицию самого правого вхождения t в s 
   * или выдает -1, если t нет в s                                      */
  int strrindex (char s[], char t[])
  {
      int i, j, k;
      int tmp = -1;

      for (i = 0; s[i] != '\0'; i++) {
          for (j = i, k = 0; t[k] != '\0' && s[j] == t[k]; j++, k++);
          if (k > 0 && t[k] == '\0' && i > tmp)
              tmp = i;
      }
      return tmp;
  }

Надеюсь, не нужно напоминать почему у нас функция называется getl(), а не getline() как в книге (см. главу 1)? Она, кстати, слегка изменилась.

Проверим наше решение слегка измененным текстом из книги. Прости Омар если что не так...

  Ah Love! could you and I with Fate conspire
  To grasp this sorry Scheme of Things entire,
  Would not we shatter it to bits -- and then re-mould
  Re-mould it nearer to The Heart's Desire!

(наша добавка -- в конце 3-ей строки)

Получаем:

  Ah Love! could you and I with Fate conspire
  To grasp this sorry Scheme of Things entire,
  Would not we shatter it to bits -- and then re-mould
  Re-mould it nearer to The Heart's Desire!
  10-Ah Love! could you and I with Fate conspire
  48-Would not we shatter it to bits -- and then re-mould
  4-Re-mould it nearer to The Heart's Desire!

тогда как раньше было:

  Ah Love! could you and I with Fate conspire
  To grasp this sorry Scheme of Things entire,
  Would not we shatter it to bits -- and then re-mould
  Re-mould it nearer to The Heart's Desire!
  10-Ah Love! could you and I with Fate conspire
  1-Would not we shatter it to bits -- and then re-mould
  4-Re-mould it nearer to The Heart's Desire!

Упражнение 4.2. Дополните функцию atof таким образом, чтобы она справлялась с числами вида: 123.45e-6, в которых после мантиссы может стоять e (или E) с последующим порядком (быть может, со знаком).

Доработка весьма прямолинейна:

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

  #define MAXLEN 100

  double atof(char s[]);

  int main()
  {
      char in1[MAXLEN] = "  -10.325e-3\0";
      char in2[MAXLEN] = "  -10.325e+3\0";

      printf("in1 = %s\n", in1);
      printf("out = %f\n\n", atof(in1));

      printf("in2 = %s\n", in2);
      printf("out = %f\n", atof(in2));

      return 0;
  }

  /*atof: преобразование строки s в double */
  double atof(char s[])
  {
      double val, power, degval, base, exponent;
      int i, sign, degsign;

      for (i = 0; isspace(s[i]); i++);  /* игнорирование левых символов-разделителей */
      sign = (s[i] == '-') ? -1 : 1;
      if (s[i] ==' || s[i] =='-')
          i++;
      for (val = 0.0; isdigit(s[i]); i++)
          val = 10.0 * val + (s[i] - '0');
      if (s[i] == '.')
          i++;
      for (power = 1.0; isdigit(s[i]); i++) {
          val = 10.0 * val + (s[i] - '0');
          power *= 10.0;
      }
      if (s[i] == 'e' || s[i] == 'E')
          i++;
      degsign = (s[i] == '-') ? -1 : 1;
      if (s[i] ==' || s[i] =='-')
          i++;
      for (degval = 0.0; isdigit(s[i]); i++)
          degval = 10.0 * degval + (s[i] - '0');

      exponent = pow(10.0, degval);
      base = sign * (val / power);

      return degsign == 1 ? base * exponent : base / exponent;
  }

math.h понадобился нам для использования функции возведения в степень pow().

Результат:

atof0.png

Однако во сремя сборки пришлось столкнуться с ошибкой:

undefined reference to `pow'

хотя math.h была указана. Чтение man pow показало, что собирать ее нужно, используя опцию -lm gcc, что я и проделал, добавив в макрос, отвечающий за сборку в Geany соответствующую опцию. Но что это за опция такая? Об этом читайте здесь.

Упражнение 4.3. Исходя из предложенной нами схемы, дополните программу-калькулятор таким образом, чтобы она "понимала" оператор получения остатка от деления (%) и отрицательные числа.

В п. 4.4 описана программа-калькулятор. Она работает корректно только с положительными числами (минус перед операндом порождает "ошибка: стек пуст\n", хотя результат и вычисляется).

Если русские буквы в комментариях при просмотре в браузере (Проверка орфографии предлагает: "маузере". Солидно!) отображаются кракозябрами (Проверка орфографии предлагает: "разбраковками". Тоже не лишено смысла), просто сохраните файл на диск и откройте в текстовом редакторе.

Итак, приступим. Оператор switch в main() пополнится условием:

case '%':
    op2 = pop();
    if (op2 != 0.0) {
        op1 = pop();
        push ( op1 - op2 * floor(op1 / op2) );
    }
    else
        printf("ошибка: деление на нуль\n");
    break;

где op1 -- типа double.

C получением остатка разобрались, теперь "научим" программу работать с отрицательными числами. Для этого усовершенствуем getop():

  int getop(char s[])
  {
      int i=0, c, t;
      while ((s[i] = c = getch()) == ' ' || c == '\t');
      if (!isdigit(c) && c != '.') {
          if (c == '-') {
              if (isdigit(t = getch()) || t == '.') {
                  s[++i] = t;
              }
              else {
                  ungetch(t);
                  return c;  /* не число */
              }
          }
          else {
              return c;      /* не число */
          }
      }
      if (isdigit(c)) /* накапливаем целую часть */
          while (isdigit(s[++i] = c = getch()));
      if (c =='.')    /* накапливаем дробную часть */
          while (isdigit(s[++i] = c = getch()));
      s[i] = '\0';
      if (c != EOF)
          ungetch(c);
      return NUMBER;
  }

Логика такова:

  • если встретился "минус", посмотрим, не стоит ли после него цифра или десятичная точка
    • если стоит, то это знак числа;
    • если нет, то это оператор, который надо возвратить.

Примеры:

2 3 + 5 2 -3 + -1 2 -3 - 5 2 -3 - 5 -2 3 - -5

Полный код

Упражнение 4.4. Добавьте команды, с помощью которых можно было бы печатать верхний элемент стека (с сохранением его в стеке), дублировать его в стеке, менять местами два верхних элемента стека. Введите команду очистки стека.

Печать верхнего элемента стека с сохранением его в стеке. Не понял, в чем проблема -- тот же pop(), но без изменения sp:

  /* tail: взять с вершины стека и выдать в качестве результата */
  double tail(void)
  {
      if (sp > 0)
          return val[sp-1];
      else {
         printf ("ошибка: стек пуст\n");
         return 0.0;
     }
  }

Вызывать эту операцию будем командой 't'. Соответствующий кусок main():

        case 't':
            printf("\n\t%.8g\n", tail());
            break;

Дублирование последнего элемента в стеке. Срабатывает по команде 'd'.

  /* duplicate: дублировать элемент с вершины стека */
  void duplicate(void)
  {
      if (sp > 0) {
          val[sp] = val[sp-1];
          ++sp;
      }
      else {
          printf ("ошибка: стек пуст\n");
      }
  }

Для удобства введем еще одну команду -- p, означающую печать элементов стека. Реализуется она так:

  /* printstack: печать содержимого стека */
  void printstack(void)
  {
      int i;
      printf ("\n");
      if (sp > 0) {
          for (i = 0; i < sp; ++i)
              printf ("%.8g ", val[i]);
      }
      else {
          printf ("ошибка: стек пуст\n");
      }
  }

Теперь у нас появилась возможность сравнить результаты. Например, печать с выталкиванием из стека и с сохранением:

calc0.png

А теперь -- с дублированием:

calc01.png

Изменение местами двух верхних элемента стека. Команда 's':

  /* swap: обмен содержимым двух верхних ячеек стека */
  void swap(void)
  {
      double t;

      if (sp > 1) {
          t = val[sp-2];
          val[sp-2] = val[sp-1];
          val[sp-1] = t;
      }
      else {
          printf ("ошибка: недостаточно элементов для обмена\n");
      }
  }

calc02.png

Очистка содержимого стека. Для этого достаточно установить указатель на следующую свободную ячейку стека равным нулю. Выполняться это будет по команде 'c'.

calc03.png

Полный код

Упражнение 4.5. Предусмотрите возможность использования в программе библиотечных функций sin, ехр и pow. См. библиотеку в приложении B (параграф 4).

Наша песня хороша... Конечно, если записывать имя функции полностью, то придется помучится, но зачем это нужно. Ограничимся, как и ранее одной буквой. И одной функцией (принцип, я думаю, уже понятен). Пусть это будет pow(), которую мы будем вызывать командой... подходящая буква уже занята... будем вызывать как 'w'. Отступление про особенности компиляции при использовании математической библиотеки -- см. выше.

Вот соответствующий фрагмент switch:

       case 'w':
            op2 = pop();
            if (op2 > 0) {
                op1 = pop();
                if (op1 != 0)
                    push (pow(op1, op2));
                else
                    printf("ошибка области: x = 0\n");
            }
            else
                printf("ошибка области: y <= 0\n");
            break;                     

А вот тест:

calc04.png

Полный код

Упражнение 4.6. Введите команды для работы с переменными (легко обеспечить до 26 переменных, каждая из которых имеет имя, представленное одной буквой латинского алфавита). Добавьте переменную, предназначенную для хранения самого последнего из напечатанных значений.

Пусть имена переменных -- прописные латинские буквы A-Z. Операция '>A' будет обозначать помещение данных из верхней ячейки стека в переменную А. Употребление имени переменной без знака '>' означает копирование информации из переменной в вершину стека.

Соответствующий фрагмент switch будет выглядеть так:

        case '>':
            in = 1;
            break;
        case 'A': case 'B': case 'C':
            if (in) {
                optovar(type, pop());
                in = 0;
            }
            else
                push(vartoop(type));
            break;

Здесь используются всего три буквы латинского алфавита, но, думаю, идея понятна. Переключатель in определять помещать ли данные из стека в переменную (это выполняется функцией optovar()) или извлекать из переменной в стек (vartoop()).

  /* optovar: поместить верхнюю ячейку стека в переменную */
  void optovar(int n, double f)
  {
      var[n-'A'] = f;
  }

  /* vartoop: взять значение переменной и выдать в качестве результата */ 
  double vartoop(int n)
  {
      return var[n-'A'];
  }

Зачем такой примитив? Почему бы сразу не записывать в var[]? Хотелось держать этот массив вместе со стеком и отдельно от main().

Кроме того, вот функция, которая печатает содержимое массива переменных:

  /* printvars: печать массива переменных */
  void printvars(void)
  {
      int i;
      printf ("\n");
      for (i = 0; i < MAXVAR; ++i)
          printf ("%.8g ", var[i]);
  }

Последнее подзадание не выполнил -- лень и очевидно. Кроме того, можно было ввести еще немало функций по работе с переменными (например, очистить заданную переменную). По той же причине не стал этим заниматься.

Для ясности, выбросил из кода некоторые добавки, появившиеся благодаря выполненным упражнениям. Вот он.

Сохраним первый операнд (2) в переменной B, а затем извлечем его оттуда и сложим с 3. Проверим также содержимое переменных (v):

calc05.png

Упражнение 4.7. Напишите программу ungets(s), возвращающую строку s во входной поток. Должна ли ungets "знать" что-либо о переменных buf и bufp, или ей достаточно пользоваться только функцией ungetch?

На мой взгляд, идеальная реализация ungets(s) (возврат строки) должна быть основана на функции возврата отдельных символов ungetch() и не должна ничего "знать" о подробностях реализации последней.

 #include <stdio.h>
 #include <string.h> /* strlen() */

 int getch(void);
 void ungetch(int);
 void ungets(char []);

 #define BUFSIZE 100

 char buf[BUFSIZE];    /* буфер для ungetch */
 int bufp = 0;         /* след. свободная позиция в буфере */

 int getch(void)       /* взять символ */
 {
     return (bufp > 0) ? buf[--bufp] : getchar();
 }

 void ungetch(int c)   /* вернуть символ на ввод */
 {
     if (bufp >= BUFSIZE)
         printf("ungetch: слишком много символов\n");
     else
         buf[bufp++] = c;
 }

 void ungets(char s[])
 {
     int i=strlen(s);

     while (i > 0) {
         ungetch(s[--i]);
     }
 }

 int main()
 {
     char string[] = "This is a\ntext\n";
     int c;

     ungets(string);

     while((c = getch()) != EOF) {
         putchar(c);
     }

     return 0;
 }

Извольте видеть:

ungets0.png

Упражнение 4.8. Предположим, что число символов, возвращаемых назад, не превышает 1. Модифицируйте с учетом этого факта функции getch и ungetch.

 #include <stdio.h>

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

 int buf = 0;          /* переменная-буфер */

 int getch(void)       /* взять символ */
 {
     int t;

     if (buf != 0){
         t = buf;
         buf = 0;
     }
     else
         t = getchar();
     return t;
 }

 void ungetch(int c)   /* вернуть символ на ввод */
 {
     if (buf == 0)
         buf = c;
     else
         printf("ungetch: слишком много символов\n");
 }

 int main()
 {
     int c;

     while ((c = getch()) != EOF) {
         if (c == 'a') { /* заменим 'a' на 'A' в строке ввода */
             ungetch('A');
             putchar(getch());
         }
         else
             putchar(c);
     }

     return 0;
 }

ungetone0.png

Упражнение 4.9. В наших функциях не предусмотрена возможность возврата EOF. Подумайте, что надо сделать, чтобы можно было возвращать EOF, и скорректируйте соответственно программу.

По правде говоря, мне не кажется, что есть какая-то необходимость возврата EOF. Но если авторы просят...

Интересно, а о каких функциях идет речь? Если говорить о функциях из прошлого упражнения, то getch() и ungetch() это вполне позволяют, не позволяет лишь main(). Что ж, если нужно не остановить цикл сразу по встрече EOF, а дать ему выполниться и лишь потом выйти, нам поможет конструкция "до-вхиле", изученная в предыдущей главе.

Переделанный main():

 int main()
 {
     int c;

     do {
         c = getch();
         if (c == 'a') { /* заменим 'a' на 'A' в строке ввода */
             ungetch('A');
             putchar(getch());
         }
         else
             putchar(c);
     } while (c != EOF);

     return 0;
 }

Упражнение 4.10. В основу программы калькулятора можно положить применение функции getline, которая читает целиком строку; при этом отпадает необходимость в getch и ungetch. Напишите программу, реализующую этот подход.

По традиции переименуем getline() в getl(), и воспользуемся более свежей версией этой функции -- из п. 4.1:

#include <stdio.h>
#include <stdlib.h> /* для atof() */

#define MAXOP 100  /* макс. размер операнда или оператора */
#define NUMBER '0' /* признак числа */
#define MAXLINE 500  /* макс. размер строки ввода */

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

char line[MAXLINE];
int line_i;

/* калькулятор с обратной польской записью */
int main()
{
    int type;
    double op2;
    char s[MAXOP];

    while (getl(line, MAXLINE) != 0) 
    {
        line_i = 0;
        while ((type = getop(s)) != '\0') 
        {
            switch (type) 
            {
                case NUMBER:
                    push (atof(s));
                    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("ошибка: деление на нуль\n");
                    break;
                case '\n':
                    printf("\t%.8g\n", pop());
                    break;
                default:
                    printf("ошибка: неизвестная операция %s\n", s);
                    break;
            }
        }
    }
    return 0;
}

#include <ctype.h>

/* getop: получает следующий оператор или операнд */
int getop(char s[])
{
    int i, c;

    while ((s[0] = c = line[line_i++]) == ' ' || c == '\t');
    s[1] = '\0';
    if (!isdigit(c) && c != '.')
        return c;  /* не число */
    i = 0;
    if (isdigit(c)) /* накапливаем целую часть */
        while (isdigit(s[++i] = c = line[line_i++]));
    if (c =='.') /* накапливаем дробную часть */
        while (isdigit(s[++i] = line[line_i++]));
    s[i] = '\0';
    line_i--;

    return NUMBER;
}

/* getline: читает строку в s, возвращает длину */
int getl(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;
}

Из кода удалены не изменившиеся push() и pop(). Вот полный код.

"Фишка" здесь в глобальности переменных line[] и line_i -- строка и обрабатываемая позиция в ней должны существовать в ходе нескольких вызовов getop(). Код, таким образом, упростился, хотя и стал более связанным.

Упражнение 4.11. Модифицируйте функцию getop так, чтобы отпала необходимость в функции ungetch. Подсказка: используйте внутреннюю статическую переменную.

Рассмотрим исходный вариант getop():

/* getop: получает следующий оператор или операнд */
int getop(char s[])
{
    int i, c;
    while ((s[0] = c = getch()) == ' ' || c == '\t');
    s[1] = '\0';
    if (!isdigit(c) && c != '.')
        return c;    /* не число */
    i = 0;
    if (isdigit(c)) /* накапливаем целую часть */
        while (isdigit(s[++i] = c = getch()));
    if (c =='.') /* накапливаем дробную часть */
        while (isdigit(s[++i] = c = getch()));
    s[i] = '\0';
    if (c != EOF)
        ungetch(c);
    return NUMBER;
}

ungetch нужна, чтобы вернуть в исходный поток символ, не соответствующий ни одному из проверяемых условий. Например, это может быть знак операции, "приклеенный" к числу сзади: 4 3+. ungetch вернет ' во входной поток, и при следующей проверке getop выяснит, что это "не число".

Но можно поступить по-другому: сохранить этот символ в переменной, значение которой сохраняется при следующем вызове функции -- т.е. в статической переменной. Тогда при следующем вызове нужно проверить содержимое этой переменной (назовем ее last_c), и если там что-то хранится, то исследовать содержимое "заначки" last_c. Если же last_c пуста, то, как и ранее, анализируем новый ввод.

int getop(char s[])
{
    int c, i;
    static int last_c = 0;

    if (last_c == 0)
        c = getch();
    else {
        c = last_c;
        last_c = 0;
    }

    while ((s[0] = c) == ' ' || c == '\t')
        c = getch();
    s[1] = '\0';
    if (!isdigit(c) && c != '.')
        return c;  /* не число */
    i = 0;
    if (isdigit(c)) /* накапливаем целую часть */
        while (isdigit(s[++i] = c = getch()));
    if (c =='.') /* накапливаем дробную часть */
        while (isdigit(s[++i] = c = getch()));
    s[i] = '\0';
    if (c != EOF)
        last_c = c;
    return NUMBER;
}

Заголовок while также изменился, поскольку при первом заходе в цикл c уже присвоено значение.

Упражнение 4.12. Примените идеи, которые мы использовали в printd, для написания рекурсивной версии функции itoa; иначе говоря, преобразуйте целое число в строку цифр с помощью рекурсивной программы.

Вот printd(), идеи из которой предполагается применить:

 #include <stdio.h>

 /* printd: печатает n как целое десятичное число */
 void printd(int n)
 {
     if (n < 0) {
         putchar('-');
         n = -n;
     }
     if (n / 10)
         printd(n / 10);
     putchar(n % 10 + '0');
 }

С функцией itoa, в ее нерекурсивном варианте, мы имели дело в упражнениях 3.4--3.6. Напомню:

 void itoa(int n, char s[])
 {
     int i, sign;
     if ((sign = n) < 0) /* сохраняем знак */
         n =-n;                 /* делаем n положительным */
     i = 0;
     do { /* генерируем цифры в обратном порядке */
     s[i++] = n % 10 + '0'; /* следующая цифра */
     } while ((n /= 10) > 0); /* исключить ее */
     if (sign < 0)
         s[i++] = '-';
     s[i] = '\0';
     reverse(s);
 }

Вот что получается:

 #include <stdio.h>

 void itoa(int n, char s[]);
 void reverse(char s[]);

 int main(void) {
     char buffer[20];
     int i =-2834;

     printf("Number: %d\n", i);
     itoa(i, buffer); 
     printf("Buffer : %s\n", buffer);

     return 0;
 }

 /* itoa: преобразование n в строку s */
 void itoa(int n, char s[])
 {
     static int i;

     if (n < 0)
     {
         n =-n;
         s[i++] = '-';      /* делаем n положительным */
     }
     if (n / 10)
         itoa(n / 10, s);
     s[i++] = n % 10 + '0'; /* следующая цифра */
     s[i] = '\0';
 }

Использование рекурсии позволяет обойтись без обращения строки. Кроме того, нам очень пригодилась внутренняя статическая переменная: Получившаяся в итоге рекурсивная itoa() имеет недостатки, с которыми мы уже боролись в упражнениях 3.4--3.6. Так что, при необходимости, ее можно развить, опираясь на результаты этих упражнений.

Упражнение 4.13. Напишите рекурсивную версию функции reverse(s), переставляющую элементы строки в ту же строку в обратном порядке.

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

 void reverse(char [], int, int);

 int main(void) {
     char test[] = "Test String";
     int last;

     printf("Input          : %s\n", test);
     last = strlen(test)-1;
     reverse(test, 0, last);
     printf("Reversed       : %s\n", test);
     reverse(test, 0, last);
     printf("Double Reversed: %s\n", test);    
     return 0;
 }

 void reverse(char s[], int first, int last) {
     int c;

     c = s[first];
     s[first++] = s[last];
     s[last--] = c;
     if (first != last)
         reverse(s, first, last);
 }

Результат:

rreverse0.png

Упражнение 4.14. Определите swap(t,x,y) в виде макроса, который осуществляет обмен значениями указанного типа t между аргументами x и y. (Примените блочную структуру.)

 #include <stdio.h>

 #define swap(t,x,y) {t temp = x; x = y; y = temp;}


 int main(void) {
     int ai=1, bi=2;
     printf("Initial: ai=%d, bi=%d\n", ai, bi);
     swap(int, ai, bi);
     printf("Swapped: ai=%d, bi=%d\n", ai, bi);

     float af=1.0, bf=2.0;
     printf("Initial: af=%f, bf=%f\n", af, bf);
     swap(float, af, bf);
     printf("Swapped: af=%f, bf=%f\n", af, bf);

     return 0;
 }

Результат:

macswap0.png



Комментарии

comments powered by Disqus