2. Побудова польського інверсного запису

Для полегшення процесу виконання програми використовується польський інверсний запис (ПОЛІЗ).

Польський інверсний запис – форма запису математичних виразів, в якій операнди знаходяться перед знаками операцій.

Побудувати ПОЛІЗ можна спираючись на таблицю пріоритетів, яка наведена нижче (таблиця 2.3).

Таблиця 2.3. Таблиця пріоритетів

Символ	Пріоритет
[ ( if dowhile	0
] ) else endif enddo input output	1
:=	2
or	3
and	4
not	5
< <= > >= == <>	6

Продовження таблиці 2.3

+ -	7
/ *	8

Розглянемо алгоритм побудови ПОЛІЗ.

• Ідентифікатори та константи проходять від входу прямо на вихід, а операції потрапляють на вихід через стек.

• Якщо пріоритет операції, що знаходиться в стеку, більше або рівний пріоритету поточної операції, то операція зі стеку подається на вихід і пункт 2 повторюється. Інакше поточна операція заноситься в стек.

• Якщо стек пустий, то поточна операція заноситься в нього.

• Якщо вхідний ланцюжок порожній, то всі операції зі стеку виштовхуються на вихід. Це є ознакою кінця побудови ПОЛІЗ.

Розглянемо особливості обробки дужок.

• Відкриваюча дужка повинна мати найнижчий пріоритет, але записуючись до стеку, нічого не виштовхувати.

• Закриваюча дужка повинна мати пріоритет на 1 більший, ніж відкриваюча, щоб виштовхувати все включаючи відкриваючу дужку, але не більше.

• Відкриваюча дужка не передається на вихід.

• Закриваюча дужка не записується у стек.

Для реалізації деяких операторів необхідно ввести оператор умовного переходу по брехні (УПБ) та оператор безумовного переходу (БП).

2.6.1 Поліз оператора умовного переходу

Оператор умовного переходу має наступний вигляд:

if <ЛВ>

<список операторів1>

else

<список операторів2>

endif

Блок-схема даного оператора буде виглядати наступним чином (рисунок 2.6).

ЛВ

ні

так

m1:

список операторів 2

список операторів 1

m2:

Рисунок 2.6. Блок-схема оператору умовного переходу

По Enterгенерується міткаm1 та УПБ. Поelse–m2 БПm1:. Поendif–m2:.

Тоді ПОЛІЗ матиме наступний вигляд:

ЛВ m1 УПБ <список операторів 1>m2 БП m1: <список операторів 2>m2:

Розберемо побудову ПОЛІЗ на конкретному прикладі.

if a < z Enter a := 6 else a := 9 endif

Побудова ПОЛІЗ приведена в таблиці нижче (таблиця 2.4).

Таблиця 2.4. Побудова ПОЛІЗу умовного оператора

П О Л І З

a

z

< m1 УПБ

a

6

:= m2 БП m1:

a

9

:= m2:

С Т Е К

if

if

< if

< if

if m1

if m1

:= if m1

:= if m1

if m1 m2

if m1 m2

:= if m1 m2

:= if m1 m2

Вхід

if

a

<

z

Enter

a

:=

6

else

a

:=

9

endif

Отриманий ПОЛІЗ буде мати наступний вигляд: az<m1 УПБa6 :=m2 БПm1:a9 :=m2: .

2.6.2 Поліз оператору циклу

Оператор циклу має наступний вигляд:

dowhile <ЛВ>

<список операторів>

enddo

Блок-схема цього циклу буде виглядати наступним чином (рисунок 2.7).

ЛВ

m1:

ні

так

список операторів

m2:

Рисунок 2.7. Блок-схема оператора циклу

По dowhile генерується міткаm1. ПоEnter – m2: УПБ. По enddo – m1БПm2.

Тоді ПОЛІЗ матиме наступний вигляд:

m1: <ЛВ> m2:УПБ <список операторів> m1 БП m2

Розберемо побудову ПОЛІЗ на конкретному прикладі.

dowhile z > 9 Enter z := z – 3 enddo

Побудова ПОЛІЗ приведена в таблиці нижче (таблиця 2.5).

Таблиця 2.5. Побудова ПОЛІЗу циклу

П О Л І З	m1 :	z		9	> m2: УПБ	z		z		3	- := m1 БП m2
С Т Е К	dowhile	dowhile	> dowhile	> dowhile	dowhile m1	dowhile m1	:= dowhile m1	:= dowhile m1	- := dowhile m1	- := dowhile m1
Вхід	dowhile	z	>	9	Enter	z	:=	z	-	3	enddo

Отриманий ПОЛІЗ буде мати наступний вигляд: m1:z9>m2:УПБzz3-:=m1БПm2.