Упражнение 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().
Результат:
Однако во сремя сборки пришлось столкнуться с ошибкой:
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");
}
}
Теперь у нас появилась возможность сравнить результаты. Например, печать с выталкиванием из стека и с сохранением:
А теперь -- с дублированием:
Изменение местами двух верхних элемента стека. Команда '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");
}
}
Очистка содержимого стека. Для этого достаточно установить указатель на следующую свободную ячейку стека равным нулю. Выполняться это будет по команде 'c'.
Упражнение 4.5. Предусмотрите возможность использования в программе библиотечных функций sin, ехр и pow. См. библиотеку
Наша песня хороша... Конечно, если записывать имя функции полностью, то придется помучится, но зачем это нужно. Ограничимся, как и ранее одной буквой. И одной функцией (принцип, я думаю, уже понятен). Пусть это будет 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;
А вот тест:
Упражнение 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):
Упражнение 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;
}
Извольте видеть:
Упражнение 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;
}
Упражнение 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);
}
Результат:
Упражнение 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;
}
Результат:
Комментарии
comments powered by Disqus