Файл: Алгоритмы и структуры (программирование).docx

Московский Государственный Открытый Университет

Курсовая работа

по дисциплине: «Структуры и алгоритмы обработки данных»

Выполнил:

студент 2 курс

факультет: ИРЭ

специальность: 230105/с

Данилов А.С. 610184

Проверил:

Найденов В.В.

Москва, 2012

Оглавление

1.Задание 3

2.Описание работы программы 5

3.Блок-схема алгоритма 8

4.Листинг программы 30

Файл infix2postfix.c 30

Файл infix2postfix.h 36

Файл unit_tests.c 37

5.Список используемой литературы 41

1. Задание

Написать программу на языке С для преобразования выражения из инфиксной (привычной) записи в постфиксную (обратную польскую).

Для перевода выражения из инфиксной формы в постфиксную с учетом приоритетов операций и скобок существует простой алгоритм (Дейкстры). Алгоритм работает со стеком, в котором хранятся знаки операций. Сначала стек пуст. На вход алгоритму подается последовательность лексем (числа, скобки или знаки операций), представляющая некоторое арифметическое выражение, записанное в инфиксной форме. Результатом работы алгоритма является эквивалентное выражение в постфиксной форме. Вводятся приоритеты операций: открывающая скобка имеет приоритет 0, знаки '+' и '–' — приоритет 1 и знаки '*' и '/' — приоритет 2.

1. Пока не достигнут конец входной последовательности, читать очередную лексему и выполнять с ней следующие операции:

   1. если прочитан операнд (число), записать его в выходную последовательность;

   2. если прочитана открывающая скобка, положить её в стек;

   3. если прочитана закрывающая скобка, вытолкнуть из стека в выходную последовательность всё до открывающей скобки, при этом сами скобки уничтожаются (удаляются из стека и в ответ не идут);

   4. если прочитан знак операции, вытолкнуть из стека в выходную последовательность все операции с большим либо равным приоритетом, а прочитанную операцию положить в стек.

2. Если достигнут конец входной последовательности, вытолкнуть всё из стека в выходную последовательность и завершить работу.

---

Заметим, что порядок операндов в выходной последовательности не отличается от порядка операндов в исходной последовательности. В выходной последовательности отсутствуют скобки.

Пример:

ввод:

(1 + 23 * 4)*(5 - 1)

вывод:

1 23 4 * + 5 1 - *

В качестве операндов допустимы как целочисленные константы, так и имена переменных.

Имя переменной может содержать символы A-Z,a-z,0-9,_, но начинаться с цифры не может. Решение оформить в виде отдельного .c модуля, .h файл приведен ниже. Снабдить модульными тестами (unit-tests).

#ifndef INFIX2POSTFIX_H

#define INFIX2POSTFIX_H

/* типы лексем: константы, операции, имена переменных */

typedef enum { tt_CONST, tt_OPER, tt_ID } TokenType;

/* виды операций: сложение, вычитание, умножение, деление, левая и правая скобки */

typedef enum { op_ADD, op_SUB, op_MUL, op_DIV, op_LBR, op_RBR } OperType;

/* максимальная длина имени переменной */

#define MAX_ID_LEN 40

/* тип - лексема */

typedef struct {

   TokenType ttype;

   unionValue{

       /* с лексемой связано одно из следующих значений */

       int inum;

       OperType otype;

       char id[MAX_ID_LEN + 1];

   } tvalue;

} Token;

/* перевести текстовую строку (s) в массив лексем (*tokens).

  получается массив длиной (*len).

  память под выходной массив выделяется внутри функции,

  а освобождается вызывающей стороной.

  в случае успеха вернуть 0, иначе какой-либо код ошибки. */

int tokenize(const char *s, Token **tokens, int *len);

/* перевести набор лексем из инфиксного порядка в постфиксный.

  память выделяется внутри функции, освобождается вызывающей стороной.

  в случае успеха вернуть 0, иначе какой-либо код ошибки. */

int infix2postfix(const Token *infix, int in_len,

                 Token **postfix, int *out_len);

#endif

---

2. Описание работы программы

Структура StrArray:

Состоит из двух элементов: динамического массива строк (** item) и переменной (counti), в которую записывается количество строк в массиве.

Функция short add_item(struct StrArray* array, char* new_item):

Выделяет память и добавляет новую строку в массив item.

Процедура void free_items(struct StrArray* array):

Освобождает память выделенную под массив item.

Процедура void GetItems(const char* s, struct StrArray *InputItems):

Принимает строку sи выбирает из нее «слова/данные» разделенные любым кол-вом пробелов или символов табуляций. Затем записывает выделенные «слова/данные» в массивInputItems.item.

1. Инициализируем индекс CurCh для обхода строк

