|
is practically non-existent, to avoid obscuring the code.
<lang scala>package org.rosetta.arithmetic_evaluator.scala
package org.rosetta.arithmetic_evaluator.scala
object ArithmeticParser extends scala.util.parsing.combinator.RegexParsers {
sealed abstract class AST
case class Expr(term: AST, rep: List[OpChain]) extends AST
case class Literal(number: Int) extends AST
def readExpression(input: String) : Option[()=>_] = {
case class OpChain(op: Op, term: AST)
parseAll(expr, input) match {
case Success(result, _) =>
Some(result)
case other =>
println(other)
None
}
}
private type AST = ()=>Int
abstract class Op
case object Plus extends Op
case object Minus extends Op
case object Times extends Op
case object Div extends Op
private def expr : Parser[AST] =
object ArithmeticEvaluator {
(term~("+" | "-")~expr ^^ toExpr) | term
private def term : Parser[AST] =
(factor~("*" | "/")~term ^^ toExpr) | factor
private def factor : Parser[AST] =
"("~> expr <~")" | digits ^^ toLiteral | failure("Expected a value")
private def digits =
"\\d+".r
private def toLiteral(partialResult: String) =
() => partialResult.toInt
private def toExpr(partialResult: ~[~[AST, String], AST]) = {
partialResult match {
case (l~op)~r =>
op match {
case "+" => () => l() + r()
case "-" => () => l() - r()
case "*" => () => l() * r()
case "/" => () => l() / r()
case x => error("Unknown operation " + x + ".")
}
}
}
}
object Main {
def main(args: Array[String]) {
println("""Please input the expressions. Type "q" to quit.""")
var input: String = ""
do {
input = readLine("> ")
if (input != "q") {
ParserArithmeticParser.readExpression(input) map Evaluator.evaluate foreach(f => println(f()))
}
} while (input != "q")
}
}
</lang>
object Evaluator {
def evaluate(ast: AST): Int = ast match {
case Literal(number) => number
case Expr(term, rep) => rep.foldLeft(evaluate(term))(evaluateOp)
}
def evaluateOp(acc: Int, op: OpChain) = op match {
case OpChain(Plus, expr) => acc + evaluate(expr)
case OpChain(Minus, expr) => acc - evaluate(expr)
case OpChain(Times, expr) => acc * evaluate(expr)
case OpChain(Div, expr) => acc / evaluate(expr)
}
}
object Parser extends scala.util.parsing.combinator.RegexParsers {
// Evaluate expressions
def readExpression(input: String): Option[AST] = parseAll(expr, input) match {
case Success(result, _) => Some(result)
case other =>
println(other)
None
}
/* Arithmetic expression grammar production rules in EBNF form:
*
* <expr> --> <term> ( '+' <term> | '-' <term> )*
* <term> --> <factor> ( '*' <factor> | '/' <factor> )*
* <factor> --> '(' <expr> ')' | <digit>*
* <digit> --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
*/
def expr : Parser[AST] = term ~ (rep( "+" ~ term | "-" ~ term) ^^ toOpChain) ^^ toExpr
def term = factor ~ (rep( "*" ~ factor | "/" ~ factor) ^^ toOpChain) ^^ toExpr
def factor = "(" ~> expr <~ ")" | digits ^^ toLiteral | failure("Expected a number")
def digits = "\\d+".r
// Build AST
private def toLiteral(partialResult: String) = Literal(partialResult.toInt)
private def toExpr(partialResult: ~[AST,List[OpChain]]) = partialResult match {
case subexpr ~ opchain => Expr(subexpr, opchain)
}
private def toOpChain(partialResult: List[~[String,AST]]) = partialResult map {
case op ~ subexpr => OpChain(toOp(op), subexpr)
}
private def toOp(op: String): Op = op match {
case "+" => Plus
case "-" => Minus
case "*" => Times
case "/" => Div
case x => error("Unknown operation "+x+".")
}
}</lang>
Example:
|