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

 

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

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

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

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

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

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

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

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

                Выполнил: ст. гр. 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.

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

N симв. 1 2 3 4 5 6 7 8 9
Символы строки ( A + ( B * C ) )
Номера  уровней 1 2 1 2 3 2 3 2 1

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

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

 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

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

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

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

 

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

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

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

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

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

 

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

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

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

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

                              Второй случай

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

 

     В данной курсовой работе  был изучен и реализован на практике алгоритм Рутисхаузера. В ходе курсового проектирования были использованы условный оператор, оператор выбора, инициализация массивов. Рассмотрены основные характеристики используемых языке программирования – С++. Вся программа протестирована на различных наборах данных и ошибок выявлено не было. 
 

 

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

 

1. Уолтер Сэвитч. С++ в примерах. Москва: Эком, 1997. (3 шт.)

2. В.А. Скляров.  Язык С++ и объектно-ориентированное   программирование. –Мн.: Выш. шк.,1997. (20 шт.)

3. Язык программирования  Си. Москва: Производственно-внедренческий  кооператив "И Н Т Е Р Ф Е Й С", 1988. (0)

4. Б.В. Керниган,Д.М. Ричи. ЯЗЫК С. (17 шт.)

5. В.А. Скляров.  Программирование на языках Си  и Си++. Мн.: Выш. шк.,1997. (2 шт.)

6. Страуструп  Бьерн. Язык программирования  Си++. М.: Софт,1999. (10 шт.).

7. Шилд Герберт. - Самоучитель C++ / Герберт Шилдт . - СПб : BHV - Санкт-Петербург, 1997. - 511 с. (1).

8. Как программировать  на С++ . Дж. Дейтел. Пер. В. Кузьменко . - М. : ЗАО "Издательство БИНОМ", 1998. - 1021 с. : ил.(1).

9. Visual C++ 6 Новые возможности для программистов. Ю. Тихомиров.- СПб.:БХВ-Санкт-Петербург,1998.-496 с.

10. Основы алгоритмизации  и программирования. Язык СИ. Е.М.Демидович.Мн.: “Бестпринт” 2003 г.

11.Использование  Visual C++ 6. Специальное издание. Грегори К.: Пер. с англ.-М.;СПб.;К.: Издательский дом “Вильямс”, 2001.-864 с.

 

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

 

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

// 

#include <iostream>

#include <fstream>

using namespace std;

//поиск и  обработка отрицательных чисел

void negative_change();  

//поиск места  для скобок

void place_to_bracket(); 

//вставка  скобок в найденные места

void _input(int, int);  

//удаление  тройки (2 операнда и операция) и  скобок

void _delete(int, int); 

//выполнение алгоритма

void do_it(); 

//поиск скобок  в формуле (если не осталось - получен ответ)

bool no_bracket(); 

//поиск наибольшего  приоритета

int place_with_max(); 

//выделение  тройки от места с наибольшим  приоритетом

void get_answer(int); 

//вставка результата

void include_answer(int, int, int); 

char str[256]; //формула

char sign[256]; //приоритеты элементов

int len;

int main ()

{

      setlocale(LC_ALL,"rus"); //разрешение на русский язык

      char file[64];

      cout<<"Введите имя файла: ";

      cin>>file;

      ifstream in(file, ios::in); //создаём поток ввода, связанный с файлом (без указания пути - в текущем каталоге)

      if (!in) //если не получилось

      {

            cerr<<"Невозможно открыть файл!";     //пишем это

            exit(EXIT_FAILURE);      //и выходим из программы

      }

      in.getline(str,256); //читаем формулу из потока

      len=strlen(str);  //считаем длину

      cout<<str<<endl;

      negative_change(); //ставим нули перед отрицательными числами для простоты расчёта

                                    cout<<str<<"\n\n"; //вывод форматированной формулы

      place_to_bracket(); //расставляем приоритет скобками

                                    cout<<str<<endl;  //показываем, что получилось

      do_it();   //решаем формулу

      cout<<str<<endl;  //ответ

      in.close();  //закрываем файл

      return 0;

} 

void negative_change()

{

      for (int i=0; i<len; i++)        //пробег по всем символам формулы

      {

            if (str[i]=='-'&&(str[i-1]=='('||!i))  //если символ - минус, а предыдущий '('

            {

                  for (int right=strlen(str+i)+i+2; right>i; right--) //то сдвигаем все символы на 1 позицию вправо

                        str[right]=str[right-1];      

                  str[i]='0';     //и вставляем 0

                  len++;                    //увеличиваем значение длины

            }

            else if (str[i]==' ')      //если нашли пробел (они в формуле лишние)

            {

                  for (int target=i; target<len; target++)  //двигаем все символы на 1 влево

                        str[target]=str[target+1];  //т. е. уничтожаем пробел

                  --len;     //-1 к длине

                  --i;  //возврат счётчика i на 1 назад, чтобы снова смотреть след. символ

            }

      }

} 

void place_to_bracket()

{

      int balance=0, left=0, right=0, j=0;

      bool empty=true;

      for (int step=2; step; step--)     //шаг первый (приоритетные операции * и /)

            for (int i=0; i<len; i++)    //идём от начала до конца строки

            {

                  if (step==2&&(str[i]=='*'||str[i]=='/'))  //если первый шаг и символ == * или /

                        {

                              for (j=i-1; j>=0; j--)   //двигаем влево

                              {

                                    if (str[j]==')') //сохраняем

                                          balance++;   //баланс

                                    else if (str[j]=='(')    //скобок

                      balance--;  //чтобы дойти

                      //до нужного места слева

            if(((str[j]=='*'||str[j]=='/'||str[j]=='-'||str[j]=='+')&&!balance)||(str[j]=='('&&balance==-1)?j,balance=0,1:0)

                                          break;

                              }

                              left=j+1;   //когда дошли, запоминаем позицию, куда вставить '('

                              for (j=i+1; j<len; j++)  //то же самое вправо

                              {

                                    if (str[j]=='(')

                                          balance--;

                                    else if (str[j]==')')

                                          balance++;

                                    if(((str[j]=='*'||str[j]=='/'||str[j]=='-'||str[j]=='+')&&!balance)||(str[j]==')'&&balance==1)?j--,balance=0,1:0)

                                          break;

                              }

                                  right=isalnum(str[j])?j:j-1; //то же самое, только с коррекцией позиции                                                                                                                                                                                                  //(тернарный оператор)

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