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

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

Читайте также:
  1. ABC-анализ данных о поставщиках
  2. II. Основные проблемы, вызовы и риски. SWOT-анализ Республики Карелия
  3. III ЭТАП: РЕЗУЛЬТАТЫ АНАЛИЗА
  4. III. ЗАЩИТНЫЕ ДЕЙСТВИЯ Я, РАССМАТРИВАЕМЫЕ КАК ОБЪЕКТ АНАЛИЗА
  5. Quot;См.: Маркс К. Капитал. Кн. I. отд. 4, гл. XIII, а также весьма интересный анализ
  6. V. Ситуационный анализ сферы народных художественных промыслов
  7. VI. Анализ человека массы

Задача синтаксического анализа заключается в том, чтобы по имеющейся строке, содержащей арифметическое выражение, и известным значениям, входящих в нее переменных, вычислить значение выражения.

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

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

В таком дереве концевыми узлами всегда будут переменные (здесь x) или числовые константы, а все внутренние узлы будут содержать арифметические операторы. Чтобы выполнить оператор, надо сначала вычислить его операнды. Таким образом, дерево на рисунке следует обходить в концевом порядке. Соответствующая последовательность узлов

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

При построении синтаксического дерева следует обратить внимание на следующую особенность. Если есть, например, выражение

и операции сложения и вычитания мы будем считывать слева на право, то правильное синтаксическое дерево будет содержать минус вместо плюса (рис. 9а). По сути, это дерево соответствует выражению Облегчить составление дерева можно, если анализировать выражение (8) наоборот, справа налево. В этом случае получается дерево с рис. 9б, эквивалентное дереву 8а, но не требующее замены знаков.

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

Рис. 9. Синтаксические деревья для выражения ab + c при чтении слева направо (а) и справа налево (б).


Дата добавления: 2015-08-09; просмотров: 148 | Нарушение авторских прав


Читайте в этой же книге: Введение. | Сущность рекурсии | Сложная рекурсия | Пример 2. | Рекуррентные соотношения. Рекурсия и итерация | Основные определения. Способы изображения деревьев | Прохождение деревьев | Представление дерева в памяти компьютера | Примеры рекурсивных алгоритмов | Задачи на графах |
<== предыдущая страница | следующая страница ==>
Ханойские башни| Быстрые сортировки

mybiblioteka.su - 2015-2024 год. (0.006 сек.)