Гибкая обработка арифметических выражений с AST на Scala

Средний

11 мин

636

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

О каких выражениях идет речь?

Прежде чем начать обсуждать сам проект и его создание, нужно определиться с предметной областью. Под выражением понимается математическая формула, состоящая из последовательного (порядок имеет значение) набора токенов, таких как: UDO (User Defined Operator, то есть операторы), левая и правая скобки, UDF (User Defined Function или, проще говоря, функции), UDC (константы, такие как число пи, число Эйлера и т.д.), числа, запятые и пробелы.

Типичные примеры выражений:

3 + 5 * (2 - 8)
avg(4, 7) + sin(0.5)
max(3, 1, 6) - min(2, 8)

что есть обработка тогда?

Под обработкой арифметического выражения понимается преобразование (вне кода преобразование обозначим символом =>) выражения в некоторое число.

примеры преобразований:

3 + 5 * (2 - 8) => -27.0
avg(4, 7) + sin(0.5) => 5.979425538604203
max(3, 1, 6) - min(2, 8) => 4.0

требования к обработке и к выражениям

требования к выражениям следующие:

Токены выражения: Выражение должно состоять только из следующих типов токенов:
- Числа (целые числа или числа с дробной частью, разделенной точкой).
- udo (бинарные или унарные).
- udc
- Токены функций udf, которые должны следовать за открывающей скобкой, за которой следует набор выражений, разделенных запятыми, и за которыми следует закрывающая скобка.
- запятые
- левая скобка
- правая скобка
- пробел
Скобки: Количество открывающих и закрывающих скобок в выражении должно быть равным.
между двумя скобками должно находиться вырожение, либо набор вырожений через запятую в случае с udf
Формат чисел: Числа могут быть записаны в двух форматах: целые числа или числа с дробной частью, разделенной точкой (например, 1 или 1.0).
Функции UDF: После токена UDF обязательно должна идти открывающая скобка, за которой следует набор выражений, разделенных запятыми, и закрывающая скобка.
Операторы udo:
- Каждый оператор должен иметь бинарную форму, то есть быть примененным между двумя числами.
- Операторы могут также иметь унарную форму, в таком случае оператор должен иметь нулевой элемент который можно выразить числом и от оператора число находиться справа.
- операторы имеют приоритет выраженный числом либо же сущностью к которому можно применить сравнение (короче числом)

требования к обработке/преобразованию

преобразование выражения всегда происходит в число
преобразование корректно работает только с корректными выражениями (смотри требования к выражениям)
подвыражения в скобках (не относящихся к udf) имеет абсолютный приоритет
udf имеет более низкий приоритет чем подвыражения в скобках
операторы имеет еще более низкий приоритет
преобразование происходит с учетом приоритетов расставленных скобок операторов и udf

нууу, вроде ничего не забыла!

Немного про AST

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

В моем случае каждый узел AST будет хранить один из следующих токенов: UDF, UDO или число. Узел с числом не будет иметь дочерних узлов, у узла с UDF их произвольное количество, а у узла с оператором (UDO) будет два дочерних узла (независимо от того, используется ли оператор как унарный или бинарный).

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

таким образом задача построить AST которое будет соответствовать следующим принципам

каждая нода содержит токен такие как: udf, udo или число и ссылки на другие AST
AST заполнено так что от корневого к дочерним понижается приоритет токена (числа им не обладают, поэтому условно примим что он нулевой или отрицательный или как вам удобно это обозначить)
у узла с числом не может быть дочерних AST
у узла с udo их ровно два независимо от того в какой он форме используеться (унарной или бинарной [собственно для этого был выше требование выдвинуто про нулевой элемент])
у узла с udf количество c дочерними AST произвольно

Написание самого "калькулятора":

Определимся с тем, как будут выглядеть основные сущности, отражающие UDC (User-Defined Constant), UDF (User-Defined Function), UDO (User-Defined Operator).

// UDC то есть она же константа 
case class UDC(symbol: String, //обозначение констант, например pi
    		   value: Double) // и значение константы, например 3.1415

// UDF она же функция
case class UDF(symbol: String, // обозначение функции
			   fun: List[Double] => Double) // что функция делает с набором переданных параметров

// UDO или же проще говоря опретор
case class UDO(symbol: String, // его обозначение
			   precedence: Byte, // приоритет опратора 
			   zeroElem: Option[Double] = None, // нулевой элемент 
			   fun: (Double, Double) => Double) // что оператор делает с переданым параметрами

и определим набор токенов:

