/*
Tokenize -- handle spaces and multi-digit integers
*/

DIGITS = explode( "0123456789" );
allDigits( s ) => is_string(s) ? allDigits( explode(s) );
allDigits( CL ) => all( (c)=>member(c,DIGITS), CL );

// not really needed
LETTERS = explode( "abcdefghijklmnopqrstuvwxyz_!@#$%&" );
allLetters( CL ) => all( (c)=>member(c,LETTERS), CL );

// these are needed
OTHERTOKENS = map( explode, ["+", "-", "=", "*", "/", "^", "(", ")"] );
otherToken( CL ) => member( CL, OTHERTOKENS );

// all tokens
validToken( CL ) => allDigits( CL ) || allLetters( CL ) || otherToken( CL );

// the tokenizer
tokenize( s ) => is_string(s) ? tokenize( explode(s) );
tokenize( [] ) => [];
tokenize( [' '|R] ) => tokenize( R );
tokenize( CL ) => RevOfCL = reverse( CL ),
                  [FirstCL, NextCL] = getToken( RevOfCL, [] ),
                  [ implode( reverse( FirstCL ) ) | tokenize( NextCL ) ];

// gets the largest next token
getToken( [], NextCL ) => [ [], NextCL ];
getToken( [f|R], NextCL ) => validToken( [f|R] ) ? 
                               [ [f|R], NextCL ] : 
                               getToken( R, [f|NextCL] );



/* 
 * parse ~ returns a pair
 *
 *    [ PT, Res ]
 *
 * PT is the parse tree so far
 *
 * Res is the "residue" or all the tokens not yet handled...
 */
parse( TL ) => S( TL );

// S
S( TL ) => [ PT, [op|R] ] = P(TL), (op == "+" || op == "-") ?
           [ RPT, R2 ] = S(R),
           [ [op, PT, RPT], R2 ];

S( TL ) => [ PT, R ] = P(TL), [ PT, R ]; 


P( TL ) => [ PT, [op|R] ] = E(TL), (op == "*" || op == "/") ?
           [ RPT, R2 ] = P(R),
           [ [op, PT, RPT], R2 ];

P( TL ) => [ PT, R ] = E(TL), [ PT, R ];

// exponentiation
E( TL ) => [ PT, [op|R] ] = U(TL), (op == "^") ?
           [ RPT, R2 ] = E(R),
           [ [op, PT, RPT], R2 ];

E( TL ) => [ PT, R ] = U(TL), [ PT, R ];


// parentheses and negation
U( ["("|RTL] ) => [ PT, Res ] = S(RTL), 
                  (Res == [] || first(Res) != ")" ) 
                     ?  [ PT, ["missing right paren"|Res] ]
                     :  [ PT, rest(Res) ];
// handle negation
U( ["-"|RTL] ) => [ PT, Res ] = V(RTL),
                  [ ["-", PT], Res ];
// otherwise, send it to V
U( TL ) => V(TL);


           
// V - almost fully provided (only handles single-digits
// in the starting file
V( [] ) => [ "Error", ["missing_V"] ];
V( ["answer"|R] ) => [ "42", R ];
V( [f|R] ) => allDigits( f ) ? [ f, R ];
V( [f|R] ) => [ "Error", [ concat("bad_v_token: ",f," :end") | R] ];


/*
 * Evaluate
 */


Evaluate( ["+", L, R] ) => Evaluate( L ) + Evaluate( R );
Evaluate( ["-", L, R] ) => Evaluate( L ) - Evaluate( R );
Evaluate( ["-", L] ) =>  - Evaluate( L );
Evaluate( ["*", L, R] ) => Evaluate( L ) * Evaluate( R );
Evaluate( ["/", L, R] ) => Evaluate( L ) / Evaluate( R );
Evaluate( ["^", L, R] ) => pow( Evaluate( L ) , Evaluate( R ) );
Evaluate( x ) => is_string(x) ? make_number(x);
Evaluate( AnythingElse ) => Message = 
            print("I don't understand", AnythingElse, "\n\n"),
                            AnythingElse;


test( tokenize( "1+2" ),  [ "1", "+", "2" ] );
test( tokenize( "1 +   2" ),  [ "1", "+", "2" ] );
test( tokenize( "11+31^1" ),  [ "11", "+", "31", "^", "1" ] );
test( tokenize( "11   +31 ^1" ),  [ "11", "+", "31", "^", "1" ] );
test( tokenize( "(11+-31)^1" ),  [ "(", "11", "+", "-", "31", ")", "^", "1" ] );
test( tokenize( "( 11   +-31) ^1" ),  [ "(", "11", "+", "-", "31", ")", "^", "1" ] );

