Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Синтаксичний аналіз арифметичних виразів

Фундаментальні алгоритми на графах і деревах.

 

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

Процес обчислення арифметичних виразів можна представити у вигляді бінарного дерева. Дійсно, кожен з арифметичних операторів (+- *, /) вимагає двох операндів, які також будуть арифметичними виразами і, відповідно можуть розглядатися як піддерева. Рис. 7 показує приклад дерева, відповідного вираженню:

 

 

Рис. 7. Синтаксичне дерево, відповідне арифметичному вираженню (6).

 

У такому дереві кінцевими вузлами завжди будуть змінні (тут x) або числові константи, а усі внутрішні вузли міститимуть арифметичні оператори. Щоб виконати оператор, потрібно спочатку вичислити його операнди. Таким чином, дерево на малюнку слід обходити з кінця. Відповідна послідовність вузлів називається зворотним польським записом арифметичного вираження.

При побудові синтаксичного дерева слід звернути увагу на наступну особливість. Якщо є, наприклад, вираження

і операції складання і віднімання ми прочитуватимемо зліва на право, то правильне синтаксичне дерево міститиме мінус замість плюса (рис. 8а). По суті, це дерево відповідає вираженню. Полегшити складання дерева можна, якщо аналізувати вираження (8) навпаки, справа наліво. В цьому випадку виходить дерево з рис. 8б, еквівалентне дереву 8а, але таке що не вимагає заміни знаків.

Аналогічно справа наліво треба аналізувати вирази, що містять оператори множення і ділення.

 

Рис. 8. Синтаксичні дерева для вираження a - b + c при читанні зліва направо (а) і справа наліво (б).

 

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

 


Читайте також:

  1. ABC-XYZ аналіз
  2. II. Багатофакторний дискримінантний аналіз.
  3. SWOT-аналіз у туризмі
  4. SWOT-аналіз.
  5. Tема 4. Фації та формації в історико-геологічному аналізі
  6. V. Нюховий аналізатор
  7. АВС (XYZ)-аналіз
  8. Автомати­зовані інформаційні систе­ми для техніч­ного аналізу товар­них, фондових та валют­них ринків.
  9. Алгоритм однофакторного дисперсійного аналізу за Фішером. Приклад
  10. Алгоритми арифметичних операцій над цілими невід’ємними числами у десятковій системі числення.
  11. Альтернативна вартість та її використання у проектному аналізі
  12. Аналіз активів банку




Переглядів: 925

<== попередня сторінка | наступна сторінка ==>
Системи числення і способи переведення чисел із однієї системи числення в іншу | Розв’язання.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.071 сек.