PicoPicoRobotWoman 13 июл 2023 в 21:21

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

Средний

10 мин

2.9K

Алгоритмы*Scala*Математика*Функциональное программирование*

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

Перед тем, как мы начнем обсуждать создание строкового калькулятора, давайте определимся, что это такое. Строковый калькулятор (далее просто "калькулятор") - это алгоритм или программа, которая преобразует арифметическое выражение, представленное в виде строки (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, где продемонстрированы примеры как пользоваться калькулятором.

Теги:

Хабы: