Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Алгоритм вычисления выражений в обратной польской записи




Читайте также:
  1. II 3. ASTM ВЫЧИСЛЕНИЯ
  2. II 5.2. Нетто вычисления
  3. IV. Подготовка к решению выражений со скобками.
  4. IV. Решение выражений.
  5. IV. Решение выражений.
  6. V. Решение и сравнение выражений.
  7. V. Решение и сравнение выражений.
  8. V. Сравнение выражений.
  9. Алгоритм RSA
  10. Алгоритм виконання часткового технологічного процесу

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

Например, необходимо вычислить 7+5*2 : 752*+

Вход Действия Магазин (стек)
752*+ Записать в стек операнд (7) 7
52*+ Записать в стек операнд (5) 57
2*+ Записать в стек операнд (2) 257
*+ 1. прочитать операнд (2) 2. прочитать операнд (5) 3. выполнить операцию (*) 4. записать результат в стек (10) 10 7
+ 1. прочитать из магазина (10) 2. прочитать из магазина (7) 3. выполнить операцию (+) 4. записать результат 17

 

Алгоритм Э.Дейкстры перевода выражения в ПОЛИЗ (метод стека с приоритетами):

1. Каждому знаку операции присваивается числовой приоритет. Он начинается с цифры 2 и операции, выполняемой в первую очередь, имеют больший приоритет.

2. Открывающимся скобкам присваивается 0, закрывающимся 1.

3. Входная строка читается слева направо. Операнды по мере считывания помещаются в выходную строку.

4. Знаки перед записью в выходную строку помещаются в стек по следующему алгоритму:

a) открывающаяся скобка (знак с приоритетом 0) помещается в стек

b) если приоритет знака операции больше приоритета знака на вершине стека или стек пуст, новый знак добавляется в стек

c) если приоритет знака меньше или равен приоритету знака на вершине стека, из стека в выходную строку “выталкиваются” все знаки с приоритетами, большими или равными приоритету входного знака. После этого входной знак записывается в стек

d) закрывающаяся скобка выталкивается в выходную строку все знаки до открывающейся скобки. Открывающаяся скобка удаляется из стека, а закрывающаяся туда не записывается.

5. после просмотра всех символов входной строки из стека выталкиваются оставшиеся знаки.

Например:


Дата добавления: 2015-01-29; просмотров: 30; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2020 год. (0.004 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты