Реклама

Наш канал:

Таненбаум Э.- Архитектура компьютера. стр.290

5. Остановка. Произошла ошибка. Изначальная формула была некорректно сбалансирована.

Рис. 5.16. Алгоритм преобразования инфиксной записи в постфиксную

После каждого действия производится новое сравнение вагона, находящегося у стрелки (это может быть тот же вагон, что и в предыдущем сравнении, а может

быть следующий вагон), и вагона, который на данный момент последним ушел на Техас. Этот процесс продолжается до тех пор, пока не будет достигнут шаг 4. Отметим, что линия на Техас используется как стек, где отправка вагона в Техас — это помещение элемента в стек, а разворот отправленного в Техас вагона в сторону Калифорнии — это выталкивание элемента из стека.

Порядок следования переменных в инфиксной и постфиксной записи одинаков. Однако порядок следования операторов не всегда один и тот же. В обратной польской записи операторы появляются в том порядке, в котором они будут выполняться. В табл. 5.5 даны примеры инфиксных формул и их эквивалентов в обратной польской записи.

Таблица 5.5. Некоторые примеры инфиксных выражений и их эквиваленты в обратной польской записи

Вычисление формул в обратной польской записи

Обратная польская запись идеально подходит для вычисления формул на компьютере со стеком. Формула состоит из п символов, каждый из которых является либо операндом, либо оператором. Алгоритм для вычисления формулы в обратной польской записи с использованием стека прост. Нужно просто прочитать обратную польскую запись слева направо. Если встречается операнд, его нужно поместить в стек. Если встречается оператор, нужно выполнить заданную им операцию.

Таблица 5.6 иллюстрирует вычисление машиной ЦУМ следующего выражения:

(8 + 2 х 5) / (1 + 3 х 2 - 4).

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

825х+132х + 4-/.

В таблице мы ввели команды умножения и деления 1М111_ и Ю1\/. Число на вершине стека — это правый операнд (а не левый). Это очень важно для операций деления и вычитания, поскольку порядок следования операндов в данном случае имеет значение (в отличие от операций сложения и умножения). Другими словами, команда Ю1\/ действует следующим образом: сначала в стек помещается числитель, потом знаменатель, и тогда операция дает правильный результат. Отметим, что преобразовать обратную польскую запись в У УМ-код очень легко: нужно просто двигаться по формуле в обратной польской записи, записывая по

одной команде для каждого символа. Если символ является константой или переменной, нужно вписывать команду помещения этой константы или переменной в стек, если символ является оператором, нужно вписывать команду для выполнения данной операции.

Таблица 5.6. Использование стека для вычисления формулы в обратной польской записи

Режимы адресации в командах перехода

До сих пор мы рассматривали только те команды, которые оперируют данными, Командам перехода (а также командам вызова процедур) также нужны особые режимы адресации для определения целевого адреса. Режимы адресации, о которых мы говорили в предыдущих подразделах, применимы и к большинству команд перехода. Один из возможных режимов — прямая адресация, когда целевой адрес просто полностью включается в команду.