Разработка расширяемого алгоритма строкового калькулятора

Что такое строковый калькулятор?

Перед тем, как мы начнем обсуждать создание строкового калькулятора, давайте определимся, что это такое. Строковый калькулятор (далее просто «калькулятор») — это алгоритм или программа, которая преобразует арифметическое выражение, представленное в виде строки (String), в числовое значение (Double).

Приведу конкретные примеры:
«cos(-pi/)^2 + sin(-pi/2)^2» => 1
«tanh(-2*pi)-(e^(-2*pi)-1)/(e^(-2*pi)+1)» => 0

Мотивация

Почему я решилa создать строковый калькулятор?

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

Пользователь должен иметь возможность работать с различными операциями
(бинарными операторами и унарными функциями), которые он определяет
самостоятельно.
Калькулятор должен поддерживать работу с константами (например, число π,
число Эйлера и т.д.), которые также задает пользователь.
При вычислении выражения сначала должны выполняться операции, заключенные в круглые скобки.
Должен соблюдаться приоритет операций, например, сначала должны выполняться операции умножения, а затем сложения.
Калькулятор должен корректно обрабатывать ситуации, когда унарная
функция используется для обозначения обратного элемента (например, «-1»)
относительно некоторой операции.

Создание такого строкового калькулятора позволит мне эффективно реализовать алгоритм оценки параметров системы дифференциальных уравнений и обеспечит гибкость для пользователей в работе с выражениями и операциями.

Определим сущности

В коде мы начнем с определения классов для объектов, таких как бинарные операторы, унарные функции и константы. Для этого воспользуемся конструкциями языка Scala.

//бинарная операция trait BinaryOperation {    def getDesignation: String // обозначение самой операции например +,-,*    def getPriority: Int // приоритет операции   def getSingleElement: Double // единичный элемент относительно данной операции    def calc(left: Double, right: Double): Double // что делает операция    //переопределяем метод equals   override def equals(obj: Any): Boolean = {     obj match {       case str: String => getDesignation == str       case _ => if (obj == null || getClass != obj.getClass) false       else getDesignation == obj.asInstanceOf[BinaryOperation].getDesignation     }   }  }  // унарная функция trait UnaryFunction {    def getDesignation: String // обозначение самой операции например ln,cos,exp    def calc(number: Double): Double // что делает операция    //переопределяем метод equals   override def equals(obj: Any): Boolean = {     obj match {       case str: String => getDesignation == str       case _ => if (obj == null || getClass != obj.getClass) false       else getDesignation == obj.asInstanceOf[UnaryFunction].getDesignation     }   }  }  // сconstanta trait Constant {    def getDesignation: String // обозначение самой операции например pi,e   def getValue: Double // значение     //переопределяем метод equals   override def equals(obj: Any): Boolean = {     obj match {       case str: String => getDesignation == str       case _ => if (obj == null || getClass != obj.getClass) false       else getDesignation == obj.asInstanceOf[Constant].getDesignation     }   }  }

Чтобы прояснить синтаксис, уточню, что здесь я использую трейты (traits) в качестве интерфейсов, подобных тем, что есть в языках Java или C#. Помимо классов для объектов, я также создала трейты-фабрики для порождения анонимных объектов:

