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

Задание

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

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

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

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

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

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

1.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;

union Value {

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

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

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

Структура 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, до тех пор пока она не кончится

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

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

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

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

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

3. Очистим CurItem

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

b. Выйти с кодом ошибки -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) Входим в цикл, проходящий по всем токенам в массиве с инфиксной формой

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Не нашли, что искали? Воспользуйтесь поиском: