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

Таким образом, программа состоит из цикла, обрабатывающего на каждом своем шаге очередной встречаемый оператор или операнд:

while ( следующий элемент не конец-файла )

if ( число )

послать его в стек

else if ( оператор )

взять из стека операнды

выполнить операцию

результат послать в стек

else if ( новая-строка )

взять с вершины стека число и напечатать

else

ошибка

Операции "послать в стек" и "взять из стека" сами по себе тривиальны, однако по мере добавления к ним механизмов обнаружения и нейтрализации ошибок становятся достаточно длинными. Поэтому их лучше оформить в виде отдельных функций, чем повторять соответствующий код по всей программе. И конечно необходимо иметь отдельную функцию для получения очередного оператора или операнда.

Главный вопрос, который мы еще не рассмотрели, - это вопрос о том, где расположить стек и каким функциям разрешить к нему прямой доступ. Стек можно расположить в функции main и передавать сам стек и текущую позицию в нем в качестве аргументов функциям push ("послать в стек") и pop ("взять из стека"). Но функции main нет дела до переменных, относящихся к стеку, - ей нужны только операции по помещению чисел в стек и извлечению их оттуда. Поэтому мы решили стек и связанную с ним информацию хранить во внешних переменных, доступных для функций push и pop , но не доступных для main .

Переход от эскиза к программе достаточно легок. Если теперь программу представить как текст, расположенный в одном исходном файле, она будет иметь следующий вид:

#include /* могут быть в любом количестве */

#define /* могут быть в любом количестве */

объявления функций для main

main() {…}

внешние переменные для push и pop

void push (double f) {…}

double pop (void) {…}

int getop(char s[]) {…}

подпрограммы, вызываемые функцией getop

Позже мы обсудим, как текст этой программы можно разбить на два или большее число файлов.

Функция main - это цикл, содержащий большой переключатель switch , передающий управление на ту или иную ветвь в зависимости от типа оператора или операнда. Здесь представлен более типичный случай применения переключателя switch по сравнению с рассмотренным в параграфе 3.4.

#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 , если буфер пустой. Следует предусмотреть индекс, указывающий на положение текущего символа в буфере.