Обратная польская запись (ОПЗ). Тема 4

В результате наибольшее распространение полу-чил метод трансляции с помощью обратной польской записи, которую предложил польский математик Я. Лукашевич.
ОПЗ представляет собой выражение, записанное в постфиксной форме, без скобок, по специальным правилам.

Пусть для операндов А и В выполняется операция сложения.
Привычная форма записи А+В называется инфиксной.
Форма записи, в которой знак операции следует перед операндами +АВ, называется префиксной.
Если же операция записывается после операндов АВ+, то это постфиксная форма.
Получение ОПЗ реализуется с использованием структур в виде стека и дерева.

Алгоритм, использующий стек
Получение ОПЗ с использованием стека может осуществляться весьма просто на основе алгоритма, предложенного Дейкстрой, кото-рый ввел понятие стекового приоритета операций, например:

Суть алгоритма в следующем
Исходное выражение, записанное в виде строки символов S, просматривается слева направо.
Операнды переписываются в выходную строку В, операции обрабатываются с использованием стека, который первоначально пуст, на основе следующих правил.
1. Если в строке S встретился операнд (буква), то его помещаем в строку В.
2. Если в S встретилась открывающая скобка, то ее помещаем в стек.

3. Если в S встретилась закрывающая скобка, то извлекаем из стека и записываем в строку В все операции до "(", саму "(" скобку также извлекаем из стека. Обе скобки игнорируются.
4. Если в S встретилась операция Х (+, - , *, /), то выталкиваем из стека все операции, приоритет которых не ниже Х, после чего саму операцию Х записываем в стек.
5. При достижении конца строки S, анализируем стек и, если он не пуст, извлекаем и пере-писываем его элементы в выходную строку В.

Пример реализации
Исходное выражение задано в виде строки S
"a + b*c + ( d*e + f )*g"
Запишем это выражение в форме ОПЗ.
Ответом будет выражение (без скобок)
abc*+de*f+g*+
Результат будем получать в строке В.
Начинаем последовательно просматривать сим-волы исходной строки, причем В – пустая строка и стек пуст.

Всего в строке 15 символов (15 п.п.).
1. Букву «a» помещается в строку В
2. Операцию «+» помещаем в стек.
3. Букву «b» помещаем в строку В.
На этот момент стек и строка В выглядят следующим образом:

4. Операцию «*» помещаем в стек, т.к. элемент «+» в вершине стека имеет более низкий приоритет.
5. Букву «с» помещаем в строку В, после чего имеем

6. Следующая операция «+»: анализируем стек и видим, что в вершине стека «*» и следующая за ней «+» имеют приоритеты не ниже текущей. Следовательно, обе операции извлекаем из стека и помещаем в строку В, а текущую операцию «+» помещаем в стек.
В итоге имеем

