МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ БЕЛАРУСЬ

БЕЛОРУССКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет информационных технологий и робототехники (ФИТР) 

Кафедра программного обеспечения вычислительной техники

и автоматизированных систем 
 
 
 

КУРСОВАЯ  РАБОТА 

по дисциплине: ”Основы алгоритмизации и программирования” 

на  тему: ” Разбор строкового выражения. Алгоритм Рутисхаузера.” 
 
 
 

      Выполнил: ст. гр. 107320 Мастега Н.Д. 

      Приняла:  ст. преподаватель И.М.Желакович 
 
 
 
 
 
 
 
 
 
 
 
 
 

Минск  2011

 

Белорусский национальный технический университет 
 

Кафедра программного обеспечения вычислительной техники 

и автоматизированных систем 
 
 
 

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА 

к курсовому проекту (работе) 

по  дисциплине “Основы алгоритмизации и программирования” 

Тема  ” Разбор строкового выражения. Алгоритм Рутисхаузера.” 
 

Исполнитель: Мастега Н.Д.                                            (подпись) 

Студент 1 курса 107320 группы 

Руководитель : Желакович И.М.                                        (подпись) 
 

Минск 2011

 

 

Оглавление

Введение. 4

Математическая формулировка задачи. 6

Описание программы…………………………………………………………………………………..7

Руководство пользователя 8

Выводы (заключение). 10

Список использованной литературы. 11

Приложение 1 (текст программы). 12 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение.

 

   «С  – удобный, выразительный и гибкий язык, пригодный для программирования широкого класса задач», – таково мнение создателей С Брайана Кернигана и Дениса Ритчи. Язык С приобрел широкую известность как язык разработки операционной системы UNIX. Сегодня многие операционные системы написаны на С++.

   С++ – это язык, расширяющий возможности  С. Его разработал Бьерн Страуструп. Название С++ предложил Рик Массити. Оно указывает на эволюционную природу перехода к нему от С, так как «++» – это операция приращения в С.

   C++ - компилируемый  язык программирования общего  назначения. Поддерживая разные  парадигмы программирования, сочетает  свойства как высокоуровневых,  так и низкоуровневых языков. В сравнении с его предшественником, наибольшее внимание уделено  поддержке объектно-ориентированного  и обобщённого программирования. Название «C++» происходит от  языка C, в котором унарный оператор ++ обозначает инкремент переменной.

      Являясь одним из самых популярных языков программирования, C++ широко используется для разработки программного обеспечения. Область его применения включает создание операционных систем, разнообразных  прикладных программ, драйверов устройств, приложений для встраиваемых систем, высокопроизводительных серверов, а  также развлекательных приложений (например, видеоигры). Существует несколько  реализаций языка C++ - как бесплатных, так и коммерческих. Несмотря на то что язык С++ был задуман как набор объектно-ориентированных расширений для языка С, вскоре он развился в самостоятельный язык программирования.

   Подключаемые  библиотеки

   fstream  —

   iostream — заголовочный файл с классами, функциями и переменными для организации ввода-вывода в языке программирования C++. Он включён в стандартную библиотеку C++. Название образовано от Input/Output Stream («поток ввода-вывода»). В языке C++ и его предшественнике, языке программирования Си, нет встроенной поддержки ввода-вывода, вместо этого используется библиотека функций. iostream управляет вводом-выводом, как и stdio.h в Cи. iostream использует объекты cin, cout, cerr и clog для передачи информации в и из стандартных потоков ввода, вывода, ошибок (без буферизации) и ошибок (с буферизацией) соответственно. Являясь частью стандартной библиотеки C++, эти объекты также являются частью стандартного пространства имён — std.

   Стандартная библиотека C++ включает стандартную  библиотеку Си с небольшими изменениями, которые делают её более подходящей для языка C++. Другая большая часть  библиотеки C++ основана на Стандартной  Библиотеке Шаблонов (STL). Она предоставляет  такие важные инструменты, как контейнеры (например, векторы и списки) и  итераторы (обобщённые указатели), предоставляющие доступ к этим контейнерам как к массивам. Кроме того, STL позволяет сходным образом работать и с другими типами контейнеров, например, ассоциативными списками, стеками, очередями. Используя шаблоны, можно писать обобщённые алгоритмы, способные работать с любыми контейнерами или последовательностями, определяемыми итераторами.

   Так же, как и в Си, возможности  библиотек активизируются использованием директивы #include для включения стандартных файлов. Всего в стандарте C++ определено 50 таких файлов

