算术表达式语法和解析器

最近我正在寻找算术表达式的体面语法，但只发现了一些不重要的语法，例如忽略pow(..., ...)。然后我自己试了一下，但有时它并没有像预期的那样工作。例如，我错过了允许表达式前面的一个单一的-并修复它。也许有人可以看看我目前的做法并改进它。此外，我认为其他人可以利用，因为解析算术表达式是一项常见任务。算术表达式语法和解析器

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 
}

所以可以评价如下：

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

任何改进的建议？我是否使用正确的语法，还是只有用户输入一个有效的（关于我提供的函数）算术表达式才能解析的时间问题？
（运算符优先级What's？）

来源

2011-04-27 Peter Schmitz

例如：以'E'开头的userFct会产生一个分析错误，因为'math.E'之前是匹配的。我怎样才能防止这种情况发生，或者如何将'Parser [Double]'与'|'结合起来才是正确的优先级？ – 2011-04-27 17:01:17

这段代码相当不错@Peter Schmitz。你应该把它放在Github的一个图书馆，然后我可以给你我的修改。我使用它作为我正在开发的项目的起点。 – Jason 2013-07-15 19:55:29

@Jason谢谢。如果时间允许，我会在Github上发布它，但你可以自由地使用你的改进并使用我的代码。我期待看到改进，因为我仍然在问自己语法是否正确。 – 2013-07-16 11:53:04

为了更好的表现，我建议定义分析器时使用private lazy val，而不是private def。否则，只要解析器是引用，它就会再次创建。

不错的代码BTW。

来源

2011-04-27 14:49:17

你是对的，谢谢。我在编码时尝试了它，但在几个输入上运行解析器时没有奏效。我猜想解析器只能使用一次，所以我选择了类似于Scala书籍中的编程。现在它可以用'lazy val'工作。 – 2011-04-27 14:56:09

嗯，也许在循环中添加变量：

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 
}

所以，现在你必须通过地图来评价，你可以这样做：

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))

正如你所看到的，我还添加参数添加一元和二元函数。

感谢您的代码！

来源

2014-12-05 18:14:02

算术表达式语法和解析器

回答

相关问题