Полная версия

Главная arrow Информатика arrow Алгоритмы и структуры данных

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

ИСПОЛЬЗОВАНИЕ СТЕКА ДЛЯ ПРЕОБРАЗОВАНИЯ ФОРМ ЗАПИСИ ВЫРАЖЕНИЙ

В инфиксной записи операция разделяет два операнда, в постфиксной — операция следует за двумя операндами, в префиксной — операция предшествует двум операндам. Примеры записи арифметических выражений в различных формах приведены в табл. 1.1.

Таблица 1.1

Формы записи арифметических выражений

Инфиксная запись

Постфиксная запись

Префиксная запись

А+В

АВ+

+АВ

А+В-С

АВ+С-

+А-ВС

А*В+С

АВ*С+

+*АВС

А+В*С

АВС*+

+А*ВС

(А+В)*С

АВ+С*

*+АВС

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

Таблица 1.2

Перевод инфиксной формы записи выражения в постфиксную (польскую)

Элемент выражения

Действие

Открывающая скобка

Вталкивание открывающей скобки в стек.

Операнд

Запись операнда в постфиксную строку.

Закрывающая скобка

Выталкивание элементов из стека до первой открывающей скобки и запись их в постфиксную строку, затем выталкивание самой открывающей скобки без записи ее в постфиксную строку. Если перед выполнением этой операции стек оказался пустым, значит, для данной закрывающей скобки не было парной открывающей, т.е. возникла исключительная ситуация.

Элемент выражения

Действие

Операция

Если стек не пуст и приоритет операции ниже либо такой же (<), как у верхней операции в стеке (открывающая скобка в данном контексте считается операцией с низшим приоритетом), то выталкивание элементов из стека до операции с меньшим приоритетом (реально: для операций «+» и «—» до «(», а для операций «*» и «/» до «+»,

«—» или «(») или до опустошения стека и запись их в постфиксную строку; в противном случае стек не изменяется. Затем вталкивание операции в стек.

После просмотра выражения выталкиваются из стека и записываются в постфиксную строку оставшиеся операции.

Вычисление значения выражения по его постфиксной записи. Постфиксное выражение сканируется слева направо и обрабатывается в соответствии с алгоритмом, приведенным в табл. 1.3.

Таблица 1.3

Вычисление значения выражения по его постфиксной записи

Элемент

выражения

Действие

Операнд

Вталкивание операнда в стек

Операция

Выталкивание из стека двух элементов, выполнение операции с ними, запись результата в стек.

Результат выполнения последней операции является результатом вычисления всего выражения.

Перевод из инфиксной формы записи выражения в префиксную. Инфиксное выражение сканируется справа налево, и префиксная строка строится также справа налево. Алгоритм преобразования такой же, как и при преобразовании в постфиксную форму, только открывающие скобки меняются на закрывающие и, наоборот. При определении приоритета операции отношение «<» изменяется на «<», чтобы равноприоритетные операции выполнялись слева направо.

Вычисление значения выражения по его префиксной записи. Алгоритм вычисления полностью совпадает с алгоритмом вычисления по постфиксной записи, но префиксная строка сканируется справа налево.

 
<<   СОДЕРЖАНИЕ   >>