В моем последнем семестре я изучал синтаксический анализатор в дизайне компилятора. Но это все было теоретически. Я хотел заняться чем-нибудь практическим. Поэтому я решил создать Библиотеку арифметического синтаксического анализатора со всеми тригонометрическими и логарифмическими функциями, которые также могли бы использоваться другими для оценки выражений. А язык котлин очень прост в написании и идиоматичен.
Цели
- Библиотека, предоставляющая функцию для оценки выражения
val result = ExpressionParser().evaluate("sin(PI)+1+cos(PI)")
// result = 0.0
- Не только оценивать выражения с
+,-,*,/, но также может анализировать и оценивать такие функции, как sin, cos, log и т. Д.
Хадзиме (Давай начнем)
Хорошо, давайте сначала сделаем enum class для операторов
private enum class Operators(val sign: Char) {
MINUS('-'),
PLUS('+'),
MULTIPLY('*'),
DIVISION('/'),
POWER('^'),
EXPONENTIAL('E');
}
Мы реализуем рекурсивный парсер с Kotlin. Итак, как мы анализируем выражение? Во-первых, мы будем различать операторы (например, +, -, *, /, ^ и круглые или маленькие скобки). Попытаемся визуализировать выражение «4.2 * (2 * 3.5) ^ 2» как рекурсивное дерево
Теперь для этого мы создадим функцию evaluate(expression:String). Теперь, что будет внутри функции оценки? Ну, основная идея состоит в том, чтобы искать в выражении оператор. Затем разделите выражение на две части. Часть 1 (слева от оператора) и Часть 2 (справа от оператора). Затем recusively evaluate значение Части 1 и Части 2 с помощью функции Assessment (), а затем, наконец, оцените ответы части 1 и Части 2 с помощью найденного оператора.
Один шаг за раз
Мы будем создавать парсер пошагово разбираясь в работе.
Шаг первый: работа только с операторами
При работе с несколькими операторами мы также должны заботиться о приоритете операторов. Например, 2 + 3 * 4 должно быть вычислено как 2+ (3 * 4) = 14, а не (2 + 3) * 4 = 20.The order of precedence from low to high is: ( ), - +, / *, ^.
Если есть несколько операторов с самым низким приоритетом, выберите последний. Это важно для правильной оценки. Например «12–4–4». Это должно быть рассчитано как «(12–4) - 4» = 4, а не «12 - (4–4)» = 12. То же самое верно и для делений.
Пока наша функция может анализировать выражение только с -,+,*,/,^,E операторами.
Второй шаг: обработка скобок
Для обработки () и правильной оценки выражения функция evaluate() должна будет сделать следующее: сначала она должна искать только операторы вне скобок и оценивать части выражения, если они найдены. Если нет, функция evaluate должна проверить, заключено ли выражение в круглые скобки, удалите их и оцените выражение.
Для этого мы сделаем модифицированную версию lastIndexOf(). Эта функция подсчитывает количество открывающихся и закрывающихся круглых скобок, с которыми она сталкивается при поиске оператора.
- Если нет. of ‘(‘ ›no. of‘) ’, мы заключены в круглые скобки.
- Если нет. of ‘(‘ = no. of ‘)’, мы вне скобок.
- А если нет. of ‘(‘ ‹no. of‘) ’, в выражении есть синтаксическая ошибка.
И если в выражении нет операторов вне скобок, но есть скобки в начале и в конце выражения, то мы должны удалить их и оценить оставшееся выражение. Используйте эту проверку перед возвратом значения.
if (expression.startsWith('(') && expression.endsWith(')')) {
return evaluate(expression.substring(1,expression.lastIndex))
}
Третий шаг: научная запись и унарный +, -
Для больших значений удобно отображать число в научной форме. Например, 300000000 = 3E8, т.е. 3 * (10⁸). С научным обозначением мы также получаем унарный минус (3E-8) и унарный плюс (3E + 10).
Унарный минус - это частный случай минуса. Унарный минус - это не оператор, а просто знак отрицательного значения. Следовательно, если мы находим оператор «+» или «-», мы должны проверить, действительно ли это оператор или унарный плюс или минус. Для этого мы создадим функцию isOperator(), которая будет проверять, является ли оператор законным или нет.
Поскольку теперь существует возможность, что найденный оператор на самом деле не является оператором, нам также понадобится дополнительный цикл. Если найден оператор, который не является оператором, мы должны снова проверить, есть ли другой. Цикл в функции оценки будет выглядеть так:
Четвертый шаг: функции обработки
Математические функции в выражении будут иметь вид «Sin (0,25 * pi)». Сначала имя функции, затем открываются круглые скобки «(«, затем выражение и строка заканчивается закрывающими скобками »)»
Мы проверим, есть ли открывающиеся круглые скобки «(« где-нибудь в выражении, и проверим, заканчивается ли выражение закрывающими скобками «)». Затем мы проверим часть перед (слева) от «(» - это имя функции. Если это так, выполните часть, заключенную в круглые скобки, и выполните найденную функцию.
Пятый шаг: математические константы
Мы можем добавить небольшую задачу в конец evaluate(), чтобы проверить, является ли выражение Value или Constant
Итак, наш оператор возврата в конце теперь будет выглядеть так
Итак, время для тестирования,
val result = ExpressionParser().evaluate("1+sin(PI)+cos(PI)")
println(result)
Результат должен быть 0,0, но на самом деле мы получаем 2.220446049250313E-16, и это довольно близко только к 0. Но почему не 0. Ответ Floating Point errors. Что ж, внутренне компьютеры используют формат (двоичная с плавающей запятой), который вообще не может точно представить число вроде 0,1, 0,2 или 0,3. Вы можете нажать на эту ссылку: Ошибки с плавающей запятой, чтобы узнать больше.
Итак, оставим ли мы здесь наш парсер?
Мы сделаем функцию, которая округлит результат до определенной точности.
private fun roundToPrecision(value:Double,precision: Int = 3):Double{
val corrector = 10.0.pow(precision).toInt()
return round(value*corrector)/corrector
}
Вы можете проверить этот замечательный блог Романа Елизарова: Плавающая точка для десятичных дробей, чтобы узнать, как округлить результат.
Итак, если мы теперь оценим 1+sin(PI)+cos(PI), мы получим «0,0».
Ура, мы создали собственный арифметический синтаксический анализатор, способный обрабатывать несколько операторов, математических функций и сложных выражений.
Но я изначально сказал, что мы сделаем для него библиотеку. Что об этом? Что ж, будем. Мы сделаем мультиплатформенную библиотеку Kotlin для этого парсера. Для этого следите за моей следующей статьей, в которой я расскажу «Как настроить многоплатформенные библиотеки для начинающих».
А пока вы можете получить весь исходный код Parser здесь:
Это пока что.