sealed trait Token
case class NumberToken(value: Double) extends Token
case class UDOToken(udo: UDO) extends Token
case class UDFToken(udf: UDF) extends Token
case class UDCToken(udc: UDC) extends Token
case class LeftParenthesisToken() extends Token
case class RightParenthesisToken() extends Token
case class CommaToken() extends Token

определим структуру AST:

case class AST(token: Token, subASTs: List[AST])

Остаётся лишь определить объект, который будет выполнять обработку выражений.

object AST {

	implicit class Parser(expression: String)(implicit udfs: Set[UDF] = Set.empty, udos: Set[UDO] = Set.empty, udcs: Set[UDC] = Set.empty) {

		def parseAST(): AST = ??? // метод преобразующий вырожение (String) в AST 

	}

	

	implicit class Calculator(sourceAst: AST) {
		def calc(): Double = ??? // метод преобразующий AST в число (Double)
	}

}

Давайте начнём с реализации метода parseAST. Первым шагом будет удаление всех пробелов из выражения.

val expr = expression.trim.replaceAll(" ", "")

В требованиях указано, что нужно учитывать возможность унарного использования операторов (UDO), при этом операторы всегда идут слева. Однако, поскольку для унарной формы оператора требуется наличие нулевого элемента, мы можем преобразовать все унарные UDO к их бинарной форме.

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

val updExpr = udos
				.filter(_.zeroElem.nonEmpty) // отфильтровываем все udo у которых нет нудевого элемента
				.map(op => (op.symbol, op.zeroElem.get)) // получаем только необходимое нам это символ udo и нулевой элемент
				.foldLeft(expr) { //тут мы проходимся по всем UDO и делаем замену
					case (acc, (sym, zer)) =>
						val updatedExpr = acc.replaceAllLiterally(s"($sym", s"($zer$sym") // случай когда udo после скобки
						if (updatedExpr.startsWith(sym)) s"$zer$updatedExpr" else updatedExpr // случай когда в самом начале
				}

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

Следующим шагом будет разбиение строки на список токенов.

val sep: Char = '|' //сепоратор (разделитель) понадобиться дальше
val spewSymbols: Set[String] = Set("(", ")", ",") // набор символов которые также будут в отдельные токены парситься

//все три обьекта нужны только для удобства
val udoSymbols = udos.map(_.symbol) // список всех обозначений udo
val udfSymbols = udfs.map(_.symbol) // список всех обозначений udf
val udcSymbols = udcs.map(_.symbol) // список всех обозначений udc

val parsedTokens: List[Token] = udoSymbols
    	.union(spewSymbols) // тут получаем все значения по которым будут делиться на токены
    	.foldLeft(updExpr) {
			case (acc, sym) =>
				acc.replaceAllLiterally(sym, f"$sep$sym$sep") // окружаем сепоратором
		}
        // убираем лишние сепораторы
		.replaceAllLiterally(f"$sep$sep", f"$sep") 
		.stripPrefix(sep.toString)
		.stripSuffix(sep.toString)
		.split(sep) // разделяем по сепоратору и получаем набор строк, каждый из которых надо будет соопоставить с токеном
		.filter(_.nonEmpty)
		.toList
		.map { // тут и происходит процесс соопоставления, 
			case str if Try(str.toDouble).isSuccess => NumberToken(str.toDouble)
			case str if udoSymbols.contains(str) => UDOToken(udos.find(_.symbol == str).get)
			case str if udfSymbols.contains(str) => UDFToken(udfs.find(_.symbol == str).get)
			case str if udcSymbols.contains(str) => UDCToken(udcs.find(_.symbol == str).get)
			case str if str == "(" => LeftParenthesisToken()
			case str if str == ")" => RightParenthesisToken()
			case str if str == "," => CommaToken()
			case str => throw new Exception(f"$str: нераспознаный токен")
		}
		.filter(_ != null)

Заранее предвижу критику идеи использования разделителя (sep) и разбиения по нему. Хочу отметить, что для меня это было наиболее удобным подходом, и я считаю его приемлемым. Однако, потенциальные проблемы могут возникнуть, если символ разделителя (sep) используется в определениях udc, udo или udf или если эти определения содержат только этот символ. В таком случае можно дополнить требования (которые были указаны ранее), чтобы избежать конфликтов.

Кроме того, учтем, что узлы в AST не могут содержать константы. Для упрощения обработки (и уменьшения числа возможных кейсов на один) мы можем преобразовать все токены с udc в токены с числами.

