Gramática de expresiones aritméticas y Analizador

Question

Recientemente estaba buscando una gramática decente para expresiones aritméticas pero encontré solo triviales, ignorando pow(..., ...) por ejemplo. Luego lo intenté por mi cuenta, pero a veces no funcionó como uno espera. Por ejemplo, fallé para permitir unario - frente a las expresiones y lo solucioné. Quizás alguien pueda echar un vistazo a mi enfoque actual y mejorarlo. Además, creo que otros pueden aprovechar porque es una tarea común poder analizar expresiones aritméticas.

import scala.math._ 
import scala.util.parsing.combinator._ 
import scala.util.Random 

class FormulaParser(val constants: Map[String,Double] = Map(), val userFcts: Map[String,String => Double] = Map(), random: Random = new Random) extends JavaTokenParsers { 
    require(constants.keySet.intersect(userFcts.keySet).isEmpty) 
    private val allConstants = constants ++ Map("E" -> E, "PI" -> Pi, "Pi" -> Pi) // shouldn´t be empty 
    private val unaryOps: Map[String,Double => Double] = Map(
    "sqrt" -> (sqrt(_)), "abs" -> (abs(_)), "floor" -> (floor(_)), "ceil" -> (ceil(_)), "ln" -> (math.log(_)), "round" -> (round(_)), "signum" -> (signum(_)) 
) 
    private val binaryOps1: Map[String,(Double,Double) => Double] = Map(
    "+" -> (_+_), "-" -> (_-_), "*" -> (_*_), "/" -> (_/_), "^" -> (pow(_,_)) 
) 
    private val binaryOps2: Map[String,(Double,Double) => Double] = Map(
    "max" -> (max(_,_)), "min" -> (min(_,_)) 
) 
    private def fold(d: Double, l: List[~[String,Double]]) = l.foldLeft(d){ case (d1,op~d2) => binaryOps1(op)(d1,d2) } 
    private implicit def map2Parser[V](m: Map[String,V]) = m.keys.map(_ ^^ (identity)).reduceLeft(_ | _) 
    private def expression: Parser[Double] = sign~term~rep(("+"|"-")~term) ^^ { case s~t~l => fold(s * t,l) } 
    private def sign:  Parser[Double] = opt("+" | "-") ^^ { case None => 1; case Some("+") => 1; case Some("-") => -1 } 
    private def term:  Parser[Double] = longFactor~rep(("*"|"/")~longFactor) ^^ { case d~l => fold(d,l) } 
    private def longFactor: Parser[Double] = shortFactor~rep("^"~shortFactor) ^^ { case d~l => fold(d,l) } 
    private def shortFactor: Parser[Double] = fpn | sign~(constant | rnd | unaryFct | binaryFct | userFct | "("~>expression<~")") ^^ { case s~x => s * x } 
    private def constant: Parser[Double] = allConstants ^^ (allConstants(_)) 
    private def rnd:   Parser[Double] = "rnd"~>"("~>fpn~","~fpn<~")" ^^ { case x~_~y => require(y > x); x + (y-x) * random.nextDouble } | "rnd" ^^ { _ => random.nextDouble } 
    private def fpn:   Parser[Double] = floatingPointNumber ^^ (_.toDouble) 
    private def unaryFct: Parser[Double] = unaryOps~"("~expression~")" ^^ { case op~_~d~_ => unaryOps(op)(d) } 
    private def binaryFct: Parser[Double] = binaryOps2~"("~expression~","~expression~")" ^^ { case op~_~d1~_~d2~_ => binaryOps2(op)(d1,d2) } 
    private def userFct:  Parser[Double] = userFcts~"("~(expression ^^ (_.toString) | ident)<~")" ^^ { case fct~_~x => userFcts(fct)(x) } 
    def evaluate(formula: String) = parseAll(expression,formula).get 
} 

Así se puede evaluar los siguientes:

val formulaParser = new FormulaParser(
    constants = Map("radius" -> 8D, 
        "height" -> 10D, 
        "c" -> 299792458, // m/s 
        "v" -> 130 * 1000/60/60, // 130 km/h in m/s 
        "m" -> 80), 
    userFcts = Map("perimeter" -> { _.toDouble * 2 * Pi })) 

println(formulaParser.evaluate("2+3*5")) // 17.0 
println(formulaParser.evaluate("height*perimeter(radius)")) // 502.6548245743669 
println(formulaParser.evaluate("m/sqrt(1-v^2/c^2)")) // 80.00000000003415 

Cualquier sugerencia de mejora? ¿Utilizo la gramática correcta o solo es cuestión de tiempo hasta que el usuario escriba una expresión aritmética válida (con respecto a las funciones proporcionadas) que no se pueda analizar?
(Cómo sobre la precedencia de operadores?)

Answer 1

Para un mejor rendimiento mejor utilizar private lazy val en lugar de private def la hora de definir programas de análisis. De lo contrario, cada vez que un analizador es referencias, se crea de nuevo.

