Польская инверсная запись (ПОЛИЗ)
ПОЛИЗ, или, как её еще называют, обратная польская запись, это способ бесскобочного представления выражений (не только арифметических), в которых операнды предшествуют операции. Например, выражение
в обратной польской записи буде выглядеть следующим образом:
Выражение, представленное в ПОЛИЗ, замечательно тем, что оно может быть вычислено за один проход слева направо без возвратов и забеганий вперед. Вычисление выражения в ПОЛИЗ выполняется следующим образом. Двигаясь слева направо по строке, операнды помещаем в стек. Когда встретится операция, то она выполняется над операндами, находящимися на вершине стека. Результат операции помещается в вершину стека вместо использованных операндов. Таблица, приведенная ниже, иллюстрирует процесс вычисления. В столбце "Входная строка" подчеркнута обработанная часть строки. Промежуточные результаты обозначены 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}
};
// Приоритет операции из входной строки
Дата добавления: 2014-12-02; просмотров: 1942;