/**********************************************************
  textcalc.pl
  Mike Thiesen and Anthony Arnone
  Feb 12, 2004
***********************************************************
  
  Textcalc is a simple text based calculator.
  This program can parse a simple math expression and return
  it's result. It can handle the 4 basic operations (add,
  subtract, multiply, and divide) and handles parentheses.

***********************************************************/


/*
                   __________________________________
                  /                                  \
-----------------<      S C A N N E R     C O D E     >------------------------
                  \__________________________________/

*/

/*---------------------------------------------------------------------------*\
  inNumber( Char )  
  Is true if Char is an ascii code for a digit or period.
\*---------------------------------------------------------------------------*/

inNumber( Char ) :- Char > 47, Char < 58.      % 0, 1, ... 0
inNumber( 46 ).                                % .

/*---------------------------------------------------------------------------*\
  notInNumber( Char )  
  Is false if Char is an ascii code for a digit or period.
\*---------------------------------------------------------------------------*/

notInNumber( Char ) :- Char >= 0, Char =< 45.
notInNumber( 47 ).
notInNumber( Char ) :- Char >= 58, Char < 256.

/*---------------------------------------------------------------------------*\
  toNumber( CharList, Result )
  CharList - a list of ascii codes to convert to a number
  Result - The resulting number.
\*---------------------------------------------------------------------------*/

toNumber( CharList, Result ) :-
	name( Text, CharList ),
	Result is 0 + Text.



/*---------------------------------------------------------------------------*\
  scan( Text, Result )
  Text - An atom to scan
  Result - A list of tokens
  
  scan converts an atom into a string of tokens recognized by the parser.
\*---------------------------------------------------------------------------*/

scan( Text, Result ) :-
	name( Text, CharList ),
	scanAux( CharList, Result ).



/*---------------------------------------------------------------------------*\
  scanAux( CharList, TokenList )
  CharList - the list of ascii values being scanned
  TokenList - The resulting list of tokens
  
  scanAux does the bulk of the scanning work. It acts as the dispatcher,
  taking care of simple tokens on it's own and calling other predicates for
  more complex tokens.
\*---------------------------------------------------------------------------*/

scanAux( [], [] ).

scanAux( [ 32 | Rest ], Rest_Tokens ) :-             % scan (and ignore) spaces
	scanAux( Rest, Rest_Tokens ).

scanAux( [ FirstChar | Rest ], [ Value | Rest_Tokens ] ) :-    % scan numbers
	inNumber( FirstChar ),
	scanNumber( [ FirstChar | Rest ], DigitList, UnscannedChars ),
	toNumber( DigitList, Value ),
	scanAux( UnscannedChars, Rest_Tokens ).

scanAux( [ 40 | Rest ], [ '(' | Rest_Tokens] ) :-    % scan left parentheses
	scanAux( Rest, Rest_Tokens ).
	
scanAux( [ 41 | Rest ], [ ')' | Rest_Tokens] ) :-    % scan right parentheses
	scanAux( Rest, Rest_Tokens ).
	
scanAux( [ 43 | Rest ], [ '+' | Rest_Tokens] ) :-    % scan +
	scanAux( Rest, Rest_Tokens ).
	
scanAux( [ 45 | Rest ], [ '-' | Rest_Tokens] ) :-    % scan -
	scanAux( Rest, Rest_Tokens ).
	
scanAux( [ 42 | Rest ], [ '*' | Rest_Tokens] ) :-    % scan *
	scanAux( Rest, Rest_Tokens ).
	
scanAux( [ 47 | Rest ], [ '/' | Rest_Tokens] ) :-    % scan /
	scanAux( Rest, Rest_Tokens ).

	
/*---------------------------------------------------------------------------*\

  scanNumber( CharList, DigitList, RestList )	
  CharList - The list of ascii codes to scan
  DigitList - The list of chars that are in the number
  The Rest of Charlist that wasn't scanned

  scanNumber will read a single number off of the character
  list and return the unread characters back to the scanner.

\*---------------------------------------------------------------------------*/
	
scanNumber( [], [], [] ).

scanNumber( [ FirstChar | RestChar ], [], [ FirstChar | RestChar ] ) :-
	notInNumber( FirstChar ).

scanNumber( [ FirstChar | RestChar ], [ FirstChar | RestDigits], RestList ) :-
	inNumber( FirstChar ),
	scanNumber( RestChar, RestDigits, RestList ).


/*
                   __________________________________
                  /                                  \
-----------------<      P A R S E R   C O D E         >------------------------
                  \__________________________________/

*/



/*---------------------------------------------------------------------------*\
  isOperator( Token )
  Is true if Token is an operator
\*---------------------------------------------------------------------------*/

isOperator( '+' ).
isOperator( '-' ).
isOperator( '*' ).
isOperator( '/' ).


/*---------------------------------------------------------------------------*\
  createParseTree( Root, LTree, RTree, ResultTree )
  Root - the root of the new parse tree
  LTree - the left branch of the tree
  RTree - the right branch of the tree
  ResultTree - the new tree
  
  createParseTree is used to create a new parse tree given the root, left
  and right branches.
\*---------------------------------------------------------------------------*/

createParseTree( Root, LTree, RTree, parseTree( Root, LTree, RTree ) ).


