• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

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

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

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

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