Богатырев Андрей. Хрестоматия по программированию на Си в Unix

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 }