/*---------------------------------------------------------------------------*\
  precedence( Operator, Result )
  Operator - The operator to find the precedence of
  Result - The resulting precedence
\*---------------------------------------------------------------------------*/

precedence( '+', 1 ).
precedence( '-', 1 ).
precedence( '*', 2 ).
precedence( '/', 2 ).

hasLessOrEqualPrecedence( Op1, Op2 ) :-
	precedence( Op1, Op1Prec ),
	precedence( Op2, Op2Prec ),
	Op1Prec =< Op2Prec.

hasGreaterPrecedence( Op1, Op2 ) :-
	precedence( Op1, Op1Prec ),
	precedence( Op2, Op2Prec ),
	Op1Prec > Op2Prec.


/*---------------------------------------------------------------------------*\
  parseExpression( TokenList, UnparsedTokens, ResultTree )
  TokenList - a list of tokens to parse
  UnparsedTokens - if any tokens were left at the end unparsed, the are
                   returned here
  ResultTree - The resulting parse tree
  
  parseExpression will convert a list of tokens into a parse tree. It performs
  a parse from the bottom up.
  
\*---------------------------------------------------------------------------*/

     %handle a single item
parseExpression( [First|[]], [], First ).

     %handle open parenthesis
parseExpression( [ '(' | Rest], OutList, Result ) :-
	parseExpression( Rest, OutList2, ParenTree ),              %parse out to the closing paren
	parseExpression( [ parenExpression( ParenTree ) | OutList2 ], OutList, Result ). %parse the rest

     %handle close parenthesis
parseExpression( [ LeftOperand | [ ')' | Rest ]], Rest, LeftOperand ) :-
	LeftOperand \== '('.

     %handle a single value
parseExpression( [ LeftOperand | [ Operator | Rest ]], OutList, parseTree( Operator, LeftOperand, RightOperand )) :-
	leftOperand \== '(',
	isOperator( Operator ),
	parseExpression( Rest, OutList, RightOperand ),
	number( RightOperand ).

     %handle a parenthesis enclosed expression
parseExpression( [ LeftOperand | [ Operator | Rest ]],
	             OutList,
	             parseTree( Operator, LeftOperand, parenExpression( RightOperand ))) :-
	leftOperand \== '(',
	isOperator( Operator ),
	parseExpression( Rest, OutList, parenExpression( RightOperand ) ).

     %handle the case that the right tree has higher precedence
parseExpression( [ LeftOperand | [ Operator | Rest ]], 
	             OutList,
	             parseTree( Operator, LeftOperand, parseTree( RestOperator, RestLeftOperand, RestRightOperand ))) :-
	LeftOperand \== '(',
	isOperator( Operator ),
	parseExpression( Rest, OutList, parseTree( RestOperator, RestLeftOperand, RestRightOperand )),
	hasLessOrEqualPrecedence( Operator, RestOperator ).

     %handle the case that the right tree has lower precedence
parseExpression( [ LeftOperand | [ Operator | Rest ]],
                 OutList,
                 parseTree( RestOperator, parseTree( Operator, LeftOperand, RestLeftOperand), RestRightOperand )) :-
	LeftOperand \== '(',
	isOperator( Operator ),
	parseExpression( Rest, OutList, parseTree( RestOperator, RestLeftOperand, RestRightOperand )),
	hasGreaterPrecedence( Operator, RestOperator ).



/*
                   __________________________________
                  /                                  \
-----------------<    E V A L U A T O R   C O D E     >------------------------
                  \__________________________________/

*/


/*---------------------------------------------------------------------------*\
  performOperation( Operator, LeftSide, RightSide, Result )
  
  performOperation performs the specified operation on LeftSide and RightSide
  and stores the answer in Result.
\*---------------------------------------------------------------------------*/
performOperation( '+', LeftSide, RightSide, Result ) :-
	Result is LeftSide + RightSide.

performOperation( '-', LeftSide, RightSide, Result ) :-
	Result is LeftSide - RightSide.
	
performOperation( '*', LeftSide, RightSide, Result ) :-
	Result is LeftSide * RightSide.
	
performOperation( '/', LeftSide, RightSide, Result ) :-
	Result is LeftSide / RightSide.


/*---------------------------------------------------------------------------*\
  evaluateParseTree( ParseTree, Value )
  
  evaluateParseTree calculates the value of an expression parse tree and
  stores the result in Value.
\*---------------------------------------------------------------------------*/
evaluateParseTree( Value, Value ) :-
	number( Value ).

evaluateParseTree( parenExpression( ParenTree ), Value ) :-
	evaluateParseTree( ParenTree, Value ).
	
evaluateParseTree( parseTree( Value, nil, nil ), Value ) :-
	number( Value ).

evaluateParseTree( parseTree( Operator, LeftTree, RightTree ), Value ) :-
	isOperator( Operator ),
	evaluateParseTree( LeftTree, LeftValue ),
	evaluateParseTree( RightTree, RightValue ),
	performOperation( Operator, LeftValue, RightValue, Value ).

/*---------------------------------------------------------------------------*\
  evaluateExpression( Expression, Result )
  
  evaluateExpression will calculate the value of an expression and store the
  result in Result.
\*---------------------------------------------------------------------------*/
evaluateExpression( Expression, Result ) :-
	scan( Expression, TokenList ),
	parseExpression( TokenList, _, Tree ),
	evaluateParseTree( Tree, Result ).



