През последния си семестър учих за парсер в дизайна на компилатора. Но всичко това беше теоретично. Исках да направя нещо практично. Затова реших да направя Библиотека за аритметичен анализатор с всички тригонометрични и логаритмични функции, които могат да се използват и от други за оценка на изрази. А езикът kotlin е много лесен за писане и идиоматичен.
цели
- Библиотека, предоставяща функцията за оценка на израза
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 с evaluate() и след това накрая оценете отговорите на част 1 и част 2 с оператора found.
Една стъпка на път
Ние ще създадем анализатор стъпка по стъпка, разбирайки работата.
Първа стъпка: Работа само с оператори
Докато работим с множество оператори, ние също трябва да се погрижим за приоритета на операторите. Например 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(). Тази функция отчита броя на отворените и затварящите скоби, които среща, докато търси оператор.
- Ако не. на ‘(‘ › номер на ‘)’, ние сме в скобите.
- Ако не. на ‘(’ = бр. на ‘)’, ние сме извън скобите.
- И ако не. на ‘(‘ ‹ номер на ‘)’, в израза има синтактична грешка.
И ако няма оператори извън скобите в израза, но има скоби в началото и края на израза, тогава трябва да ги премахнем и да оценим оставащия израз. Използвайте тази проверка, преди да върнете стойност.
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 тук:
Това е за сега.
