Марк Митчелл - Программирование для Linux. Профессиональный подход

В листинге А.3 показан текст программы, вычисляющей значения постфиксных выражений.

/* Вычисления в унарном формате. */

/* На вход программы подаются однострочные выражения

в обратной польской (постфиксной) записи, например:

602 7 5 - 3 * +

Вводимые числа должны быть неотрицательными

десятичными числами. Поддерживаются операторы

"+", "-" и "*". Унарные операторы "even" и "odd"

возвращают значение 1 в том случае, когда операнд

является четным или нечетным соответственно.

Лексемы разделяются пробелами. Отрицательные числа

не поддерживаются. */

#include

#include

#include

#include

#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:\n");

command_to_parse =

fgets(command_line, sizeof (command_line), stdin);

if (command_to_parse = NULL)

return 0;

token = strtok(command_to_parse, " \t\n");

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, " \t\n");

}

if (empty_stack(number_stack))

return 1;

else {

number answer = pop_stack(number_stack);

printf("%u\n", number_to_unsigned_int(answer));

destroy_number(answer);

clear_stack(&number_stack);

}

}

return 0;

}

Функции, приведенные в листинге А.4 выполняют операции над унарными числами, представленными в виде связных списков.

/* Операции над унарными числами */

#include

#include

#include

#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, реализуют стек унарных чисел, представленных в виде связных списков.

/* Реализация стека значений типа "number". */

#include

#include

#include "definitions.h"

/* Создание пустого стека. */

Stack create_stack() {

return 0;

}

/* Эта функция возвращает ненулевое значение,

если стек пуст. */

int empty_stack(Stack stack) {

return stack == 0;

}

/* Удаление числа, находящегося на вершине стека.

Если стек пуст, программа аварийно завершается. */