Студопедия

КАТЕГОРИИ:

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


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




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

Например, необходимо вычислить 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. после просмотра всех символов входной строки из стека выталкиваются оставшиеся знаки.

Например:

стек Выходная строка
( a
+( ab
ab+
/ ab+
(/ ab+c
+(/ ab+cd
/ ab+cd+
ab+cd+/

Поделиться:

Дата добавления: 2015-01-29; просмотров: 214; Мы поможем в написании вашей работы!; Нарушение авторских прав





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