сущьность для создания обьектов унаследованных от binaryOperation trait BinaryOperationFabric {    private val binaryOperationPool: ListBuffer[BinaryOperation] = new ListBuffer    def createBinary(designation: String, priority: Int, fun: (Double, Double) => Double, singleElement: Double): BinaryOperation = {      if(binaryOperationPool.contains(designation)) {       binaryOperationPool.filter(_.getDesignation == designation).head     } else {        val binary = new BinaryOperation {         override def getDesignation: String = designation          override def getPriority: Int = priority          override def calc(left: Double, right: Double): Double = fun(left, right)          override def getSingleElement: Double = singleElement       }        binaryOperationPool.append(binary)       binary      }    }    // для унарных функций и констант есть аналогичных трейты

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

trait StringCalculator {    //колекции сущьностей   private val binaryOperations: ListBuffer[BinaryOperation] = new ListBuffer[BinaryOperation]   private val unaryFunctions: ListBuffer[UnaryFunction] = new ListBuffer[UnaryFunction]   private val constants: ListBuffer[Constant] = new ListBuffer[Constant]   private val separator: String = "†" // сепаратор вспомогательный инструмент    def calculate(expression: String): Double = {     // ...   }    // методы для добавления новых сущьностей   def addBinaryOperation(binary: BinaryOperation): Unit = binaryOperations += binary   def addUnaryFunction(unary: UnaryFunction): Unit = unaryFunctions += unary   def addConstant(const: Constant): Unit = constants += const   }

Первый этап: операции без приоритета:

Разработку алгоритма начнем с малого, нужно чтобы метод справляться с выражениями по типу «1+2-3*8/8 4+1». получить их в виде списка List

val reducedExpression: String = binaryOperations.map(binary => binary.getDesignation)   .foldLeft(expression)((str, designation) => str.replace(designation.toString, s"$separator$designation$separator"))  val tokens: List[String] = expression.split(separator).toList

Для начала нужно в выражении отделить операции от чисел и получить их в виде списка Listобычный сплит по всем операциям тут не подойдет, поскольку он удалит сами операции и вместо этого я беру список всех операций и binaryOperations.map(binary => binary.getDesignation) и делаю замену всех операций на те же операции окружённые сепараторами т.е: «+» => «†+†». И таким образом для строки мы получим
«1+2-38/8*4+1» => «1†+†2†-†38†/†8†*†4†+†1» и уже split-уя мы получаем list:
List(1,+,2,, -3,*,8,/,8,*,4,+,1)

Таким образом, мы успешно разделили числа и операции друг от друга.

val numbers: List[Double] = finalTokens.filter(token => isNumeric(token)).map(token => token.toDouble) val operations: List[String] = finalTokens.filter(token => !isNumeric(token))

Правильно, чтобы выполнить операции в выражении справа налево, мы можем применять операции к двум последним числам из списка чисел, затем удалять числа и операцию, и добавлять полученное число обратно в список. Этот процесс будет повторяться до тех пор, пока в списке остаются только числа и нет операций. В результате получится одно число —
результат вычисления.

  @tailrec   private def performCalculations(numbers: List[Double], operations: List[String]): Double = {      val right: Double = numbers.last      if (operations.nonEmpty) {       operations.last match {         case x if (binaryOperations.contains(x)) =>           val res = binaryOperations.filter(op => op.equals(x)).head.calc(numbers(numbers.size - 2), right)           if (numbers.init.init.isEmpty && operations.init.isEmpty) res else performCalculations(numbers.init.init :+ res, operations.init)         case token => throw new Exception(s"$token - неизвестный токен")       }     } else {       numbers.last     }    }

Пример процесса вычисления: «1+1+1+1» => «1+1+2» => «1+3» => «4» => 4

Такой подход позволяет обрабатывать выражения справа налево, выполняя операции между последними двумя числами и обновляя список чисел после каждой операции.

Этот подход также обеспечивает гибкость для добавления новых функций, сохраняя исходное выражение в простейшем формате, чтобы можно было обрабатывать его справа налево.

Второй этап: обработка констант

Для обработки констант в выражении мы можем просто пройтись по всем токенам и заменить константы на их значения. После замены констант, выражение будет содержать только числа и операции.

val tokenWithConstant = constants.foldLeft(tokens)((acc, const) =>   acc.foldLeft(List[String]())((acc, token) => {   if (token == const.getDesignation) acc :+ const.getValue.toString else acc :+ token }))

Пример процесса обработки констант:
«e+1+pi» => «2.71+1+3.14» => «2.71+4.14» => «6.85» => 6.85

Таким образом, мы заменяем константы, такие как «e» (число Эйлера) и «pi» (число пи), на соответствующие числовые значения. Это позволяет проводить дальнейшие вычисления с использованием чисел вместо символических обозначений констант.

Третий этап: выражения в скобках

Для обработки выражений в скобках мы можем использовать рекурсивный подход. Наш подход будет заключаться в выделении подвыражения, окруженного скобками, и замене этого подвыражения, применив к нему тот же алгоритм рекурсивно. После вычисления подвыражения в скобках, мы заменяем его на полученное число и продолжаем вычисления в оставшейся части выражения.

Пример процесса обработки выражений в скобках:
«(e+pi+(12))^3» => «(e+pi+(1*2))^3» => «(e+pi+2)^3» => «(2.71+3.14+2)^3» =>
«7.85^3» => 483.736625

Для начала напишем метод, который будет выделять выражение во внешних скобках. Здесь я не буду останавливаться на деталях реализации этого метода, так как это может занять много времени. Важно заметить, что строка «separator{calculate(m.group(1))}separator» заменяет подстроку на вычисленное число.

   def replaceExpressionsWithExclamation(str: String): String = {      (separator + "(.*?)" + separator).r.replaceAllIn(str.foldLeft(("", 0)) { (acc, char) =>       val (output, bracketDepth) = acc       if (char == '(') (output + (if (bracketDepth > 0) char else separator), bracketDepth + 1)       else if (char == ')') (output + (if (bracketDepth > 1) char else separator), bracketDepth - 1)       else (output + char, bracketDepth)     }._1 , { m =>       $separator${calculate(m.group(1))}$separator     })    }

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

Если у вас возникнут вопросы или потребуется дальнейшая помощь, пожалуйста, сообщите мне.

Четвертый этап: обработка унарных функций

В контексте обработки унарных функций подразумевается функции от одной переменной, такие как cos, sin, ln, sqrt и т.д. Синтаксис таких функций выглядит, например, как «fun(…)». Важно отметить, что выражение находится внутри скобок, что означает, что оно будет заменено на число (это было реализовано на предыдущих этапах с обработкой скобок). Таким образом, замена будет выглядеть приблизительно так: «fun(…)» => «fun num».

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

val tokensUnWithBinary = tokens.reverse.foldLeft(List[String] {   tokens.last })((acc, token) => if (unaryFunctions.contains(token)) {   val num = acc.last.toDouble   acc.init :+ unaryFunctions.filter(_.getDesignation == token).head.calc(num).toString } else acc :+ token ).reverse.init.filter(_.nonEmpty)

Важно заметить, что в данном случае мы инвертируем порядок токенов и идем справа налево, чтобы обрабатывать случаи, когда унарные операции идут подряд, например, «ln(ln(ln(ln(…».

Пример процесса обработки унарных функций:

«ln(ln(1+e))+1» => «ln(ln3.71)+1» => «ln1.31+1» => «0.27 + 1» => «1.27» => 1.27

Таким образом, мы обрабатываем унарные функции, выполняя операции с числами и заменяя унарные функции на результаты операций.

Пятый этап: приоритеты

Одна из наиболее важных частей — это соблюдение приоритетов операций. Процесс довольно прост.

val minPriority = binaryOperations.map(_.getPriority).min   implicit val ordering: Ordering[BinaryOperation] = Ordering.by(1.0 / _.getPriority)   val orderedOperations = binaryOperations.toList.filter(_.getPriority != minPriority).sorted    val finalTokens = orderedOperations.foldLeft(tokensUnWithBinary)((acc, binary) => {      val indexes = tokens.zipWithIndex.filter(_._1 == binary.getDesignation).map(_._2)      indexes.sorted.foldRight(acc)((index, acc) => {        val left = tokensUnWithBinary(index - 1).toDouble        val right = tokensUnWithBinary(index + 1).toDouble        (acc.take(index - 1) :+ binary.calc(left, right).toString) ++ acc.takeRight(acc.size - index - 2)      })  })

Первое, что мы делаем, это сортируем операции в порядке убывания приоритетов. Мы создаем список orderedOperations, в который входят операции, отсортированные по приоритету. Важно отметить, что в orderedOperations не включаются операции с самым низким приоритетом, так как они уже были обработаны на предыдущих этапах.

Далее, проходя справа налево по всем токенам, мы выполняем замену в соответствии с принципом «num1*num2» => «num3». Например, путь строки «2*2^2» => «2*4» => «8» => 8.

Таким образом, мы обрабатываем операции с учетом их приоритетов и выполняем соответствующие замены, чтобы получить окончательный результат вычисления.

Завершающий этап:

В выражении могут случиться ситуации когда например «-e+» в данном случае минус тут это не сколько операция, сколько обозначение обратного элемента, отрицательного числа и с такими ситуациями так же надо справляться. Для этого в классе операции мы определили единичный элемент, то есть элемент операция с которым даст нам тот же элемент. Так
для — такой элемент — это ноль. Вся суть состоит в том что бы отыскать все бинарные операции в в унарной форме и конкатенировать с лева с их единичным элементом например: «-e» => «0-e»тогда мы все сводим к ситуации с которой уже наш калькулятор справлялся и до этого.

val fin = binaryOperations.foldLeft(tokenWithConstant)((acc, binary) => {    val indexing = acc.zipWithIndex.foldLeft(List[Int]())((acc, tokenIndex) => {     if (tokenIndex._1 == binary.getDesignation) acc :+ tokenIndex._2 else acc     })    indexing.sorted.reverse.foldLeft(acc)((acc, index) => {     if (!isNumeric(acc(index - 1))) (acc.take(index) :+ calculate(s"${binary.getSingleElement}${binary.getDesignation}" + acc(index + 1)).toString) ++ acc.takeRight(acc.size - index - 2) else acc   })  })

Заключение

Теперь калькулятор действительно обладает большой функциональностью. Он способен обрабатывать различные операции, унарные функции, константы, а также выражения в скобках с соблюдением приоритетов. Главным преимуществом моей реализации я считаю возможность пользователей настраивать функциональность калькулятора под свои потребности, добавляя необходимые им сущности. Именно потребность в такой гибкости вдохновила меня на создание данного проекта.

  printResalt("cos(-pi/2)^2 + sin(-pi/2)^2")   printResalt("lg(1 - 1/2)+lg(1 - 1/3)+lg(1 - 1/4)+lg(1 - 1/5)+lg(1 - 1/6)+lg(1 - 1/7)+lg(1 - 1/8)+lg(1 - 1/9)+lg(1 - 1/10)")   printResalt("round((tanh(-2*pi)-(e^(-2*pi)-1)/(e^(-2*pi)+1))*100)")   printResalt("round(fi^20)")    //функцияя для удобства   def printResalt(expression: String): Unit = {     println(s"$expression = ${calculate(expression)}")   }

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

P.S. Вы можете ознакомиться с проектом на GitHub

https://github.com/PicoPicoRobotWoman/string_calculator

P.P.S.

в проекте в src директории находится папка example, где продемонстрированы примеры как пользоваться калькулятором.

ссылка на оригинал статьи https://habr.com/ru/articles/747920/