2. Инициализируем флаг separat которые показывает что был встречен разделитель (символ пробела или таба)

3. Инициализируем строку в которой будем собирать текущее слово

4. Очищаем CurItem

5. Инициализируем индекс(CurCh_inNew) который будет считать кол-во символов в новом найденном слове

6. Входим цикл, который обходит по символьно строку CurCh, до тех пор пока она не кончится

   1. В случае нахождения разделителя устанавливаем separat = 1

   2. Если данный символ не разделитель

      1. Если separat == 1, то обнуляем его

         1. если кол-во символов в новом слове не равняется 1, то запишем его в массив с помощью add_item.

         2. Установим CurCh_inNew = 0

         3. Очистим CurItem

   3. Добавим текущий символ в CurItem

7. Если CurItem не пуста, то добавим ее в InputItems

Функция int tokenize(const char *s, Token **tokens, int *len):

Принимает строку(s) и преобразует ее в массив (**tokens).

1. Инициализируем структуру ItemsArray для хранения слов выделенных из строки

2. С помощью GetItems получим в структуру ItemsArray слова

3. Инициализируем массив токенов

4. Входим в цикл обходящий все слова в ItemsArray

   1. Устанавливаем указатель на теще слово

   2. Выделяем память под новый токен

   3. Устанавливаем указатель на текущий токен

   4. Условие: если в слове один символ и первый символ в слове == + или – или * или / ( или ) то

      1. Записать в структуру Token что текущий символ является оператором (tt_OPER)

      2. Сохранить слово в Token

   5. Если нет, то

      1. Заводим индекс CurChar = 1

         1. Если первый символ в слове является числом

            1. Входим в цикл читающий посимвольно слово, до конца

            2. Условие: если текущий символ не является числом,то

               1. Освободить память ItemsArray

               2. Выйти с кодом ошибки -1

            3. Записать в структуру Token что текущий символ является числом (tt_CONST)

            4. Преобразовать слово в число и сохранить в Token

         2. Если нет, то проверяем является ли текущий символ алфавитным. Если да, то

            1. Входим в цикл читающий посимвольно слово, до конца

            2. Условие если текущий символ не алфавитный и не является числом, то

               1. Освободить память ItemsArray

               2. Выйти с кодом ошибки -1

            3. Записать в структуру Token что текущий символ является переменной (tt_ID)

            4. Сохранить слово в Token

         3. Если нет, то

            1. Освободить память ItemsArray

            2. Выйти с кодом ошибки -1

5. Освободить память ItemsArray

---

Структура TokensDArray:

Состоит из двух элементов: динамического массива токенов (*items) и переменной (count), в которую записывается количество токенов в стеке.

Функция short push(TokensDArray *stack, const Token *token):

Выделяет память под новый элемент стека и кладет токен(*token) в конец.

Функция short pop(TokensDArray *stack, Token **TokensArray, int *len):

Вынимает токен из конца стека и возвращает его.

Функция short out_UntilBrac(TokensDArray *stack, Token **TokensArray, int *len):

Вынимает последний токен из стека(*stack) и записывает его в массив токенов(**TokensArray).

Выполнение таких операции продолжается до нахождения открывающей строчки.

Функция int infix2postfix(const Token *infix, int in_len, Token **postfix, int *out_len):

Преобразование массива с инфиксной формой(*infix)в массив с постфиксной формой(**postfix).

1. Инициализируем массив токенов

2. Инициализируем структуру для стека

3. Инициализируем массив стека

4. Входим в цикл, проходящий по всем токенам в массиве с инфиксной формой

   1. Условие. Если текущий токен является оператором, то

      1. Если текущий токен == (, то поместить токен в стек с помощью push

      2. Если текущий токен == ), то вывести все до открывающей скобки в выходную последовательность с помощью out_UntilBrac

      3. Если ни «(» ни «)», то

         1. Если токен == «+» или «-»,то

            1. Входим в цикл, выполняющийся до тех пор пока текущий токен == «+» или «-» или «*» или «/»

               1. Вынимаем токен из стека в выходную последовательность

            2. Помещаем токен в стек

         2. Если нет, то если токен == «*» или «/»

            1. Входим в цикл, выполняющийся до тех пор пока текущий токен == «*» или «/»

               1. Вынимаем токен из стека в выходную последовательность

            2. Помещаем токен в стек

         3. Если нет, то выходим с кодом ошибки -1

   2. Если нет, то если текущий токен является числом или перемнной, то

      1. Выделяем память под новый токен в массиве с постфиксной формой

      2. Записываем теущий токен из массиво с инфиксной формой в массив с постфиксной

   3. Если нет, то выходим с кодом ошибки -2

5. Выводим все оставшиеся токены в стеке в массив с постфиксной формой с помощью out_everyth

6. Освобождаем память из под стека

---

---