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

Ритчи Деннис М.

в польской записи представляется как

1 2 - 4 5 + *

Скобки не нужны, неоднозначности в вычислениях не бывает, поскольку известно, сколько операндов требуется для каждого оператора.

Реализовать нашу программу весьма просто. Каждый операнд посылается в стек; если встречается оператор, то из стека берется соответствующее число операндов (в случае бинарных операторов два) и выполняется операция, после чего результат посылается в стек. В нашем примере числа 1 и 2 посылаются в стек, затем замещаются на их разность -1. Далее в стек посылаются числа 4 и 5, которые затем заменяются их суммой (9). Числа -1 и 9 заменяются

в стеке их произведением (т. е.
– 9). Встретив символ новой строки, программа извлекает значение из стека и печатает его.

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

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.