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

Зворотній польський запис

Читайте также:
  1. Алгебраїчна форма запису комплексних чисел та дії над комплексними числами, записаними у цій формі
  2. Аналитическая запись логической формулы КЦУ
  3. Аудио- видеозаписи как доказательства
  4. Бухгалтерские счета, их виды, строение и порядок записей в счетах
  5. Бухгалтерські записи (проводки) складають перед записом сум на рахунки.
  6. Ввод данных в таблицы. Редактирование записей данных
  7. Ведення відповідних записів щодо його здійснення
  8. Ведите записи
  9. Виды записей и их выбор
  10. Восстановление нечитаемых записей, разорванных и сожженных документов, прочтение шифровальной переписки
  11. Выделенное зеленым записать в тетрадь (конспективно), обязательно- две схемы. Это будет в контрольной работе.
  12. Выполнить задания и результаты записать в тетрадь.

В математиці існує давня традиція поміщати оператор між операндами (x+y), а не після операндів (xy+). Форма з оператором між операндами називається інфіксним записом. Форма з оператором після операндів називається постфіксним чи зворотнім польським записом в честь польського логіка Я.Лукашевича (1958), який вивчав вміст цього запису.

Зворотній польський запис має ряд переваг над інфіксним записом для вираження алгебраїчних формул. По-перше, будь-яка формула може бути виражена без дужок. По-друге, вона зручна для обрахунку формул в машинах з стеками. По-третє, інфіксні оператори мають пріоритети, які довільні і не бажані. Наприклад, ми знаємо, що (a b)+c значить (a b)+c, а не a (b+c), оскільки довільно було визначено, що множення має пріоритет над додаванням. Але чи має пріоритет зсув вліво над логічною операцією І? Зворотній польський запис відсторонює такі непорозуміння.

 

 

Рис. 9.3 - Кожен вагон представляє собою один символ в формулі, яку потрібно перетворити з інфіксної форми в зворотній польський запис.

Існує декілька алгоритмів для перетворення інфікс них формул в зворотній польський запис. Нижче показана ідея Е.Дейкстри. Припустимо, що формула складається з наступних символів: змінних, двохоперандних операндів +, -, *, /, а також лівої і правої дужок. Щоб відмінити кінець формули, ми будемо вставляти символ після останнього символа одної формули і перед першим словом наступної формули.

На рис. 9.3 зображена залізна дорога з Нью-Йорка в Каліфорнію з розвилкою, яка веде в Техас. Кожен символ формули представлений одним вагоном. Поїзд рухається на схід (на право). Перед розвилкою кожен вагон повинен зупинятись і дізнаватись, чи потрібно йому рухатись прямо в Каліфорнію, чи він по дорозі повинен повернути в Техас. Вагони, які містять змінні, завжди їдуть в Каліфорнію і ніколи не повертають в Техас. Вагони, які містять всі інші символи, повинні перед входженням в розвилку дізнаватись про вміст найближчого вагона, який відправився в Техас.

В таблиці на рис.5.15. показана залежність ситуації від того, який вагон відправився останнім в Техас і який вагон знаходиться перед розвилкою. Перший завжди відправляється в Техас. Числа відповідають наступним ситуаціям:

1. Вагон на розвилці направляється в Техас.

2. Останній вагон, який відправився в Техас, розвертається і направляється в Каліфорнію.

3. Вагон, який знаходиться на розвилці, і останній вагон, який відправився в Техас, зникають (тобто обидва знищуються).

4. Зупинка. Символи, які знаходяться в Каліфорнії, представляють собою формулу в зворотнім польськім записі, якщо читати зліва направо.

5. Зупинка. Виникла помилка. Початкова формула була не коректно збалансована.

 

    Вагон на розвилці
    + P * / ( )
Вагон, який відправився останнім в сторону Техаса              
+              
P              
*              
/              
(              

Рис. 9.4 - Алгоритм перетворення інфіксного запису в зворотній польський запис.

Після кожної дії проводиться нове порівняння вагона, який знаходиться на розвилці, і вагона, який на даний момент останнім відправився на Техас. Цей процес продовжується доти, поки не буде досягнуто кроку 4. Відмітимо, що лінія на Техас використовується як стек, де відправка вагона в Техас – це поміщення елемента в стек, а повернення вагона, відправленого в Техас, в сторону Каліфорнії – це витягування елемента із стеку.

 

Таблиця 9.1 - Деякі приклади інфіксних виразів і їх еквіваленти в зворотнім польськім записі.

Інфіксний запис Зворотній польський запис
А+В С А В+С А В+С D (A+B)/(C-D) A B/C ((A+B) C+D)/(E+F+G) ABC + AB C+ AB C D + AB+CD-/ AB C/ AB+C D+E F+G/

 

Порядок змінних в інфіксному і польському записі однаковий. Проте, порядок операторів не завжди однаковий. В зворотнім польськім записі оператори появляються в тім порядку, в якім вони будуть виконуватися. В табл. 9.1 подані приклади інфікс них формул і їх еквівалентів в зворотнім польськім записі.

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)