Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import scala.util.parsing.combinator.Parsers
- import scala.util.parsing.combinator.JavaTokenParsers
- object Main
- {
- def main(args: Array[String])
- {
- val arg = "( x + 0 ) - ( 1 * --x )"
- TP2.parseAll( TP2.expression, arg ) match {
- case TP2.Success( ast, _ ) => {
- println( ast )
- println( PostfixPrinter( ast ) )
- println( new Evaluator( Map( "x" -> 2 ) )( ast ) )
- println( Simplifier( ast ) )
- }
- case TP2.NoSuccess( msg, _ ) => println( msg )
- }
- }
- }
- sealed abstract class Expression
- case class Variable( label: String ) extends Expression
- case class Number( num: Int ) extends Expression
- case class UnaryOperator( operator: String, arg: Expression ) extends Expression
- case class BinaryOperator( operator: String, left: Expression, right: Expression ) extends Expression
- object PostfixPrinter
- {
- def apply( e: Expression ): String =
- {
- e match {
- case Variable( label ) => label
- case Number( num ) => num.toString
- case UnaryOperator( operator, expression ) => apply( expression ) + operator
- case BinaryOperator( operator, left, right ) => apply( left ) + apply( right ) + operator
- }
- }
- }
- class Evaluator( idTable: Map[String, Int] )
- {
- def apply( e: Expression ): Int =
- {
- e match {
- case Variable( label ) => idTable.get( label ) match {
- case Some( value ) => value
- case None => error( label + " is not defined" )
- }
- case Number( num ) => num
- case UnaryOperator( "-", expression ) => - apply( expression )
- case BinaryOperator( "+", left, right ) => apply( left ) + apply( right )
- case BinaryOperator( "-", left, right ) => apply( left ) - apply( right )
- case BinaryOperator( "*", left, right ) => apply( left ) * apply( right )
- case BinaryOperator( "/", left, right ) => apply( left ) / apply( right )
- }
- }
- }
- object Simplifier
- {
- def apply( expression: Expression ): Expression =
- {
- case class NilExpression extends Expression
- def fixedPoint( current: Expression, last: Expression ): Expression = {
- def reduce( e: Expression ): Expression = e match {
- // Same subtraction
- case BinaryOperator( "-", x, y ) if x == y => Number( 0 )
- // Adding zero
- case BinaryOperator( "+", x, Number( 0 ) ) => x
- case BinaryOperator( "+", Number( 0 ), y ) => y
- // Multiplying by one
- case BinaryOperator( "*", x, Number( 1 ) ) => x
- case BinaryOperator( "*", Number( 1 ), y ) => y
- // Double negation
- case UnaryOperator( "-", UnaryOperator( "-", x ) ) => x
- // Recursive decent
- case BinaryOperator( op, x, y ) => BinaryOperator( op, apply( x ), apply( y ) )
- case UnaryOperator( op, x ) => UnaryOperator( op, apply( x ) )
- // Leaves
- case x: Number => x
- case x: Variable => x
- }
- if( current == last ) current
- else fixedPoint( reduce( current ), current )
- }
- fixedPoint( expression, NilExpression() )
- }
- }
- object TP2 extends JavaTokenParsers
- {
- def expression: Parser[Expression] = addExpression
- def addExpression: Parser[Expression] =
- {
- multiplicationExpression ~ ( ( ( "+" | "-" ) ~ multiplicationExpression )* ) ^^ mkBinary
- }
- def multiplicationExpression: Parser[Expression] =
- {
- unaryExpression ~ ( ( ( "*" | "/" ) ~ unaryExpression )* ) ^^ mkBinary
- }
- def unaryExpression: Parser[Expression] =
- {
- rep( "-" ) ~ basicExpression ^^ {
- case Nil ~ e => e
- case l ~ e => ( l :\ e ){ (a, b) => UnaryOperator( a, b ) }
- }
- }
- def basicExpression: Parser[ Expression ] =
- (
- ident ^^ ( id => new Variable( id ) )
- | wholeNumber ^^ ( n => new Number( n.toInt ) )
- | "(" ~> expression <~ ")" ^^ ( e => e )
- )
- def mkBinary: Expression ~ List[ String ~ Expression ] => Expression = {
- case left ~ rest => ( left /: rest ) {
- case ( l, op ~ r ) => BinaryOperator( op, l, r )
- }
- }
- }
Add Comment
Please, Sign In to add comment