//думаю коментарии тут будут лишними
val resolvedTokens: List[Token] = parsedTokens
  .map {
	case ct: UDCToken => NumberToken(ct.udc.value)
	case token: Token => token
  }

таким образом получили все токены при этом сохранили тот порядок который необходим
и теперь надо преобразовать список токенов в AST

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

private def flattenAST(sourceTokens: List[Token])(implicit udos: Set[UDO]): AST = {
	
		def toAST(tokens: List[Token]): AST = ???

		toAST(sourceTokens)
  
	}

Для реализации функции toAST начнем с определения базового случая. Согласно принципам построения AST, узел с числом не может иметь дочерних AST, что естественным образом останавливает рекурсию. Также важно учитывать, что если с обеих сторон списка токенов есть токены левой и правой скобок, то их можно удалить, особенно учитывая требование, что между скобками должно быть выражение, что исключает пустой список токенов. Это не приведет к нарушению правил для UDF, так как требования указывают, что они могут следовать только перед левой скобкой.

def stripSurroundingTokens(tokens: List[Token]): List[Token] = tokens match {
  case Nil => Nil 
  //тут проверка можно ли убрать скобки 
  // с начала проверяется есть ли по скобке с обоих сторон 
  // и функция которая определяет есть ли в списке токенов оператор вернего уровня (то есть такой который не внутри скобок и не в в нутри функции)
  // без этой функции никак, поскольку в вырожения могут быть такими: (...)udo(...)
  // и тогда если мы уберм скобки то получчим некоректное вырожение
  // функция эта будет в следующем кодовом блоке 
  case head :: tail if head.isInstanceOf[LeftParenthesisToken] && tail.nonEmpty && tail.last.isInstanceOf[RightParenthesisToken] && findNonEnclosedOperators(tokens, udos).isEmpty =>
	tail.init
  case _ => tokens
}

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

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

def findNonEnclosedOperators(tokens: List[Token], operators: Set[UDO]): Option[Int] = {
			val sortedOperators = operators.toList.sortBy(_.precedence) // Сортируем операторы по приоритету

			// Вспомогательная функция для проверки вложенности оператора
			def isEnclosed(index: Int, tokens: List[Token]): Boolean = {
				var level = 0
				for (i <- 0 until index) {
					tokens(i) match {
						case LeftParenthesisToken() => level += 1
						case RightParenthesisToken() => level -= 1
						case _ =>
					}
				}
				level != 0
			}

			// Находим первый невложенный оператор с наименьшим приоритетом
			val nonEnclosedOperators = tokens.zipWithIndex.collect {
				case (UDOToken(op), index) if !isEnclosed(index, tokens) =>
					val opPriority = sortedOperators.indexWhere(_.symbol == op.symbol)
					(opPriority, index)
			}

			// Возвращаем индекс оператора с наименьшим приоритетом
			nonEnclosedOperators.sortBy(_._1).headOption.map(_._2)
		}

итого имеем в начале toAST:

val curTokens: List[Token] = stripSurroundingTokens(tokens)

добавим базовый случай если токен это число

curTokens match {
  case List(single: NumberToken) =>  // если распознали список с одним токеном числом
	AST(
    	single,
		Nil // вспоминаем про принцип заполнения AST где сказано что у узла с числом не может быть дочерних AST
		)
  case _ => null (пока временно)
}

таким образом остаётся еще распарсить функции и операторы
необходимо начать с операторов поскольку в требованиях они по повышению приоритета идут

