|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Лабораторная работа №5. Обратная польская запись
Цель работы : изучить правила формирования постфиксной записи арифметических выражений с использованием стека. Краткие теоретические сведения Одной из задач при разработке трансляторов является задача расшифровки арифметических выражений. Выражение a+b записано в инфиксной форме, +ab – в префиксной , ab+ – в постфиксной формах. В наиболее распространенной инфиксной форме для указания последовательности выполнения операций необходимо расставлять скобки. Польский математик Я. Лукашевич использовал тот факт, что при записи постфиксной формы скобки не нужны, а последовательность операндов и операций удобна для расшифровки. Постфиксная запись выражений получила название обратной польской записи (ОПЗ). Например, в ОПЗ выражение r = (a + b) *(c + d) – e; выглядит следующим образом: r = ab + cd + *e – . Алгоритм преобразования выражения из инфиксной формы в формуОПЗ был предложен Дейкстрой. При его реализации вводится понятие стекового приоритета операций. Рассмотрим алгоритм получения ОПЗ из исходной строки символов, в которой записано выражение в инфиксной форме. 1. Символы-операнды переписываются в выходную строку, в которой формируется постфиксная форма выражения. 2. Открывающая скобка записывается в стек. 3. Очередная операция выталкивает в выходную строку все операции из стека с большим или равным приоритетом. 4. Закрывающая скобка выталкивает все операции из стека до ближайшей открывающей скобки в выходную строку, открывающая скобка удаляется из стека, а закрывающая – игнорируется. 5. Если после просмотра последнего символа исходной строки в стеке остались операции, то все они выталкиваются в выходную строку. 5.2. Пример выполнения задания Написать программу расшифровки и вычисления арифметических выражений с использованием стека. Вид формы и полученные результаты представленный на рис. 5.1. Приведем только тексты используемых функций-обработчиков и созданных функций пользователя (тексты функций InStack и OutStack взять в лаб.раб.3, заменив тип int на char):
... struct Stack { char info; Stack *next; } *begin; int Prior (char); Stack* InStack( Stack*, char); Stack* OutStack( Stack*, char*); double Rezult(String); double mas[201]; // Массив для вычисления Set < char, 0, 255> znak; // Множество символов-знаков int Kol = 8; //--------------- Текст функции-обработчика FormCreate ------------- Edit1-> Text = " a+b*(c-d)/e"; Edit2-> Text = " "; char a = 'a'; StringGrid1-> Cells[0][0] =" Имя"; StringGrid1-> Cells[1][0] =" Знач."; for(int i = 1; i< Kol; i++) { StringGrid1-> Cells[0][i] = a++; StringGrid1-> Cells[1][i] = i; } //---------------------- Текст функции-обработчика кнопки Перевести ---------------- Stack *t; begin = NULL; // Стек операций пуст char ss, a; String InStr, OutStr; // Входная и выходная строки OutStr = " "; Edit2-> Text = " "; InStr = Edit1-> Text; znak < < '*' < < '/' < < '+' < < '-' < < '^'; int len = InStr.Length(), k; for (k = 1; k < = len; k++) { ss = InStr[k]; // Открывающую скобку записываем в стек if ( ss == '(' ) begin = InStack(begin, ss); if ( ss == ')' ) { // Выталкиваем из стека все знаки операций до открывающей скобки while ( (begin -> info)! = '(' ) { begin = OutStack(begin, & a); // Считываем элемент из стека OutStr += a; // Записываем в строку } begin = OutStack(begin, & a); // Удаляем из стека '(' скобку } // Букву (операнд) заносим в выходную строку if (ss > = 'a' & & ss < = 'z' ) OutStr += ss; /* Если знак операции, то переписываем из стека в выходную строку все опера-ции с большим или равным приоритетом */ if (znak.Contains(ss)) { while ( begin! = NULL & & Prior (begin -> info) > = Prior (ss) ) { begin = OutStack(begin, & a); OutStr += a; } begin = InStack(begin, ss); } } // Если стек не пуст, переписываем все операции в выходную строку while ( begin! = NULL){ begin = OutStack(begin, & a); OutStr += a; } Edit2-> Text = OutStr; // Выводим полученную строку } //---------------------- Текст функции-обработчика кнопки Посчитать --------------- char ch; String OutStr = Edit2-> Text; for (int i=1; i< Kol; i++) { ch = StringGrid1-> Cells[0][i][1]; mas[int(ch)]=StrToFloat(StringGrid1-> Cells[1][i]); } Edit3-> Text=FloatToStr(Rezult(OutStr)); //-------- Функция реализации приоритета операций----------- int Prior ( char a ){ switch ( a ) { case '^': return 4; case '*': case '/': return 3; case '-': case '+': return 2; case '(': return 1; } return 0; } //---------------- Расчет арифметического выражения ---------------------------- double Rezult(String Str) { char ch, ch1, ch2; double op1, op2, rez; znak < < '*' < < '/' < < '+' < < '-' < < '^'; char chr = 'z'+1; for (int i=1; i < = Str.Length(); i++){ ch=Str[i]; if (! znak.Contains(ch)) begin = InStack(begin, ch); else { begin = OutStack(begin, & ch1); begin = OutStack(begin, & ch2); op1 = mas[int (ch1)]; op2 = mas[int (ch2)]; switch (ch){ case '+': rez=op2+op1; break; case '-': rez=op2-op1; break; case '*': rez=op2*op1; break; case '/': rez=op2/op1; break; case '^': rez=pow(op2, op1); break; } mas[int (chr)] = rez; begin = InStack(begin, chr); chr++; } } return rez; }
Рис. 5.1 5.3. Индивидуальные задания Написать программу формирования ОПЗ и расчета полученного выражения. Разработать удобный интерфейс ввода исходных данных и вывода результатов. Работу программы проверить на конкретном примере (табл. 5.1). Таблица 5.1
Лабораторная работа №6. Нелинейные списки Цель работы: изучить алгоритмы обработки данных с использованием нелинейных структур в виде дерева. Популярное:
|
Последнее изменение этой страницы: 2016-07-13; Просмотров: 1429; Нарушение авторского права страницы
