Польская инверсная запись (ПОЛИЗ)

ПОЛИЗ, или, как её еще называют, обратная польская запись, это способ бесско­боч­ного представления выражений (не только арифметических), в которых операнды пред­шествуют операции. Например, выражение

в обратной польской записи буде выглядеть следующим образом:

Выражение, представленное в ПОЛИЗ, замечательно тем, что оно может быть вычислено за один проход слева направо без возвратов и забеганий вперед. Вычисление выражения в ПОЛИЗ выполняется следующим образом. Двигаясь слева направо по строке, операнды помещаем в стек. Когда встретится операция, то она выполняется над операндами, находящимися на вершине стека. Результат операции помещается в вершину стека вместо использованных операндов. Таблица, приведенная ниже, иллюстрирует процесс вычисления. В столбце "Входная строка" подчеркнута обработанная часть строки. Промежуточные результаты обозначены R₀,R₁,R₂. Окончательный результат вычисления – единственный элемент на вершине стека операндов.

Входная строка	Стек	Пояснение
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

Дата добавления: 2014-12-08