Bonito código BTW.

Answer 2

Bueno, tal vez añadir las variables en el bucle:

import scala.math._ 
import scala.util.parsing.combinator._ 
import scala.util.Random 

class FormulaParser(val variables: Set[String] = Set(), 
        val constants: Map[String, Double] = Map(), 
        val unary: Map[String, Double => Double] = Map(), 
        val binary: Map[String, (Double, Double) => Double] = Map(), 
        val userFcts: Map[String, String => Double] = Map(), 
        random: Random = new Random) extends JavaTokenParsers { 
    require(constants.keySet.intersect(userFcts.keySet).isEmpty) 
    private val allConstants = constants ++ Map("E" -> E, "PI" -> Pi, "Pi" -> Pi) 
    // shouldn´t be empty 
    private val unaryOps = Map[String, Double => Double](
    "sqrt" -> (sqrt(_)), "abs" -> (abs(_)), "floor" -> (floor(_)), "ceil" -> (ceil(_)), "ln" -> (math.log(_)), "round" -> (round(_).toDouble), "signum" -> (signum(_)) 
    ) ++ unary 
    private val binaryOps1 = Map[String, (Double, Double) => Double](
     "+" -> (_ + _), "-" -> (_ - _), "*" -> (_ * _), "/" -> (_/_), "^" -> (pow(_, _)) 
    ) 
    private val binaryOps2 = Map[String, (Double, Double) => Double](
     "max" -> (max(_, _)), "min" -> (min(_, _)) 
    ) ++ binary 

    type Argument = Map[String, Double] 
    type Formula = Argument => Double 

    private def fold(d: Formula, l: List[~[String, Formula]]) = l.foldLeft(d) { case (d1, op ~ d2) => arg => binaryOps1(op)(d1(arg), d2(arg))} 
    private implicit def set2Parser[V](s: Set[String]) = s.map(_ ^^ identity).reduceLeft(_ | _) 
    private implicit def map2Parser[V](m: Map[String, V]) = m.keys.map(_ ^^ identity).reduceLeft(_ | _) 
    private def expression: Parser[Formula] = sign ~ term ~ rep(("+" | "-") ~ term) ^^ { case s ~ t ~ l => fold(arg => s * t(arg), l)} 
    private def sign: Parser[Double] = opt("+" | "-") ^^ { case None => 1; case Some("+") => 1; case Some("-") => -1} 
    private def term: Parser[Formula] = longFactor ~ rep(("*" | "/") ~ longFactor) ^^ { case d ~ l => fold(d, l)} 
    private def longFactor: Parser[Formula] = shortFactor ~ rep("^" ~ shortFactor) ^^ { case d ~ l => fold(d, l)} 
    private def shortFactor: Parser[Formula] = fpn | sign ~ (constant | variable | rnd | unaryFct | binaryFct | userFct | "(" ~> expression <~ ")") ^^ { case s ~ x => arg => s * x(arg)} 
    private def constant: Parser[Formula] = allConstants ^^ (name => arg => allConstants(name)) 
    private def variable: Parser[Formula] = variables ^^ (name => arg => arg(name)) 
    private def rnd: Parser[Formula] = "rnd" ~> "(" ~> fpn ~ "," ~ fpn <~ ")" ^^ { case x ~ _ ~ y => (arg: Argument) => require(y(arg) > x(arg)); x(arg) + (y(arg) - x(arg)) * random.nextDouble} | "rnd" ^^ { _ => arg => random.nextDouble} 
    private def fpn: Parser[Formula] = floatingPointNumber ^^ (value => arg => value.toDouble) 
    private def unaryFct: Parser[Formula] = unaryOps ~ "(" ~ expression ~ ")" ^^ { case op ~ _ ~ d ~ _ => arg => unaryOps(op)(d(arg))} 
    private def binaryFct: Parser[Formula] = binaryOps2 ~ "(" ~ expression ~ "," ~ expression ~ ")" ^^ { case op ~ _ ~ d1 ~ _ ~ d2 ~ _ => arg => binaryOps2(op)(d1(arg), d2(arg))} 
    private def userFct: Parser[Formula] = userFcts ~ "(" ~ (expression ^^ (_.toString) | ident) <~ ")" ^^ { case fct ~ _ ~ x => arg => userFcts(fct)(x)} 
    def evaluate(formula: String) = parseAll(expression, formula).get 
} 

Así que ahora usted tiene que pasar un mapa de evaluar y que puede hacer:

val formulaParser = new FormulaParser(Set("x"), unary = Map(
    "sin" -> (math.sin(_)), "cos" -> (math.cos(_)), "tan" -> (math.tan(_)) 
)) 
val formula = formulaParser.evaluate("sin(x)^x") 
val function: Double => Double = x => formula(Map("x" -> x)) 
println(function(5.5)) 

parámetros Como se puede ver, yo también agregó para agregar funciones unarias y binarias.

¡Gracias por ese buen código por cierto!