Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


Лабораторная работа №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

Выражение a b c d e Результат
a/(bc)*(d+e) 8.6 2.4 5.1 0.3 7.9 – 26.12
(a+b)*(cd)/e 7.4 3.6 2.8 9.5 0.9 – 81.89
a– (b+c*d)/e 3.1 5.4 0.2 9.6 7.8 2.16
a/b– ((c+d)*e) 1.2 0.7 9.3 6.5 8.4 – 131.006
a*(bc+d)/e 9.7 8.2 3.6 4.1 0.5 168.78
(a+b)*(cd)/e 0.8 4.1 7.9 6.2 3.5 2.38
a*(bc)/(d+e) 1.6 4.9 5.7 0.8 2.3 – 0.413
a/(b*(c+d))– e 8.5 0.3 2.4 7.9 1.6 1.151
(a+(b/cd))*e 5.6 7.4 8.9 3.1 0.2 0.666
a*(b+c)/(de) 0.4 2.3 6.7 5.8 9.1 – 1.091
a– (b/c*(d+e)) 5.6 3.2 0.9 1.7 4.8 – 17.51
(ab)/(c+d)*e 0.3 6.7 8.4 9.5 1.2 – 0.429
a/(b+cd*e) 7.6 4.8 3.5 9.1 0.2 1.173
a*(bc)/(d+e) 0.5 6.1 8.9 2.4 7.3 – 0.144
(a+b*c)/(de) 9.1 0.6 2.4 3.7 8.5 – 2.196
ab/(c*(d – e)) 1.4 9.5 0.8 6.3 7.2 14.594

Лабораторная работа №6. Нелинейные списки

Цель работы: изучить алгоритмы обработки данных с использованием нелинейных структур в виде дерева.


Поделиться:



Популярное:

  1. I WORK UNDER MANY DIFFICULTIES (я работаю в трудных условиях: «под многими сложностями»)
  2. А. В. Петровский разработал следующую схему развития групп. Он утверждает, что существует пять уровней развития групп: диффузная группа, ассоциация, кооперация, корпорация и коллектив.
  3. Бакалаврская выпускная работа
  4. Безопасность объектов почтовой связи и работающего персонала.
  5. БИЛЕТ 13. Работа по перемещению контура с током в магнитном поле. Энергия магнитного поля
  6. Биообратная связь: современное направление йоги
  7. БУДЕТ ЛИ ЭТО РАБОТАТЬ У ВАС?
  8. В помещении насосного блока находится электрооборудование, работающее под высоким напряжением, и подача жидкости пенообразователя может вызвать замыкание.
  9. Ваня: В ТОС меня привело желание подзаработать денег на свою мечту. Я хочу приобрести себе новый телефон. Про Трудовой отряд я узнал от своего друга Леши. И вот мы решили пойти работать .
  10. Взаимосвязь экономического и психологического подхода в работах Даниэля Канемана и Вернона Смита.
  11. Вопрос 22. Параллельная работа источников электроэнергии постоянного и переменного токов в авиационных системах электроснабжения.
  12. Вопрос 37. Работа читального зала архива


Последнее изменение этой страницы: 2016-07-13; Просмотров: 1333; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.023 с.)
Главная | Случайная страница | Обратная связь