7. Далее следует символ «(», его помещаем в стек.
8. Букву «d» помещаем в строку В.
В результате получается

9. Операцию «*» помещаем в стек, т.к. приоритет у скобки самый низкий.
10. Букву «e» помещаем в строку В.
Получили

11. Следующая операция «+»: приоритет операции «*» в вершине стека выше, поэтому извлекаем из стека «*» и помещаем в строку В. Текущий символ «+» помещаем в стек.
12. Букву «f» помещаем в строку В. Получаем

13. Далее идет закрывающая скобка, все элементы до символа «(» извлекаем из стека и помещаем в строку В (это элемент «+»), сам символ «(» тоже извлекаем из стека.
Обе скобки игнорируются:

14. Операцию «*» помещаем в стек, т.к. ее приоритет выше операции «+» в вершине стека.
15. Букву «g» записываем в строку В.
Получаем

Все символы строки S просмотрены, следова-тельно, анализируем состояние стека, если он не пуст, то переписываем все его элементы в строку В, т.е. операции «+» и «*» последо-вательно извлекаем из стека в строку:
Просмотрев исходную информацию только один раз, мы решили поставленную задачу.

Вычисление выражения, записанного в ОПЗ, может проводиться путем однократного просмотра, что является весьма удобным при генерации объектного кода программ.
Рассмотрим простой пример.

Выражение (A + B) * (C + D) – E в виде ОПЗ:
AB+CD+*E–
Его вычисление проводится следующим образом (R1, R2, … – вспомогательные переменные):

Текст программы, реализующий рассмотренные алгоритмы, может иметь следующий вид:
. . .
struct Stack {
char c; // Символ операции
Stack *next;
} ;
int Prior (char);
Stack* InS ( Stack*, char);
Stack* OutS ( Stack*, char&);
double Result ( char* );

void main ()
{
Stack *t,
*Op = NULL; // Стек операций Op – пуст
char a, In [81], Out [81];
// In – входная (S), Out – выходная (B) строки
int k, l = 0; // Текущие индексы для строк
cout << " Input formula : ";
cin >> In;

// Анализируем символы строки In
for ( k = 0; In[k] != '\0' ; ++k ) {
// 1. Если символ – буква, заносим ее в Out
if ( In[k] >= 'a' && In[k] <= 'z' )
Out [ l++ ] = In [ k ];
// 2. Если «(», записываем ее в стек
if ( In[k] == '(' )
Op = InS ( Op, In[k] );

/* 3. Если «)», извлекаем из стека в строку Out все операции до открывающей скобки */
if ( In[k] == ')' ) {
while ( (Op -> c) != '(' ) {
// Считываем элемент a из стека
Op = OutS ( Op, a ); if ( !Op ) a = '\0';
// и записываем его в строку Out.
Out [ l++ ] = a; }

// Удаляем из стека открывающую скобку
t = Op;
Op = Op -> next;
delete t;
// Вместо этих трех строк можно записать одну
// Op = OutS ( Op, a );
}

/* 4. Если операция, извлекаем из стека в Out опе-рации с большим или равным приоритетом */
if (In[k]=='+' || In[k]=='–' || In[k]=='*' || In[k]=='/') {
while ( Op != NULL &&
Prior (Op -> c) >= Prior ( In[k] ) ) {
Op = OutS ( Op, a );
Out [ l++ ] = a;
}
// Текущий символ операции записываем в стек
Op = InS ( Op, In[k] );
}
} // Конец цикла for () анализа входной строки

/* 5. Если стек не пуст, извлекаем из него операции и записываем в выходную строку */
while ( Op != NULL ) {
Op = OutS ( Op, a );
Out [ l++ ] = a;
}
Out [ l ] = '\0'; // Окончание строки
cout << "\n Polish = " << Out << endl;
cout << " Res = " << Result ( Out ) << endl;
system("pause");
}

Обратите внимание на то, что группа операторов if() в пунктах 1 – 4 организована НЕ ЭФФЕКТИВНО, поправьте это!!!

// Функция реализации приоритета операций
int Prior ( char a ) {
switch ( a ) {
case '*': case '/': return 3;
case '–': case '+': return 2;
case '(': return 1;
}
return 0;
}

// Добавление элемента в стек
Stack* InS ( Stack *p, char s )
{
Stack *t = new Stack;
t -> c = s;
t -> next = p;
return t;
}

// Извлечение элемента из стека (со ссылкой)
Stack* OutS ( Stack *p, char &s )
{
Stack *t = p;
s = p -> c;
p = p -> next;
delete t;
return p;
}

// ----------- Расчет выражения ОПЗ -----------
double Result (char *str ) {
int i; Stack *begin = NULL;
char ss, ss1, ss2, ssR = 'z' + 1 ;
double op1, op2, res, mas[50];
cout << " Input data" << endl;
for ( i = 0; str[i] != '\0'; ++i ) {
ss = str[i];
if ( ss >= 'a' && ss <= 'z‘ ) { // Буква
cout << ss << " = ";
cin >> mas [ int ( ss - 'a' ) ];
}
}

for ( i=0; str [ i ] != '\0'; ++i ) {
ss = str [ i ];
if ( !( ss == '+' || ss == '-' || ss == '*' ||
ss == '/' || ss == '^' ) ) // Если буквы
begin = InStack ( begin, ss );
else { // Если операции
begin = OutStack (begin, &ss2 );
begin = OutStack (begin, &ss1 );
op2 = mas [ int (ss2 - 'a') ];
op1 = mas [ int (ss1 - 'a') ];

switch ( ss ) {
case '+' : res = op1 + op2; break;
case '-' : res = op1 – op2; break;
case '*' : res = op1 * op2; break;
case '/' : res = op1 / op2; break; // ??
}
mas [ int ( ssR - 'a' ) ] = res;
begin = InStack ( begin, ssR );
ssR ++; // Символ для следующего Ri
} // Конец else
} // Конец for
return res;
} // Конец функции

Пример, реализованный в методичке для оконного приложения:

struct Stack {
char info;
Stack *next;
} *begin;
int Prior (char);
Stack* InStack ( Stack*, char);
Stack* OutStack ( Stack*, char*);
double Rezult (String);
double mas[100]; // Массив для вычисления
Set < char, 0, 255 > znak;
// Множество символов-знаков
int Kol = 10;

//---- Текст функции-обработчика 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];
// ----------- Пункт 1 алгоритма ------------
if (ss >= 'a' && ss <= 'z' )
OutStr += ss;
// ----------- Пункт 2 алгоритма ------------
if ( ss == '(' )
begin = InStack ( begin, ss);

// ----------- Пункт 3 алгоритма ------------
if ( ss == ')' ) {
while ( (begin -> info) != '(' ) {
begin = OutStack ( begin, &a );
OutStr += a;
}
begin = OutStack ( begin, &a );
}

// ----------- Пункт 4 алгоритма ------------
if ( znak.Contains ( ss ) ) {
while ( begin != NULL &&
Prior ( begin->info ) >= Prior ( ss ) ) {
begin = OutStack ( begin, &a );
OutStr += a;
}
begin = InStack ( begin, ss );
} // Конец оператора if
} // Конец оператора for

// ----------- Пункт 5 алгоритма ------------
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(SG1->Cells[1][i]);
}
// SG это StringGrid
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, chr;
double op1, op2, rez;
int len = Str.Length();
znak << '*' << '/' << '+' << '-' << '^';
chr = 'z' + 1;
for (int i=1; i <= len; 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) - 97]; // код ‘a’ - 97
op2 = mas[int (ch2) - 97];