Брайан Керниган - Язык программирования Си. Издание 3-е, исправленное

#include ‹stdio.h›

#include ‹stdlib.h› /* для atof() */

#define MAXOP 100 /* макс. размер операнда или оператора */

#define NUMBER '0' /* признак числа */

int getop (char []);

void push (double);

double pop (void);

/* калькулятор с обратной польской записью */

main()

{

int type;

double op2;

char s[MAXOP];

while ((type = getop (s)) != EOF) {

switch (type) {

case NUMBER:

push (atof(s));

break;

case '+':

push(pop() + pop());

break;

case '*':

push(pop() * pop());

break;

case '-':

op2 = pop();

push(pop() - op2);

break;

case '/':

pop2 = pop();

if (op2 != 0.0)

push(pop() / op2);

else

printf("ошибка: деление на нуль\n");

break;

case '\n':

printf("\t%.8g\n", pop());

break;

default:

printf("ошибка: неизвестная операция %s\n", s);

break;

}

}

return 0;

}

Так как операторы + и * коммутативны, порядок, в котором операнды берутся из стека, не важен, однако в случае операторов - и /, левый и правый операнды должны различаться. Так, в

push(pop() - pop()); /* НЕПРАВИЛЬНО */

очередность обращения к pop не определена. Чтобы гарантировать правильную очередность, необходимо первое значение из стека присвоить временной переменной, как это и сделано в main.

#define MAXVAL 100 /* максимальная глубина стека */

int sp = 0; /* следующая свободная позиция в стеке */

double val[MAXVAL]; /* стек */

/* push: положить значение f в стек */

void push(double f)

{

if (sp ‹ MAXVAL)

val[sp++] = f;

else

printf("ошибка: стек полон, %g не помещается\n", f);

}

/* pop: взять с вершины стека и выдать в качестве результата */

double pop(void)

{

if (sp › 0)

return val[--sp];

else {

printf ("ошибка: стек пуст\n");

return 0.0;

}

}

Переменная считается внешней, если она определена вне функции. Таким образом, стек и индекс стека, которые должны быть доступны и для push , и для pop , определяются вне этих функций. Но main не использует ни стек, ни позицию в стеке, и поэтому их представление может быть скрыто от main .

Займемся реализацией getop - функции, получающей следующий оператор или операнд. Нам предстоит решить довольно простую задачу. Более точно: требуется пропустить пробелы и табуляции; если следующий символ - не цифра и не десятичная точка, то нужно выдать его; в противном случае надо накопить строку цифр с десятичной точкой, если она есть, и выдать число NUMBER в качестве результата.

#include ‹ctype.h›

int getch(void);

void ungetch(int);

/* getop: получает следующий оператор или операнд */

int getop(char s[])

{

int i, с;

while ((s[0] = с = getch()) == ' ' || с == '\t')

;

s[1] = '\0;

if (!isdigit(c) && с!= '.')

return c; /* не число */

i = 0;

if (isdigit(c)) /* накапливаем целую часть */

while (isdigit(s[++i] - с = getch()))

;

if (с == '.') /* накапливаем дробную часть */

while (isdigit(s[++i] = с = getch()))

;

s[i] = '\0';

if (c != EOF)

ungetch(c);

return NUMBER;

}

Как работают функции getch и ungetch ? Во многих случаях программа не может "сообразить", прочла ли она все, что требуется, пока не прочтет лишнего. Так, накопление числа производится до тех пор, пока не встретится символ, отличный от цифры. Но это означает, что программа прочла на один символ больше, чем нужно, и последний символ нельзя включать в число.

Эту проблему можно было бы решить при наличии обратной чтению операции "положить-назад", с помощью которой можно было бы вернуть ненужный символ. Тогда каждый раз, когда программа считает на один символ больше, чем требуется, эта операция возвращала бы его вводу, и остальная часть программы могла бы вести себя так, будто этот символ вовсе и не читался. К счастью, описанный механизм обратной посылки символа легко моделируется с помощью пары согласованных друг с другом функций, из которых getch поставляет очередной символ из ввода, a ungetch отправляет символ назад во входной поток, так что при следующем обращении к getch мы вновь его получим.

Нетрудно догадаться, как они работают вместе. Функция ungetch запоминает посылаемый назад символ в некотором буфере, представляющем собой массив символов, доступный для обеих этих функций; getch читает из буфера, если там что-то есть, или обращается к getchar , если буфер пустой. Следует предусмотреть индекс, указывающий на положение текущего символа в буфере.