Цель работы: изучить правила формирования постфиксной записи арифметических выражений с использованием стека.
Краткие теоретические сведения
Одной из задач при разработке трансляторов является задача расшифровки арифметических выражений.
Выражение 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/(b– c)*(d+e) | 8.6 | 2.4 | 5.1 | 0.3 | 7.9 | – 26.12 | |
(a+b)*(c– d)/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*(b– c+d)/e | 9.7 | 8.2 | 3.6 | 4.1 | 0.5 | 168.78 | |
(a+b)*(c– d)/e | 0.8 | 4.1 | 7.9 | 6.2 | 3.5 | 2.38 | |
a*(b– c)/(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/c– d))*e | 5.6 | 7.4 | 8.9 | 3.1 | 0.2 | 0.666 | |
a*(b+c)/(d– e) | 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 | |
(a– b)/(c+d)*e | 0.3 | 6.7 | 8.4 | 9.5 | 1.2 | – 0.429 | |
a/(b+c– d*e) | 7.6 | 4.8 | 3.5 | 9.1 | 0.2 | 1.173 | |
a*(b– c)/(d+e) | 0.5 | 6.1 | 8.9 | 2.4 | 7.3 | – 0.144 | |
(a+b*c)/(d– e) | 9.1 | 0.6 | 2.4 | 3.7 | 8.5 | – 2.196 | |
a– b/(c*(d – e)) | 1.4 | 9.5 | 0.8 | 6.3 | 7.2 | 14.594 |
Лабораторная работа №6. Нелинейные списки
Цель работы: изучить алгоритмы обработки данных с использованием нелинейных структур в виде дерева.