*
* 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
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. Составьте программу преобразования прописных букв из файла ввода в строчные,
используя при этом функцию, в которой необходимо организовать анализ символа (дейст-
вительно ли это буква). Строчные буквы выдавать без изменения. Указание: используйте
макросы из .
Ответ:
#include
#include
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 должны пониматься только буквы (увы, не во