findNonEnclosedOperators(curTokens, udos) match { // тут находи оператор udo вернего уровня с наименьшим приоритетом и если его нет то возращается None
  case Some(index) =>
    val (left, right) = curTokens.splitAt(index) // разбиваем на две части по индексу
    AST(
        curTokens(index),
		List(
        // вспоминаем про принцып заполения что у узла с udo два дочерних AST условно левый и правый
        // вспоминаем так же про требование к бинарным операторам udo
        toAST(left),
		toAST(right.tail)
		)
	)
  case None => тут будUет обработка udf

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

curTokens.headOption.collect {
  case udf: UDFToken => // распознаем udf
    //тут доп функция которая просто сплитует список по запятой 
	val params: List[List[Token]] = splitByNonEnclosedCommas(stripSurroundingTokens(curTokens.tail))
	AST(udf, params.map(toAST)) // вспоминаем про заполнение с узлом udf
  }.orNull

вот доп функция:

def splitByNonEnclosedCommas(tokens: List[Token]): List[List[Token]] = {
  def splitHelper(tokens: List[Token], level: Int = 0, acc: List[Token] = Nil, result: List[List[Token]] = Nil): List[List[Token]] = {
	tokens match {
      case Nil => (acc.reverse :: result).reverse
      case CommaToken() :: tail if level == 0 =>
		splitHelper(tail, level, Nil, acc.reverse :: result)
      case LeftParenthesisToken() :: tail =>
		splitHelper(tail, level + 1, LeftParenthesisToken() :: acc, result)
      case RightParenthesisToken() :: tail =>
		splitHelper(tail, level - 1, RightParenthesisToken() :: acc, result)
      case token :: tail =>
		splitHelper(tail, level, token :: acc, result)
	}
  }

  splitHelper(tokens)
}

таким образом парсинг в AST готов

остается последнее - преобразовывать AST в число о котором была речь еще в начале

def calc(): Double = {

  def ASTToDouble(ast: AST): Double = {
	ast match {
      case ast if ast.token.isInstanceOf[NumberToken] => ast.token.asInstanceOf[NumberToken].value
      case ast if ast.token.isInstanceOf[UDOToken] =>
		val fun = ast.token.asInstanceOf[UDOToken].udo.fun
		val params = ast.subASTs.map(ASTToDouble)
		fun(params.head, params.last)
  	  case ast if ast.token.isInstanceOf[UDFToken] =>
		val fun = ast.token.asInstanceOf[UDFToken].udf.fun
		val params = Try( ast.subASTs.map(ASTToDouble)).getOrElse(List.empty)
		fun(params)
    }
  }
  
  ASTToDouble(sourceAst)
}

как и говорила ранее последовательно от ветвей к корню преобразуем все AST в числа, пока не останется одно число, которое и будет ответом.

Пример использования

    // создаем udo
    val plus = UDO("+", 1, Option(0d), (left, right) => left + right)
	val minus = UDO("-", 1, Option(0d), (left, right) => left - right)
	val multiply = UDO("*", 2, Option(1d), (left, right) => left * right)
	val division = UDO("/", 2, None, (left, right) => left / right)
	val pow = UDO("^", 3, None, (left, right) => Math.pow(left, right))

    // создаем udf
	val avg = UDF("avg", params => params.sum / params.size)
	val abs = UDF("abs", params => params.head.abs)
	val cos = UDF("cos", params => Math.cos(params.head))
	val sin = UDF("sin", params => Math.sin(params.head))
	val ln = UDF("ln", params => Math.log(params.head))
	val max = UDF("max", params => params.max)
	val min = UDF("min", params => params.min)
	val ran = UDF("ran", params => Random.nextDouble())

    // создаем udc
	val pi = UDC("pi", Math.PI)
	val e = UDC("e", Math.E)

    // все наше пользовательское что нужно
	implicit val udos: Set[UDO] = Set(plus, minus, multiply, division, pow)
	implicit val udfs: Set[UDF] = Set(avg, abs, cos, sin, ln, max, min, ran)
	implicit val udcs: Set[UDC] = Set(pi, e)

    // собственно то для чего все было проделанно
	import model.AST._
	println("cos(pi/2)^2+sin((pi/2) - (-0))^2".parseAST().calc()) // 1.0
	println("avg(2, 4) * 3".parseAST().calc()) // 9.0
	println("abs(-3.5) + ln(e)".parseAST().calc()) // 4.5
	println("max(1, 3, 2) - min(5, 3, 4)".parseAST().calc()) // 0.0
	println("2^3 + ran()".parseAST().calc()) // 8 + random value between 0 and 1
	println("cos(0) + sin(pi/2)".parseAST().calc()) // 1.0

Заключение или типа того

В итоге, мы разработали и реализовали механизм обработки арифметических выражений с использованием AST в языке программирования Scala. AST (Abstract Syntax Tree) позволяет нам структурировать и анализировать синтаксическую структуру математических формул, составленных из операторов, функций и констант. Процесс разработки включал учет различных случаев использования операторов, функций и констант, а также обеспечение правильного порядка выполнения операций с учетом приоритетов. Использование AST упрощает работу с выражениями, делая их более структурированными и поддерживаемыми в рамках компиляции и интерпретации программного кода.

P.S. код можно глянуть тут

Теги:

Хабы:

Гибкая обработка арифметических выражений с AST на Scala

О каких выражениях идет речь?

требования к обработке и к выражениям

Немного про AST

Написание самого "калькулятора":

Пример использования

Заключение или типа того

Публикации

Истории

Работа

Ближайшие события