// note that spaces and multi-digit integers are not
// used in these tests, but they will be when graded

// addition and subtraction
test( parse( [ "1" ] ),  [ "1", [] ] );
test( parse( [ "1", "+", "2" ] ),  [ ["+", "1", "2"], [] ] );
test( parse( [ "1", "+", "2", "+", "3" ] ),  [ ["+", "1", ["+", "2", "3"]], [] ] );
test( parse( [ "1", "-", "2" ] ),  [ ["-", "1", "2"], [] ] );
test( parse( [ "1", "-", "2", "-", "3" ] ),  [ ["-", "1", ["-", "2", "3"]], [] ] );


// multiplication and division
test( parse( [ "1", "*", "2", "+", "3" ] ),  [ ["+", ["*", "1", "2"], "3"], [] ] );
test( parse( [ "1", "*", "2", "*", "3" ] ),  [ ["*", "1", ["*", "2", "3"]], [] ] );
test( parse( [ "8", "/", "2", "+", "3" ] ),  [ ["+", ["/", "8", "2"], "3"], [] ] );
test( parse( [ "6", "/", "4", "/", "2" ] ),  [ ["/", "6", ["/", "4", "2"]], [] ] );

// exponentiation
test( parse( [ "1", "*", "2", "^", "5", "+", "3" ] ),  [ ["+", ["*", "1", ["^", "2", "5"]], "3"], [] ] );
test( parse( [ "2", "+", "3", "^", "2" ] ),  [ ["+", "2", ["^", "3", "2"]], [] ] );

// parentheses and negation
test( parse( [ "(", "1", ")" ] ),  [ "1", [] ] );
test( parse( [ "(", "1", "*", "2", ")", "^", "(", "5", "+", "3", ")" ] ),  [ ["^", ["*", "1", "2"], ["+", "5", "3"]], [] ] );
test( parse( [ "(", "2", "+", "3", ")", "^", "2" ] ),  [ ["^", ["+", "2", "3"], "2"], [] ] );
test( parse( [ "-", "1" ] ),  [ ["-", "1"], [] ] );
test( parse( [ "-", "1", "+", "2" ] ),  [ ["+", ["-", "1"], "2"], [] ] );
test( parse( [ "1", "+", "2", "+", "-", "3" ] ),  [ ["+", "1", ["+", "2", ["-", "3"]]], [] ] );


// tests of Evaluate

// addition and subtraction
test( Evaluate( "1" ),  1 );
test( Evaluate( ["+", "1", "2"] ),  3 );
test( Evaluate( ["+", "1", ["+", "2", "3"]] ),  6 );
test( Evaluate( ["-", "1", "2"] ),  -1 );
test( Evaluate( ["-", "1", ["-", "2", "3"]] ),  2 );


// multiplication and division
test( Evaluate( ["+", ["*", "1", "2"], "3"] ),  5 );
test( Evaluate( ["*", "1", ["*", "2", "3"]] ),  6 );
test( Evaluate( ["+", ["/", "8", "2"], "3"] ),  7 );
test( Evaluate( ["/", "6", ["/", "4", "2"]] ),  3 );

// exponentiation
test( Evaluate( ["+", ["*", "1", ["^", "2", "5"]], "3"] ),  35 );
test( Evaluate( ["+", "2", ["^", "3", "2"]] ),  11 );

// parentheses and negation
test( Evaluate( "1" ),  1 );
test( Evaluate( ["^", ["*", "1", "2"], ["+", "5", "3"]] ),  256 );
test( Evaluate( ["^", ["+", "2", "3"], "2"] ),  25 );
test( Evaluate( ["-", "1"] ),  -1 );
test( Evaluate( ["+", ["-", "1"], "2"] ),  1 );
test( Evaluate( ["+", "1", ["+", "2", ["-", "3"]]] ),  0 );


// some shortcuts, as well:
doT( s ) => tokenize( s );

doP( s ) => TL = tokenize(s),
            x = print("\nTokens\n", TL, "\n\n"),
            x = print("ParseTree\n"),
            parse( TL );

doE( s ) => whatis(s); //Evaluate( first( parse(tokenize(s)) ) );

// combining tokenize, parse, and Evaluate
// note that you can print (but need to bind it to a dummy variable)
whatis( s ) => TL = tokenize( s ),
               x = print( "\nTokens\n", TL, "\n\n" ),  
               [ PT, Residue ] = parse( TL ),
               x = print( "Parse tree\n", PT, "\n\n",     
                          "Residue\n", Residue, "\n\n" ),

               // was there an error?
               Residue != [] ?
               "No value ~ error in parsing" :

               x = print("Evaluated to\n"),

               // if no error, go ahead and Evaluate
               value = Evaluate( PT ),
               value;