ла в байтах */
if( (fpnew = fopen( "inv.out", "w" ))== NULL ){
printf("Can not create file\n");
exit(3);
}
while( fgets( buffer, sizeof buffer, fp ) != NULL ){
lgt = strlen( buffer );
fseek(fpnew, len - lgt , 0);
/* Помните, что смещение у lseek и fseek -
* это число типа long, а не int.
* Поэтому лучше всегда писать
* lseek(fd, (long) off, whence);
*/
len -= lgt;
fprintf( fpnew, "%s", buffer );
/* или лучше fputs(buffer, fpnew); */
}
fclose( fp ); fclose( fpnew );
}
7.34. Напишите программу, которая читает файл, состоящий из "блоков" текста, разде-
ленных пустыми строками. Размер "блока" ограничен. Программа готовит файл для печати
на принтер так, чтобы ни один блок не разбивался на части:
А. Богатырев, 1992-95 - 298 - Си в UNIX
----------- -----------
|###### A | |###### A | лист1
|#### A | превращать |#### A |
|##### A | в |##### A |
| | | |
|###### B | | |
----------- -----------
|#### B | |###### B | лист2
| | |#### B |
... | |
то есть если блок не умещается на остатке листа, он должен быть перенесен на следую-
щий лист. Блоки следует разделять одной пустой строкой (но первая строка листа не
должна быть пустой!). Если блок длиннее страницы - не переносите его.
/* Решение задачи о переносе блоков текста,
* если они не умещаются на остатке листа */
#include <stdio.h>
#include <ctype.h>
extern void *malloc(unsigned);
extern int atoi(char *);
FILE *fpin = stdin, *fpout = stdout;
/* Спасти строку в динамически выделенной памяти */
char *strdup (const char *s) {
char *ptr = (char *) malloc (strlen (s) + 1);
if( ptr ) strcpy (ptr, s); return ptr;
}
int page_length = 66; /* длина страницы */
int current_line; /* текущая строка на странице (с нуля) */
int numbered = 0; /* нумеровать строки листа ? */
#define MAXLINES 256 /* макс. длина блока */
int stored = 0; /* запомнено строк */
char *lines[MAXLINES]; /* запомненные строки */
/* Запомнить строку блока в буфер строк */
void remember (char *s) {
if (stored >= MAXLINES) {
fprintf (stderr, "Слишком длинный блок.\n"); return;
} else if((lines[stored++] = strdup (s)) == NULL ){
fprintf (stderr, "Мало памяти (Out of memory).\n"); exit(13);
}
}
/* Переход на следующую страницу */
void newpage () {
current_line = 0; putc('\f', fpout);
}
А. Богатырев, 1992-95 - 299 - Си в UNIX
/* Перевод строки или листа */
void newline (void) {
if (current_line == page_length - 1)
newpage (); /* начать новый лист */
else {
current_line++;
if( numbered ) fprintf(fpout, "%02d\n", current_line);
else putc ('\n', fpout);
}
}
/* Переход на следующую страницу вставкой пустых строк */
void nextpage () {
while (current_line != 0)
newline ();
}
/* Выдать спасенный блок */
void throwout () {
register i;
for (i = 0; i < stored; i++) {
if( numbered )
fprintf(fpout, "%02d %s", current_line, lines[i]);
else fputs (lines[i], fpout);
newline (); free (lines[i]);
}
stored = 0;
}
/* Выдать блок, перенося на следующий лист если надо */
void flush () {
int rest_of_page = page_length - current_line;
/* осталось пустых строк на странице */
if ((stored > page_length && rest_of_page < page_length / 4) ||
rest_of_page < stored)
nextpage ();
throwout ();
if (current_line) /* не первая строка листа */
newline (); /* разделитель блоков */
}
/* Обработать входной файл */
void process () {
char buffer[512]; int l;
while (fgets (buffer, sizeof buffer, fpin) != NULL) {
if ((l = strlen (buffer)) && buffer[l - 1] == '\n')
buffer[ --l] = '\0';
if (l) remember (buffer);
/* а по пустой строке - выдать блок */
else if (stored) flush ();
}
if (stored) flush ();
nextpage();
}
А. Богатырев, 1992-95 - 300 - Си в UNIX
void main (int argc, char *argv[]) {
argc--; argv++;
while (*argv) {
if (**argv == '-') {
char *key = *argv + 1, *arg;
switch (*key) {
case 'l':
if (! key[1]) {
if( argv[1] ){
arg = argv[1]; argv++; argc--;
} else arg = "";
} else arg = key+1;
if( isdigit(*arg) ){
page_length = atoi(arg);
fprintf (stderr, "Длина страницы: %d строк\n", page_length);
} else fprintf(stderr, "-l ЧИСЛО\n");
break;
case 'n':
numbered++; break;
default:
fprintf (stderr, "Неизвестный ключ %s\n", key);
break;
}
}
argv++; argc--;
}
process ();
exit(0);
}
7.35. Составьте программу вывода строк файла в инверсном отображении, причем порядок
символов в строках также следует инвертировать. Например,
abcdef ... oklmn 987654321
..... превращать в .....
123456789 nmlko ... fedcba
Программа должна быть составлена двумя способами: при помощи обратного чтения файла и
рекурсивным вызовом самой функции инвертирования. Указание: при обратном чтении надо
читать файл большими кусками (блоками).
7.36. Напишите программу, читающую файл построчно и размещающую строки в отсортиро-
ванное двоичное дерево. По концу файла - распечатайте это дерево. Указание: исполь-
зуйте динамическую память и рекурсию.
А. Богатырев, 1992-95 - 301 - Си в UNIX
/* Двоичная сортировка строк при помощи дерева */
#include <stdio.h>
char buf[240]; /* буфер ввода */
int lines; /* номер строки файла */
typedef struct node{
struct _data{ /* ДАННЫЕ */
char *key; /* ключ - строка */
int line; /* номер строки */
} data;
/* СЛУЖЕБНАЯ ИНФОРМАЦИЯ */
struct node *l, /* левое поддерево */
*r; /* правое поддерево */
} Node;
Node *root = NULL; /* корень дерева (ссылка на верхний узел) */
/* Отведение памяти и инициализация нового узла */
Node *newNode(s)
char *s; /* строка */
{
Node *tmp;
extern char *malloc(); /* выделитель памяти */
tmp = (Node *) malloc(sizeof(Node));
if( tmp == NULL ){
fprintf( stderr, "Нет памяти.\n");
exit(1);
}
tmp -> l = tmp -> r = NULL; /* нет поддеревьев */
tmp -> data.line = lines; /* номер строки файла */
tmp -> data.key = malloc( strlen(s) + 1 );
/* +1 - под байт '\0' в конце строки */
strcpy(tmp -> data.key, s); /* копируем ключ в узел */
return tmp;
}
int i; /* Вынесено в статическую память, чтобы при каждом
* рекурсивном вызове не создавалась новая auto-переменная,
* а использовалась одна и та же статическая */
А. Богатырев, 1992-95 - 302 - Си в UNIX
/* Рекурсивная печать дерева */
void printtree(root, tree, level, c)
Node *root; /* корень дерева */
Node *tree; /* дерево */
int level; /* уровень */
char c; /* имя поддерева */
{
if( root == NULL ){ printf("Дерево пусто.\n"); return; }
if( tree == NULL ) return;
/* если есть - распечатать левое поддерево */
printtree (root, tree -> l, level + 1, '/'); /* 'L' */
/* распечатать ключ узла */
for( i=0; i < level; i++ )
printf(" ");
printf("%c%3d--\"%s\"\n",
c, tree-> data.line, tree -> data.key);
/* если есть - распечатать правое поддерево */
printtree(root, tree -> r, level + 1, '\\'); /* 'R' */
}
void prTree(tree) Node *tree;
{
printtree(tree, tree, 0, '*');
}
/* Добавить узел с ключом key в дерево tree */
void addnode(tree, key)
Node **tree; /* в какое дерево добавлять: адрес переменной,
* содержащей ссылку на корневой узел */
char *key; /* ключ узла */
{
#define TREE (*tree)
if( TREE == NULL ){ /* дерево пока пусто */
TREE = newNode( key );
return;
}
/* иначе есть хоть один узел */
if ( strcmp (key, TREE -> data.key) < 0 )
{
/* добавить в левое поддерево */
if ( TREE -> l == NULL ){
/* нет левого дерева */
TREE -> l = newNode(key);
return;
}
else addnode( & TREE ->l , key);
}
А. Богатырев, 1992-95 - 303 - Си в UNIX
else{
/* добавить в правое дерево */
if ( TREE -> r == NULL ){
/* нет правого поддерева */
TREE -> r = newNode(key);
return;
}
else addnode ( & TREE ->r, key) ;
}
}
/* Процедура удаления из дерева по ключу. */
typedef struct node *NodePtr;
static NodePtr delNode; /* удаляемая вершина */
void delete(key, tree)
char *key; /* ключ удаляемого элемента */
NodePtr *tree; /* из какого дерева удалять */
{
extern void doDelete();
if(*tree == NULL){
printf( "%s не найдено\n", key ); return;
}
/* поиск ключа */
else if(strcmp(key, (*tree)->data.key) < 0)
delete( key, &(*tree)->l );
else if(strcmp(key, (*tree)->data.key) > 0)
delete( key, &(*tree)->r );
else{ /* ключ найден */
delNode = *tree; /* указатель на удаляемый узел */
if(delNode->r == NULL) *tree = delNode->l;
else if(delNode->l == NULL) *tree = delNode->r;
else doDelete( & delNode->l );
free(delNode);
}
}
static void doDelete(rt) NodePtr *rt;
{
if( (*rt)->r != NULL ) /* спуск по правой ветви */
doDelete( &(*rt)->r );
else{
/* перенос данных в другой узел */
delNode->data = (*rt)->data;
delNode = *rt; /* для free() */
*rt = (*rt)->l;
}
}
А. Богатырев, 1992-95 - 304 - Си в UNIX
void main(){
extern char *gets(); char *s;
while (gets(buf) != NULL){ /* пока не конец файла */
lines++;
addnode( & root, buf );
}
prTree(root);
/* удалим строку */
freopen("/dev/tty", "r", stdin);
do{
printf( "что удалить ? " );
if((s = gets(buf)) == NULL) break;
delete(buf, &root);
prTree( root );
} while( s && root );
printf("Bye-bye.\n");
exit(0);
}
7.37. Напишите программу, которая читает со стандартного ввода 10 чисел либо слов, а
затем распечатывает их. Для хранения введенных данных используйте объединение.
#include <stdio.h>
#include <ctype.h>
#define INT 'i'
#define STR 's'
struct data {
char tag; /* тэг, пометка. Код типа данных. */
union {
int i;
char *s;
} value;
} a[10];
int counter = 0; /* счетчик */
void main(){
char word[128]; int i; char *malloc(unsigned);
/* Чтение: */
for(counter=0; counter < 10; counter++){
if( gets(word) == NULL ) break;
if( isdigit((unsigned char) *word)){
a[counter].value.i = atoi(word);
a[counter].tag = INT;
} else {
a[counter].value.s = malloc(strlen(word)+1);
strcpy(a[counter].value.s, word);
a[counter].tag = STR;
}
}
/* Распечатка: */
for(i=0; i < counter; i++)
switch(a[i].tag){
case INT: printf("число %d\n", a[i].value.i);
break;
case STR: printf("слово %s\n", a[i].value.s);
free(a[i].value.s);
break;
}
А. Богатырев, 1992-95 - 305 - Си в UNIX
}
7.38. Рассмотрим задачу написания функции, которая обрабатывает переменное число
аргументов, например функцию-генератор меню. В такую функцию надо подавать строки
меню и адреса функций, вызываемых при выборе каждой из строк. Собственно проблема,
которую мы тут обсуждаем - как передавать переменное число аргументов в подобные
функции? Мы приведем три программы использующие три различных подхода. Предпочтение
не отдано ни одному из них - каждый из них может оказаться эффективнее других в опре-
деленных ситуациях. Думайте сами!
7.38.1. Массив
/* Передача аргументов в функцию как МАССИВА.
* Следует явно указать число аргументов в массиве.
*/
#include <stdio.h> /* printf(), NULL */
#include <string.h> /* strdup() */
#include <stdlib.h> /* malloc() */
#define A_INT 1
#define A_STR 2
#define A_NULL 0
typedef struct arg {
int type;
union jack {
char *s;
int d;
} data;
struct arg *next;
} Arg;
void doit(Arg args[], int n){
int i;
for(i=0; i < n; i++)
switch(args[i].type){
case A_INT:
printf("%d", args[i].data.d);
break;
case A_STR:
printf("%s", args[i].data.s);
break;
default:
fprintf(stderr, "Unknown type!\n");
break;
}
}
А. Богатырев, 1992-95 - 306 - Си в UNIX
/* При инициализации union надо использовать тип
* первого из перечисленных значений.
*/
Arg sample[] = {
{ A_INT, (char *) 123 },
{ A_STR, (char *) " hello, " },
{ A_INT, (char *) 456 },
{ A_STR, (char *) " world\n" }
};
int main(int ac, char *av[]){
doit(sample, sizeof sample / sizeof sample[0]);
return 0;
}
7.38.2. Список
/* Передача аргументов в функцию как СПИСКА.
* Достоинство: список можно модифицировать
* во время выполнения программы: добавлять и
* удалять элементы. Недостаток тот же: список надо
* построить динамически во время выполнения,
* заранее этого сделать нельзя.
* Недостатком данной программы является также то,
* что список не уничтожается после использования.
* В C++ эта проблема решается при помощи использования
* автоматически вызываемых деструкторов.
*/
#include <stdio.h> /* printf(), NULL */
#include <string.h> /* strdup() */
#include <stdlib.h> /* malloc() */
#define A_INT 1
#define A_STR 2
#define A_NULL 0
typedef struct arg {
int type;
union jack {
char *s;
int d;
} data;
struct arg *next;
} Arg;
А. Богатырев, 1992-95 - 307 - Си в UNIX
void doit(Arg *arglist){
for( ; arglist; arglist=arglist->next)
switch(arglist->type){
case A_INT:
printf("%d", arglist->data.d);
break;
case A_STR:
printf("%s", arglist->data.s);
break;
default:
fprintf(stderr, "Unknown type!\n");
break;
}
}
Arg *new_int(int n, Arg *next){
Arg *ptr = (Arg *) malloc(sizeof(Arg));
ptr->type = A_INT;
ptr->data.d = n;
ptr->next = next;
return ptr;
}
Arg *new_str(char *s, Arg *next){
Arg *ptr = (Arg *) malloc(sizeof(Arg));
ptr->type = A_STR;
ptr->data.s = strdup(s);
ptr->next = next;
return ptr;
}
int main(int ac, char *av[]){
doit(
new_int(123,
new_str(" hello, ",
new_int(456,
new_str(" world\n",
NULL))))
);
return 0;
}
7.38.3. Функция с переменным числом параметров
/* Передача аргументов в функцию как СПИСКА АРГУМЕНТОВ
* ФУНКЦИИ с признаком конца списка.
*/
#include <stdio.h> /* printf(), NULL */
#include <stdarg.h> /* va_... */
#define A_INT 1
#define A_STR 2
#define A_NULL 0
А. Богатырев, 1992-95 - 308 - Си в UNIX
void doit(...){ /* переменное число аргументов */
va_list args;
/* второй параметр - аргумент, предшествующий ...
* Если такого нет - ставим запятую и пустое место!
*/
va_start(args, );
for(;;){
switch(va_arg(args, int)){
case A_INT:
printf("%d", va_arg(args, int));
break;
case A_STR:
printf("%s", va_arg(args, char *));
break;
case A_NULL:
goto breakloop;
default:
fprintf(stderr, "Unknown type!\n");
break;
}
}
breakloop:
va_end(args);
}
int main(int ac, char *av[]){
doit(
A_INT, 123,
A_STR, " hello, ",
A_INT, 456,
A_STR, " world\n",
A_NULL
);
return 0;
}
7.39. Напишите несколько функций для работы с упрощенной базой данных. Запись в базе
данных содержит ключ - целое, и строку фиксированной длины:
struct data {
int b_key; /* ключ */
char b_data[ DATALEN ]; /* информация */
};
Напишите:
- добавление записи
- уничтожение по ключу
- поиск по ключу (и печать строки)
- обновление по ключу.
Файл организован как несортированный массив записей без дубликатов (т.е. ключи не
могут повторяться). Поиск производить линейно. Используйте функции fread, fwrite,
fseek. Последняя функция позволяет вам позиционироваться к n-ой записи файла:
fseek( fp, (long) n * sizeof(struct data), 0 );
Перепишите эту программу, объявив ключ как строку, например
А. Богатырев, 1992-95 - 309 - Си в UNIX
char b_key[ KEYLEN ];
Если строка-ключ короче KEYLEN символов, она должна оканчиваться '\0', иначе -
используются все KEYLEN букв и '\0' на конце отсутствует (так же устроено поле d_name
в каталогах файловой системы). Усовершенствуйте алгоритм доступа, используя хеширо-
вание по ключу (hash - перемешивание, см. пример в приложении). Вынесите ключи в
отдельный файл. Этот файл ключей состоит из структур
struct record_header {
int b_key ; /* ключ */
long b_offset; /* адрес записи в файле данных */
int b_length; /* длина записи (необязательно) */
};
то есть организован аналогично нашей первой базе данных. Сначала вы ищете нужный
ключ в файле ключей. Поле b_offset у найденного ключа задает адрес данного в другом
файле. Чтобы прочитать его, надо сделать fseek на расстояние b_offset в файле данных
и прочесть b_length байт.
7.40. Организуйте базу данных в файле как список записей. В каждой записи вместо
ключа должен храниться номер очередной записи (ссылка). Напишите функции: поиска дан-
ных в списке (по значению), добавления данных в список в алфавитном порядке, (они
просто приписываются к концу файла, но в нужных местах переставляются ссылки), распе-
чатки списка в порядке ссылок, удалению элементов из списка (из самого файла они не
удаляются!). Ссылка (номер) первой записи (головы списка) хранится в первых двух
байтах файла, рассматриваемых как short.
Введите оптимизацию: напишите функцию для сортировки файла (превращению переме-
шанного списка в линейный) и вычеркивания из него удаленных записей. При этом файл
будет перезаписан. Если файл отсортирован, то поиск в нем можно производить более
эффективно, чем прослеживание цепочки ссылок: просто линейным просмотром. Третий
байт файла используйте как признак: 1 - файл был отсортирован, 0 - после сортировки в
него было что-то добавлено и линейный порядок нарушен.
7.41. Напишите функцию match(строка,шаблон); для проверки соответствия строки упро-
щенному регулярному выражению в стиле Шелл. Метасимволы шаблона:
* - любое число любых символов (0 и более);
? - один любой символ.
Усложнение:
[буквы] - любая из перечисленных букв.
[!буквы] - любая из букв, кроме перечисленных.
[h-z] - любая из букв от h до z включительно.
Указание: для проверки "остатка" строки используйте рекурсивный вызов этой же функ-
ции.
Используя эту функцию, напишите программу, которая выделяет из файла СЛОВА,
удовлетворяющие заданному шаблону (например, "[Ии]*о*т"). Имеется в виду, что каждую
строку надо сначала разбить на слова, а потом проверить каждое слово.
А. Богатырев, 1992-95 - 310 - Си в UNIX
#include <stdio.h>
#include <string.h>
#include <locale.h>
#define U(c) ((c) & 0377) /* подавление расширения знака */
#define QUOT '\\' /* экранирующий символ */
#ifndef MATCH_ERR
# define MATCH_ERR printf("Нет ]\n")
#endif
/* s - сопоставляемая строка
* p - шаблон. Символ \ отменяет спецзначение метасимвола.
*/
int match (register char *s, register char *p)
{
register int scc; /* текущий символ строки */
int c, cc, lc; /* lc - предыдущий символ в [...] списке */
int ok, notflag;
for (;;) {
scc = U(*s++); /* очередной символ строки */
switch (c = U (*p++)) { /* очередной символ шаблона */
case QUOT: /* a*\*b */
c = U (*p++);
if( c == 0 ) return(0); /* ошибка: pattern\ */
else goto def;
case '[': /* любой символ из списка */
ok = notflag = 0;
lc = 077777; /* достаточно большое число */
if(*p == '!'){ notflag=1; p++; }
while (cc = U (*p++)) {
if (cc == ']') { /* конец перечисления */
if (ok)
break; /* сопоставилось */
return (0); /* не сопоставилось */
}
if (cc == '-') { /* интервал символов */
if (notflag){
/* не из диапазона - OK */
if (!syinsy (lc, scc, U (*p++)))
ok++;
/* из диапазона - неудача */
else return (0);
} else {
/* символ из диапазона - OK */
if (syinsy (lc, scc, U (*p++)))
ok++;
}
}
else {
if (cc == QUOT){ /* [\[\]] */
cc = U(*p++);
if(!cc) return(0);/* ошибка */
}
if (notflag){
if (scc && scc != (lc = cc))
ok++; /* не входит в список */
else return (0);
} else {
А. Богатырев, 1992-95 - 311 - Си в UNIX
if (scc == (lc = cc)) /* входит в список */
ok++;
}
}
}
if (cc == 0){ /* конец строки */
MATCH_ERR;
return (0); /* ошибка */
}
continue;
case '*': /* любое число любых символов */
if (!*p)
return (1);
for (s--; *s; s++)
if (match (s, p))
return (1);
return (0);
case 0:
return (scc == 0);
default: def:
if (c != scc)
return (0);
continue;
case '?': /* один любой символ */
if (scc == 0)
return (0);
continue;
}
}
}
/* Проверить, что smy лежит между smax и smin
*/
int syinsy (unsigned smin, unsigned smy, unsigned smax)
{
char left [2];
char right [2];
char middle [2];
left [0] = smin; left [1] = '\0';
right [0] = smax; right [1] = '\0';
middle[0] = smy; middle[1] = '\0';
return (strcoll(left, middle) <= 0 && strcoll(middle, right) <= 0);
}
Обратите внимание на то, что в UNIX расширением шаблонов имен файлов, вроде *.c,
занимается не операционная система (как в MS DOS), а программа-интерпретатор команд
пользователя (shell: /bin/sh, /bin/csh, /bin/ksh). Это позволяет обрабатывать (в
принципе) разные стили шаблонов имен.
7.42. Изучите раздел руководства man regexp и include-файл /usr/include/regexp.h,
содержащий исходные тексты функций compile и step для регулярного выражения в стиле
программ ed, lex, grep:
одна буква C
или заэкранированный спецсимвол \. \[ \* \$ \^ \\ означают сами себя;
А. Богатырев, 1992-95 - 312 - Си в UNIX
. означает один любой символ кроме \n;
[abc]
или [a-b] означает любой символ из перечисленных (из интервала);
[abc-]
минус в конце означает сам символ -;
[]abc]
внутри [] скобка ] на первом месте означает сама себя;
[^a-z]
крышка ^ означает отрицание, т.е. любой символ кроме перечисленных;
[a-z^]
крышка не на первом месте означает сама себя;
[\*.]
спецсимволы внутри [] не несут специального значения, а представляют сами себя;
C* любое (0 и более) число символов C;
.* любое число любых символов;
выражение*
любое число (0 и более) повторений выражения, например [0-9]* означает число
(последовательность цифр) или пустое место. Ищется самое длинное прижатое влево
подвыражение;
выражение\{n,m\}
повторение выражения от n до m раз (включительно), где числа не превосходят 255;
выражение\{n,\}
повторение по крайней мере n раз, например [0-9]\{1,\} означает число;
выражение\{n\}
повторение ровно n раз;
выражение$
строка, чей конец удовлетворяет выражению, например .*define.*\\$
^выражение
строка, чье начало удовлетворяет выражению;
\n символ перевода строки;
\(.....\)
сегмент. Сопоставившаяся с ним подстрока будет запомнена;
\N где N цифра. Данный участок образца должен совпадать с N-ым сегментом (нумерация
с 1).
Напишите функцию matchReg, использующую этот стиль регулярных выражений. Сохраняйте
шаблон, при вызове matchReg сравнивайте старый шаблон с новым. Перекомпиляцию следует
производить только если шаблон изменился:
#include <stdio.h>
#include <ctype.h>
#define INIT register char *sp = instring;
#define GETC() (*sp++)
#define PEEKC() (*sp)
#define UNGETC(c) (--sp)
#define RETURN(ptr) return
#define ERROR(code) \
{fprintf(stderr,"%s:ERR%d\n",instring,code);exit(177);}
# include <regexp.h>
#define EOL '\0' /* end of line */
#define ESIZE 512
int matchReg(char *str, char *pattern){
static char oldPattern[256];
static char compiledExpr[ESIZE];
if( strcmp(pattern, oldPattern)){ /* различны */
/* compile regular expression */
compile(pattern,
compiledExpr, &compiledExpr[ESIZE], EOL);
А. Богатырев, 1992-95 - 313 - Си в UNIX
strcpy(oldPattern, pattern); /* запомнить */
}
return step(str, compiledExpr); /* сопоставить */
}
/* Пример вызова: reg '^int' 'int$' char | less */
/* reg 'putchar.*(.*)' < reg.c | more */
void main(int ac, char **av){
char inputline[BUFSIZ]; register i;
while(gets(inputline)){
for(i=1; i < ac; i++)
if(matchReg(inputline, av[i])){
char *p; extern char *loc1, *loc2;
/*printf("%s\n", inputline);*/
/* Напечатать строку,
* выделяя сопоставившуюся часть жирно */
for(p=inputline; p != loc1; p++) putchar(*p);
for( ; p != loc2; p++)
if(isspace((unsigned char) *p))
putchar(*p);
else printf("%c\b%c", *p, *p);
for( ; *p; p++) putchar(*p);
putchar('\n');
break;
}
}
}
7.43. Используя <regexp.h> напишите программу, производящую контекстную замену во
всех строках файла. Если строка не удовлетворяет регулярному выражению - она остается
неизменной. Примеры вызова:
$ regsub '\([0-9]\{1,\}\)' '(\1)'
$ regsub 'f(\(.*\),\(.*\))' 'f(\2,\1)' < file
Вторая команда должна заменять все вхождения f(a,b) на f(b,a). Выражение, обозначен-
ное в образце как \(...\), подставляется на место соответствующей конструкции \N во
втором аргументе, где N - цифра, номер сегмента. Чтобы поместить в выход сам символ
\, его надо удваивать: \\.
А. Богатырев, 1992-95 - 314 - Си в UNIX
/* Контекстная замена */
#include <stdio.h>
#include <ctype.h>
#define INIT register char *sp = instring;
#define GETC() (*sp++)
#define PEEKC() (*sp)
#define UNGETC(c) (--sp)
#define RETURN(ptr) return
#define ERROR(code) regerr(code)
void regerr();
# include <regexp.h>
#define EOL '\0' /* end of line */
#define ESIZE 512
short all = 0;
/* ключ -a означает, что в строке надо заменить ВСЕ вхождения образца (global, all):
* regsub -a int INT
* "aa int bbb int cccc" -> "aa INT bbb INT cccc"
*
* step() находит САМУЮ ДЛИННУЮ подстроку, удовлетворяющую выражению,
* поэтому regsub 'f(\(.*\),\(.*\))' 'f(\2,\1)'
* заменит "aa f(1,2) bb f(3,4) cc" -> "aa f(4,1,2) bb f(3) cc'
* |___________|_| |_|___________|
*/
char compiled[ESIZE], line[512];
А. Богатырев, 1992-95 - 315 - Си в UNIX
void main(int ac, char *av[]){
register char *s, *p; register n; extern int nbra;
extern char *braslist[], *braelist[], *loc1, *loc2;
if( ac > 1 && !strcmp(av[1], "-a")){ ac--; av++; all++; }
if(ac != 3){
fprintf(stderr, "Usage: %s [-a] pattern subst\n", av[0]);
exit(1);
}
compile(av[1], compiled, compiled + sizeof compiled, EOL);
while( gets(line) != NULL ){
if( !step(s = line, compiled)){
printf("%s\n", line); continue;
}
do{
/* Печатаем начало строки */
for( ; s != loc1; s++) putchar(*s);
/* Делаем замену */
for(s=av[2]; *s; s++)
if(*s == '\\'){
if(isdigit(s[1])){ /* сегмент */
int num = *++s - '1';
if(num < 0 || num >= nbra){
fprintf(stderr, "Bad block number %d\n", num+1);
exit(2);
}
for(p=braslist[num]; p != braelist[num]; ++p)
putchar(*p);
} else if(s[1] == '&'){
++s; /* вся сопоставленная строка */
for(p=loc1; p != loc2; ++p)
putchar(*p);
} else putchar(*++s);
} else putchar(*s);
} while(all && step(s = loc2, compiled));
/* Остаток строки */
for(s=loc2; *s; s++) putchar(*s);
putchar('\n');
} /* endwhile */
}
А. Богатырев, 1992-95 - 316 - Си в UNIX
void regerr(int code){ char *msg;
switch(code){
case 11: msg = "Range endpoint too large."; break;
case 16: msg = "Bad number."; break;
case 25: msg = "\\digit out of range."; break;
case 36: msg = "Illegal or missing delimiter."; break;
case 41: msg = "No remembered search string."; break;
case 42: msg = "\\(~\\) imbalance."; break;
case 43: msg = "Too many \\(."; break;
case 44: msg = "More than 2 numbers given in \\{~\\\"}."; break;
case 45: msg = "} expected after \\."; break;
case 46: msg = "First number exceeds second in \\{~\\}."; break;
case 49: msg = "[ ] imbalance."; break;
case 50: msg = "Regular expression overflow."; break;
default: msg = "Unknown error"; break;
} fputs(msg, stderr); fputc('\n', stderr); exit(code);
}
void prfields(){
int i;
for(i=0; i < nbra; i++)
prfield(i);
}
void prfield(int n){
char *fbeg = braslist[n], *fend = braelist[n];
printf("\\%d='", n+1);
for(; fbeg != fend; fbeg++)
putchar(*fbeg);
printf("'\n");
}
7.44. Составьте функцию поиска подстроки в строке. Используя ее, напишите программу
поиска подстроки в текстовом файле. Программа должна выводить строки (либо номера
строк) файла, в которых встретилась данная подстрока. Подстрока задается в качестве
аргумента функции main().
/* Алгоритм быстрого поиска подстроки.
* Дж. Мур, Р. Бойер, 1976 Texas
* Смотри: Communications of the ACM 20, 10 (Oct., 1977), 762-772
*
* Этот алгоритм выгоден при многократном поиске образца в
* большом количестве строк, причем если они равной длины -
* можно сэкономить еще и на операции strlen(str).
* Алгоритм характерен тем, что при неудаче производит сдвиг не на
* один, а сразу на несколько символов вправо.
* В лучшем случае алгоритм делает slen/plen сравнений.
*/
char *pattern; /* образец (что искать) */
static int plen; /* длина образца */
static int d[256]; /* таблица сдвигов; в алфавите ASCII -
* 256 букв. */
/* расстояние от конца образца до позиции i в нем */
#define DISTANCE(i) ((plen-1) - (i))
А. Богатырев, 1992-95 - 317 - Си в UNIX
/* Поиск:
* выдать индекс вхождения pattern в str,
* либо -1, если не входит
*/
int indexBM( str ) char *str; /* в чем искать */
{
int slen = strlen(str); /* длина строки */
register int pindx; /* индекс сравниваемой буквы в образце */
register int cmppos; /* индекс сравниваемой буквы в строке */
register int endpos; /* позиция в строке, к которой "приставляется"
* последняя буква образца */
/* пока образец помещается в остаток строки */
for( endpos = plen-1; endpos < slen ; ){
/* Для отладки: pr(str, pattern, endpos - (plen-1), 0); /**/
/* просмотр образца от конца к началу */
for( cmppos = endpos, pindx = (plen - 1);
pindx >= 0 ;
cmppos--, pindx-- )
if( str[cmppos] != pattern[pindx] ){
/* Сдвиг, который ставит самый правый в образце
* символ str[endpos] как раз под endpos-тую
* позицию строки. Если же такой символ в образце не
* содержится (или содержится только на конце),
* то начало образца устанавливается в endpos+1 ую
* позицию
*/
endpos += d[ str[endpos] & 0377 ];
break; /* & 0377 подавляет расширение знака. Еще */
} /* можно сделать все char -> unsigned char */
if( pindx < 0 ) return ( endpos - (plen-1));
/* Нашел: весь образец вложился */
}
return( -1 ); /* Не найдено */
}
А. Богатырев, 1992-95 - 318 - Си в UNIX
/* Разметка таблицы сдвигов */
void compilePatternBM( ptrn ) char *ptrn; {
register int c;
pattern = ptrn; plen = strlen(ptrn);
/* c - номер буквы алфавита */
for(c = 0; c < 256; c++)
d[c] = plen;
/* сдвиг на длину всего образца */
/* c - позиция в образце */
for(c = 0; c < plen - 1; c++)
d[ pattern[c] & 0377 ] = DISTANCE(c);
/* Сдвиг равен расстоянию от самого правого
* (кроме последней буквы образца)
* вхождения буквы в образец до конца образца.
* Заметим, что если буква входит в образец несколько раз,
* то цикл учитывает последнее (самое правое) вхождение.
*/
}
/* Печать найденных строк */
void pr(s, p, n, nl) char *s, *p;
{
register i;
printf("%4d\t%s\n", nl, s );
printf(" \t");
for(i = 0; i < n; i++ )
putchar( s[i] == '\t' ? '\t' : ' ' );
printf( "%s\n", p );
}
/* Аналог программы fgrep */
#include <stdio.h>
char str[ 1024 ]; /* буфер для прочитанной строки */
void main(ac, av) char **av;
{
int nline = 0; /* номер строки файла */
int ind;
int retcode = 1;
if(ac != 2){
fprintf(stderr, "Usage: %s 'pattern'\n", av[0] );
exit(33);
}
compilePatternBM( av[1] );
while( gets(str) != NULL ){
nline++;
if((ind = indexBM(str)) >= 0 ){
retcode = 0; /* O'KAY */
pr(str, pattern, ind, nline);
}
}
exit(retcode);
}
А. Богатырев, 1992-95 - 319 - Си в UNIX
/* Пример работы алгоритма:
peter piper picked a peck of pickled peppers.
peck
peter piper picked a peck of pickled peppers.
peck
peter piper picked a peck of pickled peppers.
peck
peter piper picked a peck of pickled peppers.
peck
peter piper picked a peck of pickled peppers.
peck
peter piper picked a peck of pickled peppers.
peck
peter piper picked a peck of pickled peppers.
peck
peter piper picked a peck of pickled peppers.
peck
*/
7.45. Напишите аналогичную программу, выдающую все строки, удовлетворяющие упрощен-
ному регулярному выражению, задаваемому как аргумент для main(). Используйте функцию
match, написанную нами ранее. Вы написали аналог программы grep из UNIX (но с другим
типом регулярного выражения, нежели в оригинале).
7.46. Составьте функцию expand(s1, s2), которая расширяет сокращенные обозначения
вида a-z строки s1 в эквивалентный полный список abcd...xyz в строке s2. Допускаются
сокращения для строчных и прописных букв и цифр. Учтите случаи типа a-b-c, a-z0-9 и
-a-g (соглашение состоит в том, что символ "-", стоящий в начале или в конце, воспри-
нимается буквально).
7.47. Напишите программу, читающую файл и заменяющую строки вида
|<1 и более пробелов и табуляций><текст>
на пары строк
|.pp
|<текст>
(здесь | обозначает левый край файла, a <> - метасимволы). Это - простейший препро-
цессор, готовящий текст в формате nroff (это форматтер текстов в UNIX). Усложнения:
- строки, начинающиеся с точки или с апострофа, заменять на
\&<текст, начинающийся с точки или '>
- строки, начинающиеся с цифры, заменять на
.ip <число>
<текст>
- символ \ заменять на последовательность \e.
- удалять пробелы перед символами .,;:!?) и вставлять после них пробел (знак пре-
пинания должен быть приклеен к концу слова, иначе он может быть перенесен на
следующую строку. Вы когда-нибудь видели строку, начинающуюся с запятой?).
- склеивать перенесенные слова, поскольку nroff делает переносы сам:
....xxxx начало- => ....xxxx началоконец
конец yyyy...... yyyy................
А. Богатырев, 1992-95 - 320 - Си в UNIX
Вызывайте этот препроцессор разметки текста так:
$ prep файлы... | nroff -me > text.lp
7.48. Составьте программу преобразования прописных букв из файла ввода в строчные,
используя при этом функцию, в которой необходимо организовать анализ символа (дейст-
вительно ли это буква). Строчные буквы выдавать без изменения. Указание: используйте
макросы из <ctype.h>.
Ответ:
#include <ctype.h>
#include <stdio.h>
main(){
int c;
while( (c = getchar()) != EOF )
putchar( isalpha( c ) ?
(isupper( c ) ? tolower( c ) : c) : c);
}
либо ...
putchar( isalpha(c) && isupper(c) ? tolower(c) : c );
либо даже
putchar( isupper(c) ? tolower(c) : c );
В последнем случае под isupper и islower должны пониматься только буквы (увы, не во
всех реализациях это так!).
7.49. Обратите внимание, что если мы выделяем класс символов при помощи сравнения,
например:
char ch;
if( 0300 <= ch && ch < 0340 ) ...;
(в кодировке КОИ-8 это маленькие русские буквы), то мы можем натолкнуться на следую-
щий сюрприз: перед сравнением с целым значение ch приводится к типу int (приведение
также делается при использовании char в качестве аргумента функции). При этом, если
у ch был установлен старший бит (0200), произойдет расширение его во весь старший
байт (расширение знакового бита). Результатом будет отрицательное целое число! Опыт:
char c = '\201'; /* = 129 */
printf( "%d\n", c );
печатается -127. Таким образом, наше сравнение не сработает, т.к. оказывается что ch
< 0. Следует подавлять расширение знака:
if( 0300 <= (ch & 0377) && (ch & 0377) < 0340) ...;
(0377 - маска из 8 бит, она же 0xFF, весь байт), либо объявить
unsigned char ch;
что означает, что при приведении к int знаковый бит не расширяется.
7.50. Рассмотрим еще один пример:
А. Богатырев, 1992-95 - 321 - Си в UNIX
main(){
char ch;
/* 0377 - код последнего символа алфавита ASCII */
for (ch = 0100; ch <= 0377; ch++ )
printf( "%03o %s\n",
ch & 0377,
ch >= 0300 && ch < 0340 ? "yes" : "no" );
}
Какие неприятности ждут нас здесь?
- во-первых, когда бит 0200 у ch установлен, в сравнении ch выступает как отрица-
тельное целое число (т.к. приведение к int делается расширением знакового бита),
то есть у нас всегда печатается "no". Это мы можем исправить, написав
unsigned char ch, либо используя ch в виде
(ch & 0377) или ((unsigned) ch)
- во-вторых, рассмотрим сам цикл. Пусть сейчас ch =='\377'. Условие ch <= 0377
истинно. Выполняется оператор ch++. Но ch - это байт, поэтому операции над ним
производятся по модулю 0400 (0377 - это максимальное значение, которое можно
хранить в байте - все биты единицы). То есть теперь значением ch станет 0. Но
0 < 0377 и условие цикла верно! Цикл продолжается; т.е. происходит зациклива-
ние. Избежать этого можно только описав int ch; чтобы 0377+1 было равно 0400, а
не 0 (или unsigned int, лишь бы длины переменной хватало, чтобы вместить число
больше 0377).
7.51. Составьте программу, преобразующую текст, состоящий только из строчных букв в
текст, состоящий из прописных и строчных букв. Первая буква и буква после каждой
точки - прописные, остальные - строчные.
слово один. слово два. -->
Слово один. Слово два.
Эта программа может оказаться полезной для преобразования текста, набранного в одном
регистре, в текст, содержащий буквы обоих регистров.
7.52. Напишите программу, исправляющую опечатки в словах (spell check): программе
задан список слов; она проверяет - является ли введенное вами слово словом из списка.
Если нет - пытается найти наиболее похожее слово из списка, причем если есть нес-
колько похожих - выдает все варианты. Отлавливайте случаи:
- две соседние буквы переставлены местами: ножинцы=>ножницы;
- удвоенная буква (буквы): ккаррандаш=>карандаш;
- потеряна буква: бот=>болт;
- измененная буква: бинт=>бант;
- лишняя буква: морда=>мода;
- буквы не в том регистре - сравните с каждым словом из списка, приводя все буквы
к маленьким: сОВОк=>совок;
Надо проверять каждую букву слова. Возможно вам будет удобно использовать рекурсию.
Подсказка: для некоторых проверок вам может помочь функция match:
слово_таблицы = "дом";
if(strlen(входное_слово) <= strlen(слово_таблицы)+1 &&
match(входное_слово, "*д*о*м*") ... /* похоже */
*о*м* ?дом дом?
*д*м* д?ом
*д*о* до?м
Приведем вариант решения этой задачи:
А. Богатырев, 1992-95 - 322 - Си в UNIX
#include <stdio.h>
#include <ctype.h>
#include <locale.h>
typedef unsigned char uchar;
#define ANYCHAR '*'
/* символ, сопоставляющийся с одной любой буквой */
static uchar version[120]; /* буфер для генерации вариантов */
static uchar vv; /* буква, сопоставившаяся с ANYCHAR */
/* привести все буквы к одному регистру */
static uchar icase(uchar c){
return isupper(c) ? tolower(c) : c;
}
/* сравнение строк с игнорированием регистра */
static int eqi(uchar *s1, uchar *s2 )
{
while( *s1 && *s2 ){
if( icase( *s1 ) != icase( *s2 ))
break;
s1++; s2++;
}
return ( ! *s1 && ! *s2 ) ? 1 : 0 ;
/* OK : FAIL */
}
/* сравнение строк с игнорированием ANYCHAR */
static strok(register uchar *word, register uchar *pat)
{
while( *word && *pat ){
if( *word == ANYCHAR){
/* Неважно, что есть *pat, но запомним */
vv= *pat;
} else {
if( icase(*pat) != icase(*word) )
break;
}
word++; pat++;
}
/* если слова кончились одновременно ... */
return ( !*word && !*pat) ? 1 : 0;
/* OK : FAIL */
}
А. Богатырев, 1992-95 - 323 - Си в UNIX
/* ЛИШНЯЯ БУКВА */
static int superfluous( uchar *word /* слово для коррекции */
, uchar *s /* эталон */
){
register int i,j,k;
int reply;
register len = strlen(word);
for(i=0 ; i < len ; i++){
/* генерим слова , получающиеся удалением одной буквы */
k=0;
for(j=0 ; j < i ; j++)
version[k++]=word[j];
for(j=i+1 ; j < len ; j++)
version[k++]=word[j];
version[k]='\0';
if( eqi( version, s )) return 1; /* OK */
}
return 0; /* FAIL */
}
/* ПОТЕРЯНА БУКВА */
static int hole; /* место, где вставлена ANYCHAR */
static int lost(uchar *word, uchar *s)
{
register int i,j,k;
register len = strlen(word);
hole= (-1);
for(i=0 ; i < len+1 ; i++){
k=0;
for(j=0 ; j < i ; j++)
version[k++]=word[j];
version[k++]=ANYCHAR;
for(j=i ; j < len ; j++)
version[k++]=word[j];
version[k]='\0';
if( strok( version, s )){
hole=i;
return 1; /* OK */
}
}
return 0; /* FAIL */
}
А. Богатырев, 1992-95 - 324 - Си в UNIX
/* ИЗМЕНИЛАСЬ ОДНА БУКВА (включает случай ошибки регистра) */
static int changed(uchar *word, uchar *s)
{
register int i,j,k;
register len = strlen(word);
hole = (-1);
for(i=0 ; i < len ; i++){
k=0;
for( j=0 ; j < i ; j++)
version[k++]=word[j];
version[k++]=ANYCHAR;
for( j=i+1 ; j < len ; j++)
version[k++]=word[j];
version[k]='\0';
if( strok( version,s)){
hole=i;
return 1; /* OK */
}
}
return 0; /* FAIL */
}
/* УДВОЕННАЯ БУКВА */
static int duplicates(uchar *word, uchar *s, int leng)
{
register int i,j,k;
uchar tmp[80];
if( eqi( word, s )) return 1; /* OK */
for(i=0;i < leng - 1; i++)
/* ищем парные буквы */
if( word[i]==word[i+1]){
k=0;
for(j=0 ; j < i ; j++)
tmp[k++]=word[j];
for(j=i+1 ; j < leng ; j++)
tmp[k++]=word[j];
tmp[k]='\0';
if( duplicates( tmp, s, leng-1) == 1)
return 1; /* OK */
}
return 0; /* FAIL */
}
А. Богатырев, 1992-95 - 325 - Си в UNIX
/* ПЕРЕСТАВЛЕНЫ СОСЕДНИЕ БУКВЫ */
static int swapped(uchar *word, uchar *s)
{
register int i,j,k;
register len = strlen(word);
for(i=0;i < len-1;i++){
k=0;
for(j=0 ; j < i ; j++)
version[k++]=word[j];
version[k++]=word[i+1];
version[k++]=word[i];
for(j=i+2 ; j < len ; j++)
version[k++]=word[j];
version[k]='\0';
if( eqi( version, s))
return 1; /* OK */
}
return 0; /* FAIL */
}
uchar *words[] = {
(uchar *) "bag",
(uchar *) "bags",
(uchar *) "cook",
(uchar *) "cool",
(uchar *) "bug",
(uchar *) "buy",
(uchar *) "cock",
NULL
};
#define Bcase(x, operators) case x: { operators; } break;
char *cname[5] = {
"переставлены буквы",
"удвоены буквы ",
"потеряна буква ",
"ошибочная буква ",
"лишняя буква "
};
А. Богатырев, 1992-95 - 326 - Си в UNIX
static int spellmatch( uchar *word /* IN слово для коррекции */
, uchar *words[] /* IN таблица допустимых слов */
, uchar **indx /* OUT ответ */
){
int i, code, total = (-1);
uchar **ptr;
if(!*word) return -1;
for(ptr = words; *ptr; ++ptr)
if(eqi(word, *ptr)){
if(indx) *indx = *ptr;
return 0;
}
/* Нет в таблице, нужен подбор похожих */
for(ptr = words; *ptr; ++ptr){
uchar *s = *ptr;
int max = 5;
for(i=0; i < max; i++){
switch( i ){
Bcase(0,code = swapped(word, s) )
Bcase(1,code = duplicates(word, s, strlen(word)) )
Bcase(2,code = lost(word, s) )
Bcase(3,code = changed(word, s) )
Bcase(4,code = superfluous(word, s) )
}
if(code){
total++;
printf("?\t%s\t%s\n", cname[i], s);
if(indx) *indx = s;
/* В случае с дубликатами не рассматривать
* на наличие лишних букв
*/
if(i==1) max = 4;
}
}
}
return total;
}
А. Богатырев, 1992-95 - 327 - Си в UNIX
void main(){
uchar inpbuf[BUFSIZ];
int n;
uchar *reply, **ptr;
setlocale(LC_ALL, "");
for(ptr = words; *ptr; ptr++)
printf("#\t%s\n", *ptr);
do{
printf("> "); fflush(stdout);
if(gets((char *)inpbuf) == NULL) break;
switch(spellmatch(inpbuf, words, &reply)){
case -1:
printf("Нет такого слова\n"); break;
case 0:
printf("Слово '%s'\n", reply); break;
default:
printf("Неоднозначно\n");
}
} while(1);
}
7.53. Пока я сам писал эту программу, я сделал две ошибки, которые должны быть
весьма характерны для новичков. Про них надо бы говорить раньше, в главе про строки и
в самой первой главе, но тут они пришлись как раз к месту. Вопрос: что печатает сле-
дующая программа?
#include <stdio.h>
char *strings[] = {
"Первая строка"
"Вторая строка"
"Третяя строка",
"Четвертая строка",
NULL
};
void main(){
char **p;
for(p=strings;*p;++p)
printf("%s\n", *p);
}
А печатает она вот что:
Первая строкаВторая строкаТретяя строка
Четвертая строка
Дело в том, что ANSI компилятор Си склеивает строки:
"начало строки" "и ее конец"
если они разделены пробелами в смысле isspace, в том числе и пустыми строками. А в
нашем объявлении массива строк strings мы потеряли несколько разделительных запятых!
Вторая ошибка касается того, что можно забыть поставить слово break в операторе
switch, и долго после этого гадать о непредсказуемом поведении любого поступающего на
вход значения. Дело просто: пробегаются все случаи, управление проваливается из case
в следующий case, и так много раз подряд! Это и есть причина того, что в предыдущем
А. Богатырев, 1992-95 - 328 - Си в UNIX
примере все case оформлены нетривиальным макросом Bcase.
7.54. Составьте программу кодировки и раскодировки файлов по заданному ключу (строке
символов).
7.55. Составьте программу, которая запрашивает анкетные данные типа фамилии, имени,
отчества, даты рождения и формирует файл. Программа должна отлавливать ошибки ввода
несимвольной и нецифровой информации, выхода составляющих даты рождения за допустимые
границы с выдачей сообщений об ошибках. Программа должна давать возможность корректи-
ровать вводимые данные. Все данные об одном человеке записываются в одну строку файла
через пробел. Вот возможный пример части диалога (ответы пользователя выделены
жирно):
Введите месяц рождения [1-12]: 14 <ENTER>
*** Неправильный номер месяца (14).
Введите месяц рождения [1-12]: март <ENTER>
*** Номер месяца содержит букву 'м'.
Введите месяц рождения [1-12]: <ENTER>
Вы хотите закончить ввод ? n
Введите месяц рождения [1-12]: 11 <ENTER>
Ноябрь
Введите дату рождения [1-30]: _
В таких программах обычно ответ пользователя вводится как строка:
printf("Введите месяц рождения [1-12]: ");
fflush(stdout); gets(input_string);
затем (если надо) отбрасываются лишние пробелы в начале и в конце строки, затем вве-
денный текст input_string анализируется на допустимость символов (нет ли в нем не
цифр?), затем строка преобразуется к нужному типу (например, при помощи функции atoi
переводится в целое) и проверяется допустимость полученного значения, и.т.д.
Вводимую информацию сначала заносите в структуру; затем записывайте содержимое
полей структуры в файл в текстовом виде (используйте функцию fprintf, а не fwrite).
7.56. Составьте программу, осуществляющую выборку информации из файла, сформирован-
ного в предыдущей задаче, и ее распечатку в табличном виде. Выборка должна осуществ-
ляться по значению любого заданного поля (т.е. вы выбираете поле, задаете его значе-
ние и получаете те строки, в которых значение указанного поля совпадает с заказанным
вами значением). Усложнение: используйте функцию сравнения строки с регулярным выра-
жением для выборки по шаблону поля (т.е. отбираются только те строки, в которых зна-
чение заданного поля удовлетворяет шаблону). Для чтения файла используйте fscanf,
либо fgets и затем sscanf. Второй способ лучше тем, что позволяет проверить по шаб-
лону значение любого поля - не только текстового, но и числового: так 1234 (строка -
изображение числа) удовлетворяет шаблону "12*".
7.57. Составьте вариант программы подсчета служебных слов языка Си, не учитывающий
появление этих слов, заключенных в кавычки.
7.58. Составьте программу удаления из программы на языке Си всех комментариев. Обра-
тите внимание на особые случаи со строками в кавычках и символьными константами; так
строка
char s[] = "/*";
не является началом комментария! Комментарии записывайте в отдельный файл.
7.59. Составьте программу выдачи перекрестных ссылок, т.е. программу, которая выво-
дит список всех идентификаторов переменных, используемых в программе, и для каждого
из идентификаторов выводит список номеров строк, в которые он входит.
А. Богатырев, 1992-95 - 329 - Си в UNIX
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*/
А. Богатырев, 1992-95 - 330 - Си в UNIX
#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);} /* прыгнуть в контрольную точку */
А. Богатырев, 1992-95 - 331 - Си в UNIX
/* ВЫЧИСЛИТЕЛЬ --------------------------------------- */
/* Если вместо помещения операндов в стек 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');
}
А. Богатырев, 1992-95 - 332 - Си в UNIX
/* КОМПИЛЯТОР ---------------------------------------- */
/* номера лексем */
#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); }
А. Богатырев, 1992-95 - 333 - Си в UNIX
/* Таблица приоритетов */
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; /* предыдущая лексема */
А. Богатырев, 1992-95 - 334 - Си в UNIX
/* Транслятор в польскую запись + интерпретатор */
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();
}
А. Богатырев, 1992-95 - 335 - Си в UNIX
/* Прочесть число (с точкой) */
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);
}
А. Богатырев, 1992-95 - 336 - Си в UNIX
/* прочесть открывающую скобку после имени функции */
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
*/
7.68. Приведем еще один арифметический вычислитель, использующий классический рекур-
сивный подход:
/* Калькулятор на основе рекурсивного грамматического разбора.
* По мотивам арифметической части программы csh (СиШелл).
* csh написан Биллом Джоем (Bill Joy).
: var1 = (x = 1+3) * (y=x + x++) 36
: s = s + 1 ошибка
: y 9
: s = (1 + 1 << 2) == 1 + (1<<2) 0
: var1 + 3 + -77 -38
: a1 = 3; a2 = (a4=a3 = 2; a1++)+a4+2 8
: sum(a=2;b=3, a++, a*3-b) 12
*/
#include <stdio.h>
#include <ctype.h>
#include <setjmp.h>
typedef enum { NUM, ID, OP, OPEN, CLOSE, UNKNOWN, COMMA, SMC } TokenType;
char *toknames[] = { "number", "identifier", "operation",
"open_paren", "close_paren", "unknown", "comma", "semicolon" };
typedef struct _Token {
char *token; /* лексема (слово) */
struct _Token *next; /* ссылка на следующую */
TokenType type; /* тип лексемы */
} Token;
extern void *malloc(unsigned); extern char *strchr(char *, char);
char *strdup(const char *s){
char *p = (char *)malloc(strlen(s)+1);
if(p) strcpy(p,s); return p;
}
А. Богатырев, 1992-95 - 337 - Си в UNIX
/* Лексический разбор ------------------------------------------*/
/* Очистить цепочку токенов */
void freelex(Token **p){
Token *thisTok = *p;
while( thisTok ){ Token *nextTok = thisTok->next;
free((char *) thisTok->token); free((char *) thisTok);
thisTok = nextTok;
}
*p = NULL;
}
/* Добавить токен в хвост списка */
void addtoken(Token **hd, Token **tl, char s[], TokenType t){
Token *newTok = (Token *) malloc(sizeof(Token));
newTok->next = (Token *) NULL;
newTok->token = strdup(s); newTok->type = t;
if(*hd == NULL) *hd = *tl = newTok;
else{ (*tl)->next = newTok; *tl = newTok; }
}
/* Разобрать строку в список лексем (токенов) */
#define opsym(c) ((c) && strchr("+-=!~^|&*/%<>", (c)))
#define is_alpha(c) (isalpha(c) || (c) == '_')
#define is_alnum(c) (isalnum(c) || (c) == '_')
void lex(Token **hd, Token **tl, register char *s){
char *p, csave; TokenType type;
while(*s){
while( isspace(*s)) ++s; p = s;
if( !*s ) break;
if(isdigit (*s)){ type = NUM; while(isdigit (*s))s++; }
else if(is_alpha(*s)){ type = ID; while(is_alnum(*s))s++; }
else if(*s == '('){ type = OPEN; s++; }
else if(*s == ')'){ type = CLOSE; s++; }
else if(*s == ','){ type = COMMA; s++; }
else if(*s == ';'){ type = SMC; s++; }
else if(opsym(*s)){ type = OP; while(opsym(*s)) s++; }
else { type = UNKNOWN; s++; }
csave = *s; *s = '\0'; addtoken(hd, tl, p, type); *s = csave;
}
}
/* Распечатка списка лексем */
void printlex(char *msg, Token *t){
if(msg && *msg) printf("%s: ", msg);
for(; t != NULL; t = t->next)
printf("%s`%s' ", toknames[(int)t->type], t->token);
putchar('\n');
}
А. Богатырев, 1992-95 - 338 - Си в UNIX
/* Система переменных ----------------------------------------- */
#define NEXT(v) *v = (*v)->next
#define TOKEN(v) (*v)->token
#define TYPE(v) (*v)->type
#define eq(str1, str2) (!strcmp(str1, str2))
jmp_buf breakpoint;
#define ERR(msg,val) { printf("%s\n", msg);longjmp(breakpoint, val+1);}
typedef struct {
char *name; /* Имя переменной */
int value; /* Значение переменной */
int isset; /* Получила ли значение ? */
} Var;
#define MAXV 40
Var vars[MAXV];
/* Получить значение переменной */
int getVar(char *name){ Var *ptr;
for(ptr=vars; ptr->name; ptr++)
if(eq(name, ptr->name)){
if(ptr->isset) return ptr->value;
printf("%s: ", name); ERR("variable is unbound yet", 0);
}
printf("%s: ", name); ERR("undefined variable", 0);
}
/* Создать новую переменную */
Var *internVar(char *name){ Var *ptr;
for(ptr=vars; ptr->name; ptr++)
if(eq(name, ptr->name)) return ptr;
ptr->name = strdup(name);
ptr->isset = 0; ptr->value = 0; return ptr;
}
/* Установить значение переменной */
void setVar(Var *ptr, int val){ ptr->isset = 1; ptr->value = val; }
/* Распечатать значения переменных */
void printVars(){ Var *ptr;
for(ptr=vars; ptr->name; ++ptr)
printf("\t%s %s %d\n", ptr->isset ? "BOUND ":"UNBOUND",
ptr->name, ptr->value);
}
А. Богатырев, 1992-95 - 339 - Си в UNIX
/* Синтаксический разбор и одновременное вычисление ----------- */
/* Вычисление встроенных функций */
int apply(char *name, int args[], int nargs){
if(eq(name, "power2")){
if(nargs != 1) ERR("power2: wrong argument count", 0);
return (1 << args[0]);
} else if(eq(name, "min")){
if(nargs != 2) ERR("min: wrong argument count", 0);
return (args[0] < args[1] ? args[0] : args[1]);
} else if(eq(name, "max")){
if(nargs != 2) ERR("max: wrong argument count", 0);
return (args[0] < args[1] ? args[1] : args[0]);
} else if(eq(name, "sum")){ register i, sum;
for(i=0, sum=0; i < nargs; sum += args[i++]);
return sum;
} else if(eq(name, "rand")){
switch(nargs){
case 0: return rand();
case 1: return rand() % args[0];
case 2: return args[0] + rand() % (args[1] - args[0] + 1);
default: ERR("rand: wrong argument count", 0);
}
}
ERR("Unknown function", args[0]);
}
/* Вычислить выражение из списка лексем. */
/* Синтаксис задан праворекурсивной грамматикой */
int expr(Token *t){ int val = 0;
if(val = setjmp(breakpoint)) return val - 1;
val = expression(&t);
if(t){ printlex(NULL, t); ERR("Extra tokens", val); }
return val;
}
/* <EXPRESSION> = <EXPASS> |
<EXPASS> ";" <EXPRESSION> */
int expression(Token **v){ int arg = expass(v);
if(*v && TYPE(v) == SMC ){
NEXT(v); return expression(v);
} else return arg;
}
/* <EXPASS> = <ПЕРЕМЕННАЯ> "=" <EXPASS> |
<EXP0> */
int expass(Token **v){ int arg;
if(*v && (*v)->next && (*v)->next->type == OP &&
eq((*v)->next->token, "=")){ Var *ptr;
/* присваивание (assignment) */
if( TYPE(v) != ID ) /* слева нужна переменная */
ERR("Lvalue needed", 0);
ptr = internVar(TOKEN(v));
NEXT(v); NEXT(v); setVar(ptr, arg = expass(v)); return arg;
}
return exp0(v);
}
А. Богатырев, 1992-95 - 340 - Си в UNIX
/* <EXP0> = <EXP1> | <EXP1> "||" <EXP0> */
int exp0(Token **v){ int arg = exp1(v);
if(*v && TYPE(v) == OP && eq(TOKEN(v), "||")){
NEXT(v); return(exp0(v) || arg );
/* помещаем arg ВТОРЫМ, чтобы второй операнд вычислялся
* ВСЕГДА (иначе не будет исчерпан список токенов и
* возникнет ошибка в expr(); Это не совсем по правилам Си.
*/
} else return arg;
}
/* <EXP1> = <EXP2> | <EXP2> "&&" <EXP1> */
int exp1(Token **v){ int arg = exp2(v);
if(*v && TYPE(v) == OP && eq(TOKEN(v), "&&")){
NEXT(v); return(exp1(v) && arg);
} else return arg;
}
/* <EXP2> = <EXP2A> | <EXP2A> "|" <EXP2> */
int exp2(Token **v){ int arg = exp2a(v);
if(*v && TYPE(v) == OP && eq(TOKEN(v), "|")){
NEXT(v); return( arg | exp2(v));
} else return arg;
}
/* <EXP2A> = <EXP2B> | <EXP2B> "^" <EXP2A> */
int exp2a(Token **v){ int arg = exp2b(v);
if(*v && TYPE(v) == OP && eq(TOKEN(v), "^")){
NEXT(v); return( arg ^ exp2a(v));
} else return arg;
}
/* <EXP2B> = <EXP2C> | <EXP2C> "&" <EXP2B> */
int exp2b(Token **v){ int arg = exp2c(v);
if(*v && TYPE(v) == OP && eq(TOKEN(v), "&")){
NEXT(v); return( arg & exp2b(v));
} else return arg;
}
/* <EXP2C> = <EXP3> | <EXP3> "==" <EXP3>
| <EXP3> "!=" <EXP3> */
int exp2c(Token **v){ int arg = exp3(v);
if(*v && TYPE(v) == OP && eq(TOKEN(v), "==")){
NEXT(v); return( arg == exp3(v));
} else if(*v && TYPE(v) == OP && eq(TOKEN(v), "!=")){
NEXT(v); return( arg != exp3(v));
} else return arg;
}
А. Богатырев, 1992-95 - 341 - Си в UNIX
/* <EXP3> = <EXP3A> | <EXP3A> ">" <EXP3>
| <EXP3A> "<" <EXP3>
| <EXP3A> ">=" <EXP3>
| <EXP3A> "<=" <EXP3> */
int exp3(Token **v){ int arg = exp3a(v);
if(*v && TYPE(v) == OP && eq(TOKEN(v), ">")){
NEXT(v); return( arg && exp3(v));
}else if(*v && TYPE(v) == OP && eq(TOKEN(v), "<")){
NEXT(v); return( arg && exp3(v));
}else if(*v && TYPE(v) == OP && eq(TOKEN(v), ">=")){
NEXT(v); return( arg && exp3(v));
}else if(*v && TYPE(v) == OP && eq(TOKEN(v), "<=")){
NEXT(v); return( arg && exp3(v));
} else return arg;
}
/* <EXP3A> = <EXP4> | <EXP4> "<<" <EXP3A>
| <EXP4> ">>" <EXP3A> */
int exp3a(Token **v){ int arg = exp4(v);
if(*v && TYPE(v) == OP && eq(TOKEN(v), "<<")){
NEXT(v); return( arg << exp3a(v));
}else if(*v && TYPE(v) == OP && eq(TOKEN(v), ">>")){
NEXT(v); return( arg && exp3a(v));
} else return arg;
}
/* <EXP4> = <EXP5> | <EXP5> "+" <EXP4>
| <EXP5> "-" <EXP4> */
int exp4(Token **v){ int arg = exp5(v);
if(*v && TYPE(v) == OP && eq(TOKEN(v), "+")){
NEXT(v); return( arg + exp4(v));
}else if(*v && TYPE(v) == OP && eq(TOKEN(v), "-")){
NEXT(v); return( arg - exp4(v));
} else return arg;
}
/* <EXP5> = <EXP6> | <EXP6> "*" <EXP5>
| <EXP6> "/" <EXP5>
| <EXP6> "%" <EXP5> */
int exp5(Token **v){ int arg = exp6(v), arg1;
if(*v && TYPE(v) == OP && eq(TOKEN(v), "*")){
NEXT(v); return( arg * exp5(v));
}else if(*v && TYPE(v) == OP && eq(TOKEN(v), "/")){
NEXT(v); if((arg1 = exp5(v)) == 0) ERR("Zero divide", arg);
return( arg / arg1);
}else if(*v && TYPE(v) == OP && eq(TOKEN(v), "%")){
NEXT(v); if((arg1 = exp5(v)) == 0) ERR("Zero module", arg);
return( arg % arg1);
} else return arg;
}
А. Богатырев, 1992-95 - 342 - Си в UNIX
/* <EXP6> = "!"<EXP6> | "~"<EXP6> | "-"<EXP6>
| "(" <EXPRESSION> ")"
| <ИМЯФУНКЦИИ> "(" [ <EXPRESSION> [ "," <EXPRESSION> ]... ] ")"
| <ЧИСЛО>
| <CH_ПЕРЕМЕННАЯ> */
int exp6(Token **v){ int arg;
if( !*v) ERR("Lost token", 0);
if(TYPE(v) == OP && eq(TOKEN(v), "!")){
NEXT(v); return !exp6(v);
}
if(TYPE(v) == OP && eq(TOKEN(v), "~")){
NEXT(v); return ~exp6(v);
}
if(TYPE(v) == OP && eq(TOKEN(v), "-")){
NEXT(v); return -exp6(v); /* унарный минус */
}
if(TYPE(v) == OPEN){
NEXT(v); arg = expression(v);
if( !*v || TYPE(v) != CLOSE) ERR("Lost ')'", arg);
NEXT(v); return arg;
}
if(TYPE(v) == NUM){ /* изображение числа */
arg = atoi(TOKEN(v)); NEXT(v); return arg;
}
if(TYPE(v) == ID){
char *name = (*v)->token; int args[20], nargs = 0;
NEXT(v);
if(! (*v && TYPE(v) == OPEN)){ /* Переменная */
return expvar(v, name);
}
/* Функция */
args[0] = 0;
do{ NEXT(v);
if( *v && TYPE(v) == CLOSE ) break; /* f() */
args[nargs++] = expression(v);
} while( *v && TYPE(v) == COMMA);
if(! (*v && TYPE(v) == CLOSE)) ERR("Error in '()'", args[0]);
NEXT(v);
return apply(name, args, nargs);
}
printlex(TOKEN(v), *v); ERR("Unknown token type", 0);
}
/* <CH_ПЕРЕМЕННАЯ> = <ПЕРЕМЕННАЯ> |
<ПЕРЕМЕННАЯ> "++" |
<ПЕРЕМЕННАЯ> "--"
Наши операции ++ и -- соответствуют ++x и --x из Си */
int expvar(Token **v, char *name){
int arg = getVar(name); Var *ptr = internVar(name);
if(*v && TYPE(v) == OP){
if(eq(TOKEN(v), "++")){ NEXT(v); setVar(ptr, ++arg); return arg; }
if(eq(TOKEN(v), "--")){ NEXT(v); setVar(ptr, --arg); return arg; }
}
return arg;
}
А. Богатырев, 1992-95 - 343 - Си в UNIX
/* Головная функция ------------------------------------------- */
char input[256];
Token *head, *tail;
void main(){
do{ printf(": "); fflush(stdout);
if( !gets(input)) break;
if(!*input){ printVars(); continue; }
if(eq(input, "!!")) ; /* ничего не делать, т.е. повторить */
else{ if(head) freelex(&head); lex(&head, &tail, input); }
printf("Result: %d\n", expr(head));
} while(1); putchar('\n');
}
7.69. Напишите программу, выделяющую n-ое поле из каждой строки файла. Поля разделя-
ются двоеточиями. Предусмотрите задание символа-разделителя из аргументов программы.
Используйте эту программу для выделения поля "домашний каталог" из файла /etc/passwd.
Для выделения очередного поля можно использовать следующую процедуру:
main(){
char c, *next, *strchr(); int nfield;
char *s = "11111:222222222:333333:444444";
for(nfield=0;;nfield++){
if(next = strchr(s, ':')){
c= *next; *next= '\0';
}
printf( "Поле #%d: '%s'\n", nfield, s);
/* можно сделать с полем s что-то еще */
if(next){ *next= c; s= next+1; continue; }
else { break; /* последнее поле */ }
}
}
7.70. Разработайте архитектуру и систему команд учебной машины и напишите интерпре-
татор учебного ассемблера, отрабатывающего по крайней мере такие команды:
mov пересылка (:=) add сложение
sub вычитание cmp сравнение и выработка признака
jmp переход jeq переход, если ==
jlt переход, если < jle переход, если <=
neg изменение знака not инвертирование признака
7.71. Напишите программу, преобразующую определения функций Си в "старом" стиле в
"новый" стиль стандарта ANSI ("прототипы" функций).
f(x, y, s, v)
int x;
char *s;
struct elem *v;
{ ... }
преобразуется в
int f(int x, int y, char *s, struct elem *v)
{ ... }
(обратите внимание, что переменная y и сама функция f описаны по умолчанию как int).
А. Богатырев, 1992-95 - 344 - Си в UNIX
Еще пример:
char *ff() { ... }
заменяется на
char *ff(void){ ... }
В данной задаче вам возможно придется использовать программу lex.
В списке аргументов прототипа должны быть явно указаны типы всех аргументов -
описатель int нельзя опускать. Так
q(x, s) char *s; { ... } // не прототип, допустимо.
// x - int по умолчанию.
q(x, char *s); // недопустимо.
q(int x, char *s); // верно.
Собственно под "прототипом" понимают предварительное описание функции в новом стиле -
где вместо тела {...} сразу после заголовка стоит точка с запятой.
long f(long x, long y); /* прототип */
...
long f(long x, long y){ return x+y; } /* реализация */
В прототипе имена аргументов можно опускать:
long f(long, long); /* прототип */
char *strchr(char *, char);
Это предварительное описание помещают где-нибудь в начале программы, до первого
вызова функции. В современном Си прототипы заменяют описания вида
extern long f();
о которых мы говорили раньше. Прототипы предоставляют программисту механизм для
автоматического контроля формата вызова функции. Так, если функция имеет прототип
double f( double );
и вызывается как
double x = f( 12 );
то компилятор автоматически превратит это в
double x = f( (double) 12 );
(поскольку существует приведение типа от int к double); если же написано
f( "привет" );
то компилятор сообщит об ошибке (так как нет преобразования типа (char *) в double).
Прототип принуждает компилятор проверять:
a) соответствие ТИПОВ фактических параметров (при вызове) типам формальных парамет-
ров (в прототипе);
b) соответствие КОЛИЧЕСТВА фактических и формальных параметров;
c) тип возвращаемого функцией значения.
Прототипы обычно помещают в include-файлы. Так в ANSI стандарте Си предусмотрен файл,
подключаемый
#include <stdlib.h>
А. Богатырев, 1992-95 - 345 - Си в UNIX
в котором определены прототипы функций из стандартной библиотеки языка Си. Черезвы-
чайно полезно писать эту директиву include, чтобы компилятор проверял, верно ли вы
вызываете стандартные функции.
Заметим, что если вы определили прототипы каких-то функций, но в своей программе
используете не все из этих функций, то функции, соответствующие "лишним" прототипам,
НЕ будут добавляться к вашей программе из библиотеки. Т.е. прототипы - это указание
компилятору; ни в какие машинные команды они не транслируются. То же самое касается
описаний внешних переменных и функций в виде
extern int x;
extern char *func();
Если вы не используете переменную или функцию с таким именем, то эти строки не имеют
никакого эффекта (как бы вообще отсутствуют).
7.72. Обратная задача: напишите преобразователь из нового стиля в старый.
int f( int x, char *y ){ ... }
переводить в
int f( x, y ) int x; char *y; { ... }
7.73. Довольно легко использовать прототипы таким образом, что они потеряют всякий
смысл. Для этого надо написать программу, состоящую из нескольких файлов, и в каждом
файле использовать свои прототипы для одной и той же функции. Так бывает, когда вы
поменяли функцию и прототип в одном файле, быть может во втором, но забыли сделать
это в остальных.
--------
файл a.c
--------
void g(void);
void h(void);
int x = 0, y = 13;
void f(int arg){
printf("f(%d)\n", arg);
x = arg;
x++;
}
int main(int ac, char *av[]){
h();
f(1);
g();
printf("x=%d y=%d\n", x, y);
return 0;
}
А. Богатырев, 1992-95 - 346 - Си в UNIX
--------
файл b.c
--------
extern int x, y;
int f(int);
void g(){
y = f(5);
}
--------
файл c.c
--------
void f();
void h(){
f();
}
Выдача программы:
abs@wizard$ cc a.c b.c c.c -o aaa
a.c:
b.c:
c.c:
abs@wizard$ aaa
f(-277792360)
f(1)
f(5)
x=6 y=5
abs@wizard$
Обратите внимание, что во всех трех файлах f() имеет разные прототипы! Поэтому прог-
рамма печатает нечто, что довольно-таки бессмысленно!
Решение таково: стараться вынести прототипы в include-файл, чтобы все файлы
программы включали одни и те же прототипы. Стараться, чтобы этот include-файл вклю-
чался также в файл с самим определением функции. В таком случае изменение только
заголовка функции или только прототипа вызовет ругань компилятора о несоответствии.
Вот как должен выглядеть наш проект:
-------------
файл header.h
-------------
extern int x, y;
void f(int arg);
int main(int ac, char *av[]);
void g(void);
void h(void);
А. Богатырев, 1992-95 - 347 - Си в UNIX
--------
файл a.c
--------
#include "header.h"
int x = 0, y = 13;
void f(int arg){
printf(