Польская инверсная запись (ПОЛИЗ)
ПОЛИЗ, или, как её еще называют, обратная польская запись, это способ бесскобочного представления выражений (не только арифметических), в которых операнды предшествуют операции. Например, выражение
в обратной польской записи буде выглядеть следующим образом:
Выражение, представленное в ПОЛИЗ, замечательно тем, что оно может быть вычислено за один проход слева направо без возвратов и забеганий вперед. Вычисление выражения в ПОЛИЗ выполняется следующим образом. Двигаясь слева направо по строке, операнды помещаем в стек. Когда встретится операция, то она выполняется над операндами, находящимися на вершине стека. Результат операции помещается в вершину стека вместо использованных операндов. Таблица, приведенная ниже, иллюстрирует процесс вычисления. В столбце "Входная строка" подчеркнута обработанная часть строки. Промежуточные результаты обозначены R0,R1,R2. Окончательный результат вычисления – единственный элемент на вершине стека операндов.
| Входная строка | Стек | Пояснение |
| 4 A * 2 X / - 3 B * 2 Y * + * | ||
| 4 A * 2 X / - 3 B * 2 Y * + * | A4 | |
| 4 A * 2 X / - 3 B * 2 Y * + * | R0 | R0=4*A |
| 4 A * 2 X / - 3 B * 2 Y * + * | 2R0 | |
| 4 A * 2 X / - 3 B * 2 Y * + * | X2R0 | |
| 4 A * 2 X / - 3 B * 2 Y * + * | R1R0 | R1=2/X |
| 4 A * 2 X / - 3 B * 2 Y * + * | R0 | R0=R0-R1 |
| 4 A * 2 X / - 3 B * 2 Y * + * | 3R0 | |
| 4 A * 2 X / - 3 B * 2 Y * + * | B3R0 | |
| 4 A * 2 X / - 3 B * 2 Y * + * | R1R0 | R=3*B |
| 4 A * 2 X / - 3 B * 2 Y * + * | 2R1R0 | |
| 4 A * 2 X / - 3 B * 2 Y * + * | Y2R1R0 | |
| 4 A * 2 X / - 3 B * 2 Y * + * | R2R1R0 | R2=2*Y |
| 4 A * 2 X / - 3 B * 2 Y * + * | R1R0 | R2=R1+R2 |
| 4 A * 2 X / - 3 B * 2 Y * + * | R0 | R0=R0*R1 |
Таблица 2. Вычисление значения выражения, заданного польской записью.
Отметим, что в обратную польскую запись может быть преобразована любая компьютерная программа. В области архитектуры ЭВМ в своё время это привело к созданию безадресных ЭВМ, в области программного обеспечения – к созданию так называемых "прямых" методов трансляции. Весьма популярным в течение некоторого времени был язык ФОРТ, полностью базирующийся на ПОЛИЗ.
Рассмотрим алгоритм преобразования скобочного выражения в ПОЛИЗ. Для простоты ограничимся арифметическими выражениями, использующими четыре действия арифметики. Предположим также, что операнды только переменные с однобуквенными идентификаторами. Преобразование выполняется за один проход. Строка просматривается слева направо.
Операнды сразу помещаются в выходную строку.
Знаки операций сначала помещаются в стек. Прежде чем быть помещенным в стек, знак операции выталкивает из стека все операции, которые имеют приоритет больше или равный приоритета входной операции.
Открывающая скобка просто помещается в стек как операция с самим низким приоритетом.
Закрывающая скобка выталкивает из стека в выходную строку все операции вплоть до ближайшей открывающей скобки, которая удаляется из стека, но в выходную строку не помещается. Закрывающая скобка в стек не помещается.
После того как входная строка закончилась, остаток стека выталкивается в выходную строку.
Текст алгоритма преобразования приведен ниже.
struct opri{ // знаки операций и их приоритеты
char oper; // операция
unsigned char prior; // приоритет
};
//---------------------------------------------
static opri tpri[]={ // таблица приоритетов
{'+',1},
{'-',1},
{'*',2},
{'/',2}
};
// Приоритет операции из входной строки
static unsigned char vhpri;
//----------------------------------------------
static char Class(char z){
// Классификация символов из входной строки
// Символ может быть отнесен к одному из классов:
// - 'б' – буква (операнд)
// - 'о' – операция
// - '('
// - ')'
// - 'н' – недопустимый символ
int i;
if(z=='(' || z==')') return z;
if(isalpha(z)) return 'б'; // буква – операнд
for(i=0;i<sizeof(tpri)/sizeof(opri);i++){
if(z==tpri[i].oper){
vhpri=tpri[i].prior;
return 'о'; // знак операции
}
}
return 'н'; // недопустимый символ
}
//-------------------------------------------------
int Poliz(char *in,char *out){
// in – входная строка
// out – выходная строка
// функция возвращает 0 в случае успеха или номер ошибки
int i,j,v;
opri Stack[MAXSTACK];
j=-1; // Номер очередного выходного символа
v=-1; // указатель на вершину стека
for(i=0;i<strlen(in);i++){
switch (Class(in[i])) {
case 'б': // буква
// Операнды сразу помещаются в выходную строку
out[++j]=in[i];
break;
case 'о': // операция
// Операция выталкивает из стека все операции
// с приоритетом >=
while(v>=0 && vhpri<=Stack[v].prior){
out[++j]=Stack[v--].oper;
}
// после чего сама помещается в стек
Stack[++v].oper=in[i];
Stack[v].prior=vhpri;
break;
case '(':
// Открывающая скобка просто помещается в стек
// как операция с самым низким приоритетом
Stack[++v].oper=in[i];
Stack[v].prior=0;
break;
case ')':
// Закрывающая скобка выталкивает из стека всё,
// вплоть до открывающей скобки включительно
// но сама в стек не помещается
for(;v>=0;v--){
if(Stack[v].oper=='('){
break;
} else {
out[++j]=Stack[v].oper;
}
}
if(v<0){
return 1; // Непарная открывающая скобка
}
v--;
break;
case 'н':
return 2; // недопустимый символ
default:
return 9; // Ошибка в программе
} /* switch */
out[j+1]=0;
} /* for i */
/* Остаток стека – на выход */
for(;v>=0;v--){
if(Stack[v].oper=='('){
// Непарная открывающая скобка
return 3;
}
out[++j]=Stack[v].oper;
}
out[++j]=0;
return 0;
} // Poliz