Реализация стекового калькулятора на Си
Рассмотрим небольшой проект, реализующий стековый калькулятор на Си. Такая программа весьма полезна, поскольку позволяет проводить вычисления, не прибегая к записи промежуточных результатов на бумаге.
Программа состоит из трех файлов: "streal.h", "streal.cpp" и "stcalc.cpp". Первые два файла реализуют стек вещественных чисел, эта реализация уже рассматривалась ранее. Файл "stcalc.cpp" реализует стековый калькулятор на базе стека. Для сборки программы следует объединить все три файла в один проект. Команды построения программы зависят от операционной системы и компилятора, например, в системе Unix с компилятором "gcc" программу можно собрать с помощью команды
g++ -o stcalc -lm stcalc.cpp streal.cpp
в результате которой создается файл "stcalc" с программой, готовой к выполнению.
Ниже приведено содержимое файла "stcalc.cpp". Функция main, описанная в этом файле, организует диалог с пользователем в режиме команда-ответ. Пользователь может ввести число с клавиатуры, это число просто добавляется в стек. При вводе одного из четырех знаков арифметических операций +, -, *, / программа извлекает из стека два числа, выполняет указанное арифметическое действие над ними и помещает результат обратно в стек. Значение результата отображается также на дисплее. Кроме арифметических операций, пользователь может ввести название одной из стандартных функций: sin, cos, exp, log (натуральный логарифм). При этом программа извлекает из стека аргумент функции, вычисляет значение функции и помещает его обратно в стек. При желании список стандартных функций и возможных операций можно расширить. Наконец, можно выполнять еще несколько команд:
| удалить вершину стека; |
| очистить стек; |
| напечатать вершину стека; |
| напечатать содержимое стека; |
| напечатать подсказку; |
| завершить работу программы. |
Каждая команда стекового калькулятора реализуется с помощью отдельной функции. Например, вычитание реализуется с помощью функции onSub():
static void onSub() { double y, x; if (st_size() < 2) { printf("Stack depth < 2.\n"); return; } y = st_pop(); x = st_pop(); st_push(x - y); display(); }
В начале функции проверяется, что глубина стека не меньше двух. В противном случае, выдается сообщение об ошибке, и функция завершается. Далее из стека извлекаются операнды y и x операции вычитания. Элементы извлекаются из стека в порядке, обратном их помещению в стек, поэтому y извлекается раньше, чем x. Затем вычисляется разность y - x, ее значение помещается обратно в стек и печатается на дисплее, для печати вершины стека вызывается функция display.
Приведем полный текст программы.
// Файл "stcalc.cpp" // Реализация стекового калькулятора на базе стека // #include <stdio.h> #include <stdlib.h> #include <ctype.h> #include <string.h> #include <math.h> #include "streal.h" // Интерфейс исполнителя "стек"
// Прототипы функций, реализующих команды калькулятора: // Арифметические операции static void onAdd(); static void onSub(); static void onMul(); static void onDiv();
// Добавить число в стек(вх: текстовая запись числа) static void onPush(const char* line);
// Вычисление математических функций static void onSin(); // sin static void onCos(); // cos static void onExp(); // Экспонента static void onLog(); // Натуральный логарифм static void onSqrt(); // Квадратный корень
// Другие команды static void onPop(); // Удалить вершину стека static void onClear(); // Очистить стек static void display(); // Напечатать вершину стека static void onShow(); // Напечатать содержимое стека static void printHelp(); // Напечатать подсказку
int main() { char line[256]; // Буфер для ввода строки int linelen; // Длина строки
st_init(1024); // Стек.начать работу(1024) // 1024 — макс. глубина стека printHelp(); // Напечатать подсказку
while (true) { // Цикл до бесконечности scanf("%s", line); // ввести строку linelen = strlen(line); // длина строки if (linelen == 0) continue;
// Разобрать команду и вызвать реализующую // ее функцию if (strcmp(line, "+") == 0) { onAdd(); } else if (strcmp(line, "-") == 0) { onSub(); } else if (strcmp(line, "*") == 0) { onMul(); } else if (strcmp(line, "/") == 0) { onDiv(); } else if (strcmp(line, "sin") == 0) { onSin(); } else if (strcmp(line, "cos") == 0) { onCos(); } else if (strcmp(line, "exp") == 0) { onExp(); } else if (strcmp(line, "log") == 0) { onLog(); } else if (strcmp(line, "sqrt") == 0) { onSqrt(); } else if (strcmp(line, "=") == 0) { display(); } else if ( // Если это число isdigit(line[0]) || ( linelen > 1 && (line[0] == '-' || line[0] == '+') && isdigit(line[1]) ) ) { onPush(line); // Добавить число в стек } else if (strcmp(line, "pop") == 0) { onPop(); } else if (strcmp(line, "clear") == 0) { onClear(); } else if (strcmp(line, "show") == 0) { onShow(); } else if (strcmp(line, "quit") == 0) { break; // Завершить работу } else { // Неправильная команда => printHelp(); // напечатать подсказку } } return 0; }
static void onAdd() { double y, x; if (st_size() < 2) { printf("Stack depth < 2.\n"); return; } y = st_pop(); x = st_pop(); st_push(x + y); display(); }
static void onSub() { double y, x; if (st_size() < 2) { printf("Stack depth < 2.\n"); return; } y = st_pop(); x = st_pop(); st_push(x - y); display(); }
static void onMul() { double y, x; if (st_size() < 2) { printf("Stack depth < 2.\n"); return; } y = st_pop(); x = st_pop(); st_push(x * y); display(); }
static void onDiv() { double y, x; if (st_size() < 2) { printf("Stack depth < 2.\n"); return; } y = st_pop(); x = st_pop(); st_push(x / y); display(); }
static void onPush(const char* line) { double x = atof(line); st_push(x); }
static void onSin() { double x; if (st_empty()) { printf("Stack empty.\n"); return; } x = st_pop(); st_push(sin(x)); display(); }
static void onCos() { double x; if (st_empty()) { printf("Stack empty.\n"); return; } x = st_pop(); st_push(cos(x)); display(); }
static void onExp() { double x; if (st_empty()) { printf("Stack empty.\n"); return; } x = st_pop(); st_push(exp(x)); display(); }
static void onLog() { double x; if (st_empty()) { printf("Stack empty.\n"); return; } x = st_pop(); st_push(log(x)); display(); }
static void onSqrt() { double x; if (st_empty()) { printf("Stack empty.\n"); return; } if (st_top() < 0.0) { printf("Arg. of square root is negative.\n"); return; } x = st_pop(); st_push(sqrt(x)); display(); }
static void onPop() { st_pop(); }
static void onClear() { st_clear(); }
static void display() { if (!st_empty()) { printf("=%lf\n", st_top()); } else { printf("stack empty\n"); } }
static void onShow() { int d = st_size(); printf("Depth of stack = %d.", d); if (d > 0) printf(" Stack elements:\n"); else printf("\n");
for (int i = 0; i < d; i++) { printf(" %lf\n", st_elementAt(i)); } }
static void printHelp() { printf( "Stack Calculator commands:\n" " <number> Push а number in stack\n" " +, -, *, / Ariphmetic operations\n" " sin, cos, Calculate a function\n" " exp, log, \n" " sqrt \n" " = Display the stack top\n" " pop Remove the stack top\n" " show Show the stack\n" " clear Clear the stack\n" " quit Terminate the program\n" ); } // Конец файла "stcalc.cpp"
Пример работы программы "stcalc". Пусть нужно вычислить выражение (3*3 + 4*4)1/2
Запишем выражение, используя обратную польскую запись:
3, 3, *, 4, 4, *, +, sqrt
(через sqrt обозначается операция извлечения квадратного корня). Последовательно отдаем соответствующие команды стековому калькулятору. При работе программы stcalc получается следующий диалог:
Stack Calculator commands: <number> Push а number in stack +, -, *, / Ariphmetic operations sin, cos, Calculate a function exp, log, sqrt = Display the stack top pop Remove the stack top show Show the stack clear Clear the stack quit Terminate the program 3 3 * =9.000000 4 4 * =16.000000 + =25.000000 sqrt =5.000000
Обратная польская запись формул оказалась исключительно удобной при работе с компьютерами. Для вычислений используется стек, что позволяет работать с выражениями любой степени сложности. Реализация стекового вычислителя не представляет никакого труда. Имеется также простой алгоритм преобразования выражения из обычной записи, в которой знак операции указывается между аргументами, в ее обратную польскую запись. Все это привело к тому, что многие компиляторы языков высокого уровня используют обратную польскую запись в качестве внутренней формы представления программы. Рассмотрим, к примеру, язык программирования Java. Как всякий объектно-ориентированный язык, он является интерпретируемым, а не компилируемым языком. Это означает, что компилятор Java преобразует исходную Java-программу не в машинные коды, а в промежуточный язык, предназначенный для выполнения (интерпретации) на специальной Java-машине. В случае Java этот промежуточный язык называют байткодом. Компилятор Java помещает байткод в файл с расширением ".class". Байткод представляет собой, упрощенно говоря, обратную польскую запись Java-прогаммы, а Java-машина — стековый вычислитель.