Математическая  формулировка задачи.

 

            В текстовом файле находится выражение, состоящее из числе и знаков арифметических операций. Программа вычисляет это выражение, учитывая приоритет операций и скобки.

           

            Алгоритм Рутисхаузера

            Алгоритм Рутисхаузера является одним из наиболее ранних алгоритмов разбора выражений. Его особенностью является предположение о полной скобочной структуре выражения. Под полной скобочной записью выражения понимается запись, в которой порядок действий задается расстановкой скобок. Неявный приоритет операций при этом не учитывается. Например: D:=((C-(B*L))+K)

           Обрабатывая выражение с полной скобочной структурой, алгоритм присваивает каждому символу из строки номер уровня по следующему правилу:

1. если это открывающаяся скобка или переменная, то значение увеличивается на 1;
2. если знак операции или закрывающаяся скобка, то уменьшается на 1.

   Для выражения (А+(В*С)) присваивание значений уровня будет происходить следующим  образом :

Алгоритм складывается из следующих шагов:

1. выполнить расстановку уровней;
2. выполнить поиск элементов строки с максимальным значением уровня;
3. выделить тройку — два операнда с максимальным значением уровня и операцию, которая заключена между ними;
4. результат вычисления тройки обозначить вспомогательной переменной;
5. из исходной строки удалить выделенную тройку вместе с ее скобками, а на ее место поместить вспомогательную переменную, обозначающую результат, со значением уровня на единицу меньше, чем у выделенной тройки;
6. выполнять п.п.2 — 5 до тех пор, пока во входной строке не останется одна переменная, обозначающая общий результат выражения.

 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

     Для успешной компиляции программы требуется  подключение библиотек. В данной курсовой работе были использованы такие  библиотеки как   <iostream.h>,<fstream>. Далее мы открываем файл с выражением, которое нужно вычислить. При успешном открытии файла данные считываются в символьный массив и выводятся на экран для проверки. Если не получилось открыть файл – выходим из программы с ошибкой "Невозможно открыть файл!".

     Считываем строку из файла и считаем ее длину. Затем ищем отрицательные элементы и пробелы. Перед отрицательными элементами ставим «0» для простоты расчета. Если находим пробел – сдвигаем все символы на одну позицию влево. После этого мы находим места для расстановки скобок. Сначала для приоритетных операций «*» и «/», а потом для «+» и «-».  Далее мы расставляем скобки в выражении, ищем и, если есть, удаляем лишние скобки. После чего расставляем приоритеты во вспомогательном символьном массиве. Получаем индекс элемента строки с наибольшим приоритетом и вычисляем результат операции с двумя операндами. Результат вставляем вместо старых операндов и расставляем приоритет результата в дополнительном массиве. Проверяем формулу на наличие скобок. Пока в выражении есть скобки, мы будем его решать. 
 
 
 
 
 
 
 
 
 
 

Руководство пользователя

 

После запуска  программы пользователю предлагается ввести имя входного файла с выражением: 

Если имя файла  указано не правильно, программа  выведет ошибку :

Если имя файла  указано верно, на экране появится выражение из файла. Первое – без форматирования. Второе – форматированное. 

После расстановки  скобок и приоритетов программа  выведет готовую формулу с  индексами элементов:

Далее программа  поэтапно вычисляет конечный результат:

 

Тестирование

Рисунок 1- первое выражение

Рисунок 2 – второе выражение 

                              Первый случай