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

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

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

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


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.004 сек.