А.3.5. Исходные тексты программы-калькулятора

We use cookies. Read the Privacy and Cookie Policy

А.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 */