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

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

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

Выполнил:

студент 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