Pull to refresh

Вычисление значения выражения «на коленке»

Reading time 2 min
Views 9.2K
Тема навеяна недавними постами Компилятор выражений и Вычисление значения выражения. Рассмотрены два подхода — построение семантического дерева выражения для быстрого вычисления и вычисление самого выражения на ходу при помощи двух своих стеков. Я же хочу показать довольно простой способ реализации, по сути алгоритма из первой статьи, но на базе рекурсии. Иногда бывает уместно переложить часть работы со стеком на комплиятор, благо современные ОС дают нам большой стек и возможность разумного использования рекурсии.

Итак, что такое арифметическое выражение? Как было написано в первой упомянутой статье, структуру выражения можно задать следующими правилами:

выражение ::= слагаемое [«+» или «-» слагаемое] *
слагаемое ::= множитель [«*» или «/» множитель] *
множитель ::= число | переменная | (выражение) | +множитель | -множитель


На заметку: такая форма описания грамматик часто используется в технической документации. В теории она называется БНФ, желающие могут почитать более детально например в википедии.

Проблему анализа текста согласно некой формальной грамматике, как правило решают двумя способами: явное построение конечного автомата (об этом как-то потом) и простенький рекурсивный разбор, который мы сейчас и будем реализовывать.

Руководствуясь приведенной схемой, можно легко записать следующий псведокод для анализа первого правила:

вычислить_выражение()
	результат = вычислить_слагаемое()
	пока есть символы
		если текущий_символ = "+"
			результат = результат + вычислить_слагаемое()
		или если текущий_символ = "-"
			результат = результат - вычислить_слагаемое()
		иначе
			ошибка
	вернуть результат


Абсолютно аналогично пишется разбор операций умножения, а на самом нижнем уровне разбора мы приходим к рекурсии — для вычисления значения в скобках мы просто вызываем вычислить_выражение().

вычислить_множитель()
	результат = 0
	если текущий_символ цифра
		результат = прочитать_число()
	или если текущий_символ буква
		результат = вычислить_переменную()
	или если текущий_символ = "("
		результат = вычислить_выражение()
		если текущий символ != ")"
			ошибка
	или если текущий_символ = "+"
		результат = вычислить_множитель()
	или если текущий_символ = "-"
		результат = -вычислить_множитель()
	иначе
		ошибка
	вернуть результат


Да, в приведенном псевдокоде не учтены пробелы, но для общего ознакомления с идеей этого достаточно. Желающим ознакомиться с рабочей реализацией такого подхода на С++ могу предложить почитать мой код в плагине Popup Plus для миранды: formula.h и formula.cpp.

P.S. если есть желающие почитать о том, как можно использовать грамматики и конечные автоматы для рабора других тектсов, могу написать о простеньком XPath парсере внутри Jabber модуля из той же миранды. Или о том, как разбирать XML.
Tags:
Hubs:
+6
Comments 11
Comments Comments 11

Articles