А.3.5. Исходные тексты программы-калькулятора
А.3.5. Исходные тексты программы-калькулятора
В листинге А.3 показан текст программы, вычисляющей значения постфиксных выражений.
Листинг А.3. (calculator.c) Основная часть программы-калькулятора
/* Вычисления в унарном формате. */
/* На вход программы подаются однострочные выражения
в обратной польской (постфиксной) записи, например:
602 7 5 - 3 * +
Вводимые числа должны быть неотрицательными
десятичными числами. Поддерживаются операторы
"+", "-" и "*". Унарные операторы "even" и "odd"
возвращают значение 1 в том случае, когда операнд
является четным или нечетным соответственно.
Лексемы разделяются пробелами. Отрицательные числа
не поддерживаются. */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "definitions.h"
/* Эта функция выполняет указанную бинарную операцию над
операндами, извлекаемыми из стека, помещая результат
обратно в стек, в случае успеха возвращается
ненулевое значение. */
int apply_binary_function(number (*function)(number, number),
Stack* stack) {
number operand1, operand2;
if (empty_stack(*stack))
return 0;
operand2 = pop_stack(stack);
if (empty_stack(*stack))
return 0;
operand1 = pop_stack(stack);
push_stack(stack, (*function)(operand1, operand2));
destroy_number(operand1);
destroy_number(operand2);
return 1;
}
/* Эта функция выполняет указанную унарную операцию над
операндом, извлекаемым из стека, помещая результат
обратно в стек. В случае успеха возвращается
ненулевое значение. */
int apply_unary_function(number (*function)(number), Stack* stack) {
number operand;
if (empty_stack(*stack))
return 0;
operand = pop_stack(stack);
push_stack(stack, (*function)(operand));
destroy_number(operand);
return 1;
}
int main() {
char command_line[1000];
char* command_to_parse;
char* token;
Stack number_stack = create_stack();
while (1) {
printf("Please enter a postfix expression: ");
command_to_parse =
fgets(command_line, sizeof (command_line), stdin);
if (command_to_parse = NULL)
return 0;
token = strtok(command_to_parse, " ");
command_to_parse = 0;
while (token != 0) {
if (isdigit(token[0]))
push_stack(&number_stack, string_to_number(token));
else if (((strcmp(token, "+ ") == 0) &&
!apply_binary_function(&add, &number_stack)) ||
((strcmp(token, "-") == 0) &&
!apply_binary_function(&subtract, &number_stack)) ||
((strcmp(token, "*") == 0) &&
!apply_binary_function(&product, &number_stack)) ||
((strcmp(token, "even") == 0) &&
!apply_unary_function(&even, &number_stack)) ||
((strcmp(token, "odd") == 0) &&
!apply_unary_function(&odd, &number_stack)))
return 1;
token = strtok(command_to_parse, " ");
}
if (empty_stack(number_stack))
return 1;
else {
number answer = pop_stack(number_stack);
printf("%u ", number_to_unsigned_int(answer));
destroy_number(answer);
clear_stack(&number_stack);
}
}
return 0;
}
Функции, приведенные в листинге А.4 выполняют операции над унарными числами, представленными в виде связных списков.
Листинг А.4. (number.c) Арифметика унарных чисел
/* Операции над унарными числами */
#include <assert.h>
#include <stdlib.h>
#include <limits.h>
#include "definitions.h"
/* Создание числа, равного нулю. */
number make_zero() {
return 0;
}
/* Эта функция возвращает ненулевое значение,
если аргумент равен нулю. */
int zerop(number n) {
return n == 0;
}
/* Уменьшение числа на единицу. */
number decrement_number(number n) {
number answer;
assert(!zerop(n));
answer = n->one_less_;
free(n);
return answer;
}
/* Добавление единицы к числу. */
number add_one(number n) {
number answer = malloc(sizeof(struct LinkedListNumber));
answer->one_less_ = n;
return answer;
}
/* Удаление числа. */
void destroy_number(number n) {
while (!zerop(n))
n = decrement_number(n);
}
/* Копирование числа. Эта функция необходима для того,
чтобы при временных вычислениях не искажались
исходные операнды. */
number copy_number(number n) {
number answer = make_zero();
while (!zerop(n)) {
answer = add_one(answer);
n = n->one_less_;
}
return answer;
}
/* Сложение двух чисел. */
number add(number n1, number n2) {
number answer = copy_number(n2);
number addend = n1;
while(!zerop(addend)) {
answer = add_one(answer);
addend = addend->one_less_;
}
return answer;
}
/* Вычитание одного числа из другого. */
number subtract(number n1, number n2) {
number answer = copy_number(n1);
number subtrahend = n2;
while(!zerop(subtrahend)) {
assert(!zerop(answer));
answer = decrement_number(answer);
subtrahend = subtrahend->one_less_;
}
return answer;
}
/* Умножение двух чисел. */
number product(number n1, number n2) {
number answer = make_zero();
number multiplicand = n1;
while (!zerop(multiplicand)) {
number answer2 = add(answer, n2);
destroy_number(answer);
answer = answer2;
multiplicand = multiplicand >one_less_;
}
return answer;
}
/* Эта функция возвращает ненулевое значение, если
ее аргумент является четным числом. */
number even(number n) {
if (zerop(n))
return add_one(make_zero());
else
return odd(n->one_less_);
}
/* Эта функция возвращает ненулевое значение, если
ее аргумент является нечетным числом. */
number odd (number n) {
if (zerop(n))
return make_zero();
else
return even(n->one_less_);
}
/* Приведение строки, содержащей десятичное целое,
к типу "number". */
number string_to_number(char* char_number) {
number answer = make_zero();
int num = strtoul(char_number, (char **)0, 0);
while (num != 0) {
answer = add_one(answer);
--num;
}
return answer;
}
/* Приведение значения типа "number"
к типу "unsigned int". */
unsigned number_to_unsigned_int (number n) {
unsigned answer = 0;
while (!zerop(n)) {
n = n->one_less_;
++answer;
}
return answer;
}
Функции, приведенные в листинге A.5, реализуют стек унарных чисел, представленных в виде связных списков.
Листинг А.5. (stack.c) Стек унарных чисел
/* Реализация стека значений типа "number". */
#include <assert.h>
#include <stdlib.h>
#include "definitions.h"
/* Создание пустого стека. */
Stack create_stack() {
return 0;
}
/* Эта функция возвращает ненулевое значение,
если стек пуст. */
int empty_stack(Stack stack) {
return stack == 0;
}
/* Удаление числа, находящегося на вершине стека.
Если стек пуст, программа аварийно завершается. */
number pop_stack(Stack* stack) {
number answer;
Stack rest_of_stack;
assert(!empty_stack(*stack));
answer = (*stack)->element_;
rest_of_stack = (*stack)->next_;
free(*stack);
*stack = rest_of_stack;
return answer;
}
/* Добавление числа в начало стека. */
void push_stack(Stack* stack, number n) {
Stack new_stack =
malloc(sizeof(struct StackElement));
new_stack->element_ = n;
new_stack->next_ = *stack;
*stack = new_stack;
}
/* Очистка стека. */
void clear_stack(Stack* stack) {
while(!empty_stack(*stack)) {
number top = pop_stack (stack);
destroy_number(top);
}
}
В листинге А.6 показаны объявления типов данных и функций работы со стеком и унарными числами.
Листинг А.6. (definitions.h) Файл заголовков для файлов number.c и stack.c
#ifndef DEFINITIONS_H
#define DEFINITIONS_H 1
/* Представление числа в виде связного списка. */
struct LinkedListNumber {
struct LinkedListNumber* one_less_;
};
typedef struct LinkedListNumber* number;
/* Реализация стека чисел, представленных в виде
связных списков. Значение 0 соответствует
пустому стеку. */
struct StackElement {
number element_;
struct StackElement* next_;
};
typedef struct StackElement* Stack;
/* Операции над стеком. */
Stack create_stack();
int empty_stack(Stack stack);
number pop_stack Stack* stack);
void push_stack(Stack* stack, number n);
void clear_stack(Stack* stack);
/* Операции над числами */
number make_zero();
void destroy_number(number n);
number add(number n1, number n2);
number subtract(number n1, number n2);
number product(number n1, number n2);
number even(number n);
number odd(number n);
number string_to_number(char* char_number);
unsigned number_to_unsigned_int(number n);
#endif /* DEFINITIONS_H */