7. Текстовая обработка.
Под "текстовой обработкой" (в противовес "вычислительным задачам") здесь понима-
ется огромный класс задач обработки информации нечислового характера, например редак-
тирование текста, форматирование документов, поиск и сортировка, базы данных, лекси-
ческий и синтаксический анализ, печать на принтере, преобразование формата таблиц,
и.т.п.
7.1. Напишите программу, "угадывающую" слово из заранее заданного списка по первым
нескольким буквам. Выдайте сообщение "неоднозначно", если есть несколько похожих
слов. Усложните программу так, чтобы список слов считывался в программу при ее
запуске из файла list.txt
7.2. Напишите программу, которая удваивает пробелы в тексте с одиночными пробелами.
7.3. Напишите программу, которая копирует ввод на вывод, заменяя каждую последова-
тельность из идущих подряд нескольких пробелов и/или табуляций на один пробел. Схема
ее решения сходна с решением следующей задачи.
7.4. Напишите программу подсчета слов в файле. Слово определите как последователь-
ность символов, не включающую символы пробела, табуляции или новой строки. "Канони-
ческий" вариант решения, приведенный у Кернигана и Ритчи, таков:
#include <ctype.h>
#include <stdio.h>
const int YES=1, NO=0;
main(){
register int inWord = NO; /* состояние */
int words = 0, c;
while((c = getchar()) != EOF)
if(isspace(c) || c == '\n') inWord = NO;
else if(inWord == NO){
inWord = YES; ++words;
}
printf("%d слов\n", words);
}
Обратите внимание на конструкцию const. Это объявление имен как констант. Эта конст-
рукция близка к
#define YES 1
но позволяет компилятору
- более строго проверять тип, т.к. это типизированная константа;
- создавать более экономный код;
- запрещает изменять это значение.
Рассмотрим пример
main(){ /* cc 00.c -o 00 -lm */
double sqrt(double);
const double sq12 = sqrt(12.0);
#define SQRT2 sqrt(2.0)
double x;
x = sq12 * sq12 * SQRT2 * SQRT2; /* @1 */
sq12 = 3.4641; /* @2 */
printf("%g %g\n", sq12, x);
}
Использование #define превратит строку @1 в
x = sq12 * sq12 * sqrt(2.0) * sqrt(2.0);
то есть создаст код с двумя вызовами функции sqrt. Конструкция же const заносит
вычисленное выражение в ячейку памяти и далее просто использует ее значение. При этом
А. Богатырев, 1992-95 - 284 - Си в UNIX
компилятор не позволяет впоследствии изменять это значение, поэтому строка @2 оши-
бочна.
Теперь предложим еще одну программу подсчета слов, где слово определяется макро-
сом isWord, перечисляющим буквы допустимые в слове. Программа основана на переключа-
тельной таблице функций (этот подход применим во многих случаях):
#include <ctype.h>
#include <stdio.h>
int wordLength, inWord, words; /* = 0 */
char aWord[128], *wrd;
void space (c){}
void letter (c){ wordLength++; *wrd++ = c; }
void begWord(c){ wordLength=0; inWord=1;
wrd=aWord; words++; letter(c); }
void endWord(c){ inWord=0; *wrd = '\0';
printf("Слово '%s' длины %d\n",
aWord, wordLength); }
void (*sw[2][2])() = {
/* !isWord */ { space, endWord },
/* isWord */ { begWord, letter }
/* !inWord inWord */
};
#define isWord(c) (isalnum(c) || c=='-' || c=='_')
main(){ register c;
while((c = getchar()) != EOF)
(*sw[isWord(c)][inWord])(c);
printf("%d слов\n", words);
}
7.5. Напишите программу, выдающую гистограмму длин строк файла (т.е. таблицу: строк
длины 0 столько-то, длины 1 - столько-то, и.т.п., причем таблицу можно изобразить
графически).
7.6. Напишите программу, которая считывает слово из файла in и записывает это слово
в конец файла out.
7.7. Напишите программу, которая будет печатать слова из файла ввода, причем по
одному на строку.
7.8. Напишите программу, печатающую гистограмму длин слов из файла ввода.
7.9. Напишите программу, читающую слова из файла и размещающую их в виде двунаправ-
ленного списка слов, отсортированного по алфавиту. Указания: используйте динамическую
память (malloc) и указатели; напишите функцию включения нового слова в список на нуж-
ное место.
В конце работы распечатайте список дважды: в прямом и в обратном порядке.
Усложнение: не хранить в списке дубликаты; вместо этого вместе со словом хранить
счетчик количества его вхождений в текст.
7.10. Напишите программу, которая печатает слова из своего файла ввода, расположен-
ные в порядке убывания частоты их появления. Перед каждым словом напечатайте число
частоты его появления.
7.11. Напишите программу, читающую файл построчно и печатающую слова в каждой строке
в обратном порядке.
А. Богатырев, 1992-95 - 285 - Си в UNIX
7.12. Напишите программу копирования ввода на вывод таким образом, чтобы из каждой
группы последовательно одинаковых строк выводилась только одна строка. Это аналог
программы uniq в системе UNIX. Ответ:
#include <stdio.h> /* char *gets(); */
char buf1[4096], buf2[4096];
char *this = buf1, *prev = buf2;
main(){
long nline =0L; char *tmp;
while( gets(this)){
if(nline){ /* сравнить новую и предыдущую строки */
if( strcmp(this, prev)) /* различны ? */
puts(prev);
}
/* обмен буферов: */ tmp=prev; prev=this; this=tmp;
nline++; /* номер строки */
}/* endwhile */
if( nline ) puts(prev);
/* последняя строка всегда выдается */
}
7.13. Составьте программу, которая будет удалять в конце (и в начале) каждой строки
файла пробелы и табуляции, а также удалять строки, целиком состоящие из пробелов и
табуляций.
7.14. Для экономии места в файле, редакторы текстов при записи отредактированного
файла сжимают подряд идущие пробелы в табуляцию. Часто это неудобно для программ
обработки текстов (поскольку требует особой обработки табуляций - это ОДИН символ,
который на экране и в тексте занимает НЕСКОЛЬКО позиций!), поэтому при чтении файла
мы должны расширять табуляции в нужное количество пробелов, например так:
/* заменять табуляции на пробелы */
void untab(s) register char *s;
{
char newstr[256]; /* новая строка */
char *src = s;
int n; /* счетчик */
register dstx; /* координата x в новой строке */
for(dstx = 0; *s != '\0'; s++)
if( *s == '\t'){
for(n = 8 - dstx % 8 ; n > 0 ; n--)
newstr[dstx++] = ' ';
}else newstr[dstx++] = *s;
newstr[dstx] = '\0';
strcpy(src, newstr); /* строку на старое место */
}
7.15. Напишите обратную функцию, сжимающую подряд идущие пробелы в табуляции.
А. Богатырев, 1992-95 - 286 - Си в UNIX
void tabify(){
int chr;
int icol, ocol; /* input/output columns */
for(icol = ocol = 0; ; ){
if((chr = getchar()) == EOF)
break;
switch(chr){
case ' ':
icol++;
break;
case '\n':
case '\r':
ocol = icol = 0;
putchar(chr);
break;
case '\t':
icol += 8;
icol &= ~07; /* icol -= icol % 8; */
break;
default:
while(((ocol + 8) & ~07) <= icol){
#ifdef NOTDEF
if(ocol + 1 == icol)
break;
/* взять ' ' вместо '\t' */
#endif
putchar('\t');
ocol += 8;
ocol &= ~07;
}
while(ocol < icol){
putchar(' ');
ocol++;
}
putchar(chr);
icol++;
ocol++;
break;
}
}
}
7.16. Составьте программу, укорачивающую строки исходного файла до заданной величины
и помещающую результат в указанный файл. Учтите, что табуляция разворачивается в нес-
колько пробелов!
7.17. Разработайте программу, укорачивающую строки входного файла до 60 символов.
Однако теперь запрещается обрубать слова.
А. Богатырев, 1992-95 - 287 - Си в UNIX
7.18. Разработайте программу, заполняющую промежутки между словами строки дополни-
тельными пробелами таким образом, чтобы длина строки была равна 60 символам.
7.19. Напишите программу, переносящую слишком длинные строки. Слова разбивать
нельзя (неумешающееся слово следует перенести целиком). Ширину строки считать равной
60.
7.20. Составьте программу, центрирующую строки файла относительно середины экрана,
т.е. добавляющую в начало строки такое количество пробелов, чтобы середина строки
печаталась в 40-ой позиции (считаем, что обычный экран имеет ширину 80 символов).
7.21. Напишите программу, отсекающую n пробелов в начале каждой строки (или n первых
любых символов). Учтите, что в файле могут быть строки короче n (например пустые
строки).
#include <stdio.h>
/* ... текст функции untab(); ... */
void process(char name[], int n, int spacesOnly){
char line[256]; int length, shift, nline = 0;
char newname[128]; FILE *fpin, *fpout;
if((fpin = fopen(name, "r")) == NULL){
fprintf(stderr, "Не могу читать %s\n", name);
return;
}
sprintf(newname, "_%s", name); /* например */
if((fpout = fopen(newname, "w")) == NULL){
fprintf(stderr, "Не могу создать %s\n",
newname); fclose(fpin); return;
}
while(fgets(line, sizeof line, fpin)){ ++nline;
if((length = strlen(line)) &&
line[length-1] == '\n')
line[--length] = '\0'; /* обрубить '\n' */
untab(line); /* развернуть табуляции */
for(shift=0; line[shift] != '\0' && shift < n ;
++shift)
if(spacesOnly && line[shift] != ' ') break;
if(*line && shift != n ) /* Предупреждение */
fprintf(stderr,
"Начало строки #%d слишком коротко\n", nline);
fprintf(fpout, "%s\n", line+shift);
/* нельзя было fputs(line+n, fpout);
* т.к. эта позиция может быть ЗА концом строки
*/
}
fclose(fpin); fclose(fpout);
}
void main(int argc, char **argv){
if( argc != 3 ) exit(1);
process(argv[2], atoi(argv[1]) /* 8 */, 1);
exit(0);
}
7.22. Напишите программу, разбивающую файл на два по вертикали: в первый файл попа-
дает левая половина исходного файла, во второй - правая. Ширину колонки задавайте из
аргументов main(). Если же аргумент не указан - 40 позиций.
7.23. Напишите программу сортировки строк в алфавитном порядке. Учтите, что функция
strcmp() сравнивает строки в порядке кодировки, принятой на данной конкретной машине.
Русские буквы, как правило, идут не в алфавитном порядке! Следует написать функцию
А. Богатырев, 1992-95 - 288 - Си в UNIX
для алфавитного сравнения отдельных символов и, пользуясь ею, переписать функцию
strcmp().
7.24. Отсортируйте массив строк по лексикографическому убыванию, игнорируя различия
между строчными и прописными буквами.
7.25. Составьте программу дихотомического поиска в отсортированном массиве строк
(методом деления пополам).
/* Поиск в таблице методом половинного деления: dihotomia */
#include <stdio.h>
struct elem {
char *name; /* ключ поиска */
int value;
} table[] = {
/* имена строго по алфавиту */
{ "andrew", 17 },
{ "bill", 23 },
{ "george", 55 },
{ "jack", 54 },
{ "jaw", 43 },
{ "john", 33 },
{ "mike", 99 },
{ "paul", 21 },
{ "sue", 66 }, /* SIZE - 2 */
{ NULL, -1 }, /* SIZE - 1 */
/* NULL введен только для распечатки таблицы */
};
#define SIZE (sizeof(table) / sizeof(struct elem))
/* Дихотомический поиск по таблице */
struct elem *find(s, table, size)
char *s; /* что найти ? */
struct elem table[]; /* в чем ? */
int size; /* среди первых size элементов */
{
register top, bottom, middle;
register code;
top = 0; /* начало */
bottom = size - 1; /* конец: индекс строки "sue" */
while( top <= bottom ){
middle = (top + bottom) / 2; /* середина */
/* сравнить строки */
code = strcmp( s, table[middle].name ) ;
if( code > 0 ){
top = middle + 1;
}else if( code < 0 ){
bottom = middle - 1;
}else return &table[ middle ];
}
return (struct elem *) NULL; /* не нашел */
}
А. Богатырев, 1992-95 - 289 - Си в UNIX
/* распечатка таблицы */
void printtable(tbl) register struct elem *tbl; {
for( ; tbl->name != NULL ; tbl++ ){
printf( "%-15s %d\n", tbl->name, tbl->value );
}
}
int main(){
char buf[80];
struct elem *ptr;
printtable(table);
for(;;){
printf( "-> " );
if( gets( buf ) == NULL) break; /* EOF */
if( ! strcmp( buf, "q" ))
exit(0); /* quit: выход */
ptr = find( buf, table, SIZE-1 );
if( ptr )
printf( "%d\n", ptr->value );
else {
printf( "--- Не найдено ---\n" );
printtable(table);
}
}
return 0;
}
7.26. Напишем функцию, которая преобразует строку так, что при ее печати буквы в ней
будут подчеркнуты, а цифры - выделены жирно. Формат текста с выделениями, который
создается этим примером, является общепринятым в UNIX и распознается некоторыми прог-
раммами: например, программа просмотра файлов less (more) выделяет такие буквы на
экране специальными шрифтами или инверсией фона.
#define LEN 9 /* потом напишите 256 */
char input[] = "(xxx+yyy)/123.75=?";
char output[LEN];
void main( void ){
int len=LEN, i; void bi_conv(); char c;
bi_conv(input, output, &len);
if(len > LEN){
printf("Увеличь LEN до %d\n", len);
len = LEN; /* доступный максимум */
}
for(i=0; i < len && (c = output[i]); ++i)
putchar(c);
putchar('\n');
}
/* Заметьте, что include-файлы не обязательно
* должны включаться в самом начале программы! */
#include <stdio.h>
#include <ctype.h>
#define PUT(c) { count++; \
if(put < *len){ *p++ = (c); ++put;}}
#define GET() (*s ? *s++ : EOF)
void bi_conv(
А. Богатырев, 1992-95 - 290 - Си в UNIX
/*IN*/ char *s,
/*OUT*/ char *p,
/*INOUT*/ int *len ){
int count, put, c;
for(count=put=0; (c=GET()) != EOF; ){
/* жирный: C\bC */
/* подчеркнутый: _\bC */
if(isalpha(c)){ PUT('_'); PUT('\b'); }
else if(isdigit(c)){ PUT( c ); PUT('\b'); }
PUT(c);
}
PUT('\0'); /* закрыть строку */
*len = count;
#undef PUT
#undef GET
}
Напишите программу для подобной обработки файла. Заметим, что для этого не нужны
промежуточные строки input и output и построчное чтение файла; все, что надо сделать,
это определить
#define PUT(c) if(c)putchar(c)
#define GET() getchar()
Напишите подобную функцию, удваивающую буквы в ссттррооккее.
7.27. Напишите программу, удаляющую из файла выделения. Для этого надо просто уда-
лять последовательности вида C\b
#include <stdio.h>
#define NOPUT (-1) /* не символ ASCII */
/* Названия шрифтов - в перечислимом типе */
typedef enum { NORMAL=1, ITALICS, BOLD, RED=BOLD } font;
int ontty; font textfont; /* текущее выделение */
#define setfont(f) textfont=(f)
#define getfont() (textfont)
#define SetTtyFont(f) if(ontty) tfont(f)
/* Установить выделение на экране терминала */
void tfont(font f){ /* только для ANSI терминала */
static font ttyfont = NORMAL;
if(ttyfont == f) return;
printf("\033[0m"); /* set NORMAL font */
switch(ttyfont = f){
case NORMAL: /* уже сделано выше */ break;
case BOLD: printf("\033[1m"); break;
case ITALICS: /* use reverse video */
printf("\033[7m"); break;
}
}
void put(int c){ /* Вывод символа текущим цветом */
if(c == NOPUT) return; /* '\b' */
SetTtyFont(getfont()); putchar(c);
setfont(NORMAL); /* Ожидать новой C\b посл-ти */
}
void
main(){ register int c, cprev = NOPUT;
/* Стандартный вывод - это терминал ? */
ontty = isatty(fileno(stdout));
setfont(NORMAL);
while((c = getchar()) != EOF){
А. Богатырев, 1992-95 - 291 - Си в UNIX
if(c == '\b'){ /* выделение */
if((c = getchar()) == EOF) break;
if(c == cprev) setfont(BOLD);
else if(cprev == '_') setfont(ITALICS);
else /* наложение A\bB */ setfont(RED);
} else put(cprev);
}
put(cprev); /* последняя буква файла */
SetTtyFont(NORMAL);
}
7.28. Напишите программу печати на принтере листинга Си-программ. Ключевые слова
языка выделяйте двойной надпечаткой. Для выдачи на терминал напишите программу, под-
черкивающую ключевые слова (подчеркивание - в следующей строке). Упрощение: выде-
ляйте не ключевые слова, а большие буквы. Указание: для двойной печати используйте
управляющий символ '\r' - возврат к началу той же строки; затем строка печатается
повторно, при этом символы, которые не должны печататься жирно, следует заменить на
пробелы (или на табуляцию, если этот символ сам есть '\t').
7.29. Напишите программу, печатающую тексты Си-программ на принтере. Выделяйте клю-
чевые слова языка жирным шрифтом, строки "строка", символы 'c' и комментарии - курси-
вом. Шрифты для EPSON-FX совместимых принтеров (например EP-2424) переключаются
такими управляющими последовательностями (ESC означает символ '\033'):
ВКЛЮЧЕНИЕ ВЫКЛЮЧЕНИЕ
жирный шрифт (bold) ESC G ESC H
утолщенный шрифт (emphasized) ESC E ESC F
курсив (italics) ESC 4 ESC 5
подчеркивание (underline) ESC - 1 ESC - 0
повышенное качество печати ESC x 1 ESC x 0
(near letter quality) nlq draft
верхние индексы (superscript) ESC S 0 ESC T
нижние индексы (subscript) ESC S 1 ESC T
сжатый шрифт (17 букв/дюйм) '\017' '\022'
(condensed)
двойная ширина букв ESC W 1 ESC W 0
(expanded)
пропорциональная печать ESC p 1 ESC p 0
(proportional spacing)
Можно включить одновременно несколько из перечисленных выше режимов. В каждой из
следующих двух групп надо выбрать одно из трех:
pitch (плотность печати)
pica (10 букв/дюйм) ESC P
elite (12 букв/дюйм) ESC M
micron (15 букв/дюйм) ESC g
font (шрифт)
черновик (draft (Roman)) ESC k '\0'
текст (text (Sans Serif)) ESC k '\1'
курьер (courier) ESC k '\2'
Всюду выше 0 означает либо '0' либо '\0'; 1 означает либо '1' либо '\1'. Пример:
printf( "This is \033Gboldface\033H word\n");
А. Богатырев, 1992-95 - 292 - Си в UNIX
7.30. Составьте программу вывода набора файлов на печать, начинающую каждый очеред-
ной файл с новой страницы и печатающую перед каждым файлом заголовок и номер текущей
страницы. Используйте символ '\f' (form feed) для перевода листа принтера.
7.31. Напишите программу печати текста в две колонки. Используйте буфер для форми-
рования листа: файл читается построчно (слишком длинные строки обрубать), сначала
заполняется левая половина листа (буфера), затем правая. Когда лист полностью запол-
нен или файл кончился - выдать лист построчно, расписать буфер пробелами (очистить
лист) и повторить заполнение очередного листа. Указание: размеры листа должны переда-
ваться как аргументы main(), для буфера используйте двумерный массив букв, память для
него заказывайте динамически. Усложнение: не обрубайте, а переносите слишком длинные
строки (строка может потребовать даже переноса с листа на лист).
/* ПРОГРАММА ПЕЧАТИ В ДВЕ ПОЛОСЫ: pr.c */
#include <stdio.h>
#include <string.h>
#define YES 1
#define NO 0
#define FORMFEED '\f'
#define LINEFEED '\n'
extern char *malloc(unsigned);
extern char *strchr(char *, char);
void untab(register char *s);
void resetsheet( void );
void addsheet( char *s, FILE *fpout );
void flushsheet( FILE *fpout );
void printline( int y, char *s, char *attr,
FILE *fpout );
void doattr( register char *abuf,
register char *vbuf );
void printcopy( FILE *fpin, FILE *fpout );
void main(void);
char *strdup (const char *s){
char *p = malloc(strlen(s)+1); strcpy(p,s); return p;
/* return strcpy((char *) malloc(strlen(s)+1), s); */
}
/* ... текст функции untab() ... */
int Sline; /* строка на листе */
int Shalf; /* половина листа */
int npage; /* номер страницы */
int startpage = 1;
/* печать начиная с 1ой страницы */
int fline; /* номер строки файла */
int topline = 0; /* смещение до начала листа */
int halfwidth; /* ширина полулиста */
int twocolumns = YES; /* в две колонки ? */
int lshift, rshift = 1; /* поля слева и справа */
typedef unsigned short ushort;
int COLS = 128; /* ширина листа (букв) */
int LINES = 66; /* длина листа (строк) */
ushort *mem; /* буфер листа */
#define AT(x,y) mem[ (x) + (y) * COLS ]
/* Выделить буфер под лист и зачистить его */
void resetsheet ( void ){
register x;
if( mem == NULL ){ /* выделить память */
А. Богатырев, 1992-95 - 293 - Си в UNIX
if ((mem = (ushort *)
malloc (COLS * LINES * sizeof(ushort)))
== NULL ){
fprintf(stderr, "Out of memory.\n"); exit(1);
}
}
/* очистить */
for( x= COLS * LINES - 1 ; x >= 0 ; x-- )
mem[x] = ' ' & 0xFF;
halfwidth = (twocolumns ? COLS/2 : COLS )
- (lshift + rshift );
Sline = topline; Shalf = 0;
}
#define NEXT_HALF \
if( twocolumns == YES && Shalf == 0 ){ \
/* закрыть данную половину листа */ \
Shalf = 1; /* перейти к новой половине */ \
Sline = topline; \
} else \
flushsheet(fpout) /* напечатать лист */
/* Записать строку в лист */
void addsheet ( char *s, FILE *fpout )
{
register x, y;
register i;
char *rest = NULL;
int wrap = NO;
/* YES когда идет перенос слишком длинной строки */
/* в какое место поместить строку? */
x = (Shalf == 0 ? 0 : COLS/2) + lshift;
y = Sline;
i = 0; /* позиция в строке s */
while (*s) {
if( *s == '\f' ){
/* вынужденный form feed */
rest = strdup( s+1 ); /* остаток строки */
NEXT_HALF;
if( *rest ) addsheet(rest, fpout);
free( rest );
return;
}
if( i >= halfwidth ){
/* перенести длинную строку */
wrap = YES;
rest = strdup(s);
break;
}
/* Обработка выделений текста */
if( s[1] == '\b' ){
while( s[1] == '\b' ){
AT(x, y) = (s[0] << 8) | (s[2] & 0xFF);
/* overstrike */
s += 2;
}
s++; x++; i++;
} else {
AT (x, y) = *s++ & 0xFF;
А. Богатырев, 1992-95 - 294 - Си в UNIX
x++; i++;
}
}
/* Увеличить строку/половину_листа */
Sline++;
if (Sline == LINES) { /* полулист заполнен */
NEXT_HALF; }
if( wrap && rest ) { /* дописать остаток строки */
addsheet(rest, fpout); free(rest);
}
}
int again; /* нужна ли повторная надпечатка? */
/* Напечатать заполненный лист */
void flushsheet ( FILE *fpout ){
register x, y, xlast;
char *s, *p;
static char outbuf[BUFSIZ], attr[BUFSIZ];
/* attr - буфер под атрибуты выделений */
ushort c;
if( npage >= startpage )
for (y = 0; y < LINES; y++) {
/* обрезать концевые пробелы */
for (xlast = (-1), x = COLS - 1; x >= 0; x--)
if (AT (x, y) != ' ') { xlast = x; break; }
again = NO; s = outbuf; p = attr;
for (x = 0; x <= xlast; x++){
c = AT(x, y);
*s++ = c & 0xFF;
/* имеет атрибуты ? */
c >>= 8; c &= 0xFF;
*p++ = c ? c : ' ';
if( c ) again = YES;
}
*s = '\0'; *p = '\0';
printline(y, outbuf, attr, fpout);
}
npage++; /* next page */
resetsheet(); /* зачистить новый лист */
}
/* Напечатать одну строку листа */
void printline ( int y, char *s, char *attr,
FILE *fpout ){
register x;
if( again ){
doattr(attr, s); fprintf(fpout, "%s\r", attr );
}
fprintf(fpout, "%s", s);
/* перевод листа или строки */
fputc( y == LINES-1 ? FORMFEED : LINEFEED, fpout );
}
/* Проверить - нет ли атрибутов выделений */
void doattr ( register char *abuf,
register char *vbuf ){
for(; *abuf; abuf++, vbuf++ )
if( !strchr(" _-!|\177", *abuf))
*abuf = *vbuf;
}
А. Богатырев, 1992-95 - 295 - Си в UNIX
/* Копирование файла на принтер */
void printcopy ( FILE *fpin, FILE *fpout )
{
char inbuf[BUFSIZ];
npage = 1; /* первая страница имеет номер 1 */
fline = 0; /* текущая строка файла - 0 */
resetsheet(); /* зачистить буфер листа */
while( fgets(inbuf, sizeof inbuf - 1, fpin )
!= NULL ){
register l = strlen( inbuf );
if( l && inbuf[l-1] == '\n' )
inbuf[--l] = '\0' ;
fline++;
untab ( inbuf );
addsheet( inbuf, fpout );
}
if( !(Sline == topline && Shalf == 0))
/* если страница не была только что зачищена ... */
flushsheet(fpout);
fprintf(stderr, "%d строк, %d листов.\n",
fline, npage-1);
}
/* Вызов: pr < файл > /dev/lp */
void main (){ printcopy(stdin, stdout); }
Файл-принтер имеет в UNIX имя /dev/lp или подобное ему, а в MS DOS - имя prn.
7.32. Напишите программу, которая построчно считывает небольшой файл в память и
печатает строки в обратном порядке. Указание: используйте динамическую память -
функции malloc() и strcpy().
Объясним, почему желательно пользоваться динамической памятью. Пусть мы знаем,
что строки имеют максимальную длину 80 символов и максимальное количество строк равно
50. Мы могли бы хранить текст в двумерном массиве:
char text[50][80];
занимающем 50*80 = 4000 байт памяти. Пусть теперь оказалось, что строки файла в
действительности имеют длину по 10 букв. Мы
используем 50 * (10 + 1) = 550 байт
не используем 4000 - 50 * (10 + 1) = 3450 байт
(+1 нужен для символа '\0' на конце строки).
Пусть мы теперь пишем
char *text[50]; int i=0;
и при чтении очередной строки сохраняем ее так:
char buffer[81], *malloc(), *gets();
while( gets(buffer) != NULL ){
text[i] = (char *) malloc(strlen(buffer)+1);
/* +1 для хранения \0, который не учтен strlen-ом */
strcpy(text[i++], buffer);
}
то есть заказываем ровно столько памяти, сколько надо для хранения строки и ни байтом
больше. Здесь мы (если sizeof(char *)==4) используем
А. Богатырев, 1992-95 - 296 - Си в UNIX
50 * 4 + 50 * (10 + 1 + 4) = 950 байт
массив указателей + заказанная malloc память
(+4 - служебная информация malloc), но зато у нас не остается неиспользуемой памяти.
Преимуществом выделения памяти в виде массива является то, что эта память выделится
ГАРАНТИРОВАННО, тогда как malloc()-у может не хватить памяти (если мы ее прежде очень
много захватывали и не освобождали free()). Если malloc не может выделить участок
памяти требуемого размера, он возвращает значение NULL:
if((text[i] = malloc(....)) == NULL)
{ fprintf(stderr, "Мало памяти\n"); break; }
Распечатка строк:
for(--i; i >= 0; i-- ){
printf("%s\n", text[i]);
free( text[i] );
}
Функция free(ptr) "освобождает"[*] отведенную ранее malloc()ом или calloc()ом область
памяти по адресу ptr так, что при новых вызовах malloc() эта область может быть пере-
использована. Данные в освобожденной памяти ПОРТЯТСЯ после free(). Ошибочно (и
опасно) освобождать память, которая НЕ БЫЛА отведена malloc()-ом!
Организация текста в виде массива ссылок на строки или списка ссылок на строки,
а не в виде двумерного текстового поля, выгодна еще тем, что такие строки проще
переставлять, сортировать, вставлять строку в текст, удалять строку из текста. При
этом переставляются лишь указатели в линейном массиве, а сами строки никуда не копи-
руются. В двумерном же байтовом массиве нам пришлось бы для тех же перестановок
копировать целые массивы байт - строки этой текстовой матрицы.
7.33. Напишите программу, печатающую строки файла в обратном порядке. Не считывать
файл целиком в память! Следует использовать метод "обратного чтения" либо метод
"быстрого доступа" к строкам файла, описанный в главе "Работа с файлами".
____________________
[*] На самом деле все освобожденные куски включаются в список свободной памяти, и
склеиваются вместе, если два освобожденных куска оказались рядом. При новых вызовах
malloc сначала просматривается список свободной памяти - нет ли там области достаточ-
ного размера? Этот алгоритм описан у Кернигана и Ритчи.
А. Богатырев, 1992-95 - 297 - Си в UNIX
/* Инвертирование порядка строк в файле.
* Используется та идея, что файл-результат имеет тот же
* размер, что и исходный
*/
#include <sys/types.h>
#include <sys/stat.h>
#include <stdio.h>
#define BUFS 4096 /* максимальная длина строки */
void main(int argc, char **argv )
{
FILE *fp;
struct stat st;
long len;
char buffer[ BUFS+1 ];
FILE *fpnew; /* инверсный файл */
int lgt;
if( argc != 2 ){
printf("Error: must be filename\n");
exit(1);
}
if( (fp= fopen( argv[1], "r" )) == NULL ){
printf( "Can not open %s\n", argv[1] );
exit(2);
}
stat( argv[1], &st ); /* fstat(fileno(fp), &st); */
len = st.st_size; /* длина файла в байтах */
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("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;
}
--------
файл b.c
--------
#include "header.h"
void g(){
y = f(5);
}
--------
файл c.c
--------
#include "header.h"
void h(){
f();
}
Попытка компиляции:
abs@wizard$ cc a.c b.c c.c -o aaa
a.c:
b.c:
"b.c", line 4: operand cannot have void type: op "="
"b.c", line 4: assignment type mismatch:
int "=" void
cc: acomp failed for b.c
c.c:
"c.c", line 4: prototype mismatch: 0 args passed, 1 expected
cc: acomp failed for c.c