LOG3210 - TP2

tp2.scala

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