Використання стекової адресації

Зазвичай в математиці прийнято записувати знак операції між операндами, напри­клад a+b, c:d і т. д. Такий запис називають інфіксним. При використанні такого запису для обчислення складного виразу необхідно задавати пріоритети операцій. Наприклад, в алгебраїчному виразі

а + bc/d - f

пріоритети можуть бути наступні: х, /, +, -.

Інший підхід, який забезпечує правильне виконання інфіксного запису - викорис­тання дужок, причому, з тим, що обчислення проводиться від внутрішніх дужок до зо­внішніх. В дужковій формі наведений вираз прийме вигляд:

((а + ((Ьс)/а))

Замість аналізу пріоритету знаків операцій тут необхідно визначити дужки з най­більшою глибиною вкладення.

Для реалізації наведеного виразу в комп’ютері можна використати всі раніше описа­ні способи адресації.

Польський математик Ян Лукашевич показав, що якщо знаки арифметичних опе­рацій записувати перед операндами (префіксна форма) чи після операндів (постфіксна форма, або обернений польський запис), то для визначення порядку виконання опера­цій дужки стають непотрібними.

Так, для наведеного вище виразу префіксна форма має вигляд:

- + а/ хbcf,

а постфіксна форма має вигляд:

аbсх/f-

Ця форма - обернений польський запис.

Обернений польський запис прекрасно підходить для проведення обчислень на комп’ютері зі стеком.

Якщо вираз складається із N символів, то алгоритм його обчислення на стеку можна представити у вигляді блок-схеми, показаної на рис. 3.35.

Рис. 3.35. Блок-схема обчислення на стеку виразу, представленого в постфіксній формі

Розглянемо по тактовий стан комірок стеку при реалізації раніше розглянутого ви­разу, записаного в постфіксній формі (рис. 3.36).

а

а

а

а

а

а

а+bс/d

а+bс/d-f

b

b

b*с

b*с

Ь*с/d

f

с

d

Рис. 3.36. Використання стека при розрахунку по формулі в оберненому польському запису

Для реалізації стека можуть бути використані регістри. В цьому випадку схема об­числень з використанням стека має вигляд, показаний на рис. 3.37.

Рис. 3.37. Схема обчислень з використанням регістрового стека

Алгоритм функціонування такий же, як вище описано функціонування на базі основ­ної пам’яті ОП. Операція виконується над вмістом Ргі і результат розміщується в Ргі, а вміст нижніх регістрів зміщується на один крок вверх.

Дата добавления: 2014-11-06