/*! KAS | https://github.com/Khan/KAS */
// This is a @generated file
window.KAS = {};
(function(KAS) {

/* parser generated by jison 0.4.13 */
/*
  Returns a Parser object of the following structure:

  Parser: {
    yy: {}
  }

  Parser.prototype: {
    yy: {},
    trace: function(),
    symbols_: {associative list: name ==> number},
    terminals_: {associative list: number ==> name},
    productions_: [...],
    performAction: function anonymous(yytext, yyleng, yylineno, yy, yystate, $$, _$),
    table: [...],
    defaultActions: {...},
    parseError: function(str, hash),
    parse: function(input),

    lexer: {
        EOF: 1,
        parseError: function(str, hash),
        setInput: function(input),
        input: function(),
        unput: function(str),
        more: function(),
        less: function(n),
        pastInput: function(),
        upcomingInput: function(),
        showPosition: function(),
        test_match: function(regex_match_array, rule_index),
        next: function(),
        lex: function(),
        begin: function(condition),
        popState: function(),
        _currentRules: function(),
        topState: function(),
        pushState: function(condition),

        options: {
            ranges: boolean           (optional: true ==> token location info will include a .range[] member)
            flex: boolean             (optional: true ==> flex-like lexing behaviour where the rules are tested exhaustively to find the longest match)
            backtrack_lexer: boolean  (optional: true ==> lexer regexes are tested in order and for each matching regex the action code is invoked; the lexer terminates the scan when a token is returned by the action code)
        },

        performAction: function(yy, yy_, $avoiding_name_collisions, YY_START),
        rules: [...],
        conditions: {associative list: name ==> set},
    }
  }


  token location info (@$, _$, etc.): {
    first_line: n,
    last_line: n,
    first_column: n,
    last_column: n,
    range: [start_number, end_number]       (where the numbers are indexes into the input string, regular zero-based)
  }


  the parseError function receives a 'hash' object with these members for lexer and parser errors: {
    text:        (matched text)
    token:       (the produced terminal token, if any)
    line:        (yylineno)
  }
  while parser (grammar) errors will also provide these members, i.e. parser errors deliver a superset of attributes: {
    loc:         (yylloc)
    expected:    (string describing the set of expected tokens)
    recoverable: (boolean: TRUE when the parser has a error recovery rule available for this particular error)
  }
*/
var parser = (function(){
var parser = {trace: function trace() { },
yy: {},
symbols_: {"error":2,"equation":3,"expression":4,"SIGN":5,"EOF":6,"additive":7,"+":8,"multiplicative":9,"-":10,"triglog":11,"*":12,"negative":13,"/":14,"trig":15,"TRIG":16,"trigfunc":17,"^":18,"TRIGINV":19,"logbase":20,"ln":21,"log":22,"_":23,"subscriptable":24,"power":25,"primitive":26,"variable":27,"VAR":28,"CONST":29,"INT":30,"FLOAT":31,"{":32,"}":33,"(":34,")":35,"function":36,"FUNC":37,"invocation":38,"sqrt":39,"abs":40,"|":41,"LEFT|":42,"RIGHT|":43,"FRAC":44,"$accept":0,"$end":1},
terminals_: {2:"error",5:"SIGN",6:"EOF",8:"+",10:"-",12:"*",14:"/",16:"TRIG",18:"^",19:"TRIGINV",21:"ln",22:"log",23:"_",28:"VAR",29:"CONST",30:"INT",31:"FLOAT",32:"{",33:"}",34:"(",35:")",37:"FUNC",39:"sqrt",40:"abs",41:"|",42:"LEFT|",43:"RIGHT|",44:"FRAC"},
productions_: [0,[3,4],[3,2],[3,1],[4,1],[7,3],[7,3],[7,1],[9,2],[9,3],[9,3],[9,1],[13,2],[13,1],[15,1],[17,1],[17,3],[17,1],[20,1],[20,1],[20,3],[11,2],[11,2],[11,1],[25,3],[25,1],[27,1],[24,3],[24,1],[24,1],[24,1],[24,1],[24,3],[24,3],[36,1],[38,4],[38,4],[38,4],[38,3],[38,3],[38,4],[26,1],[26,1],[26,7]],
performAction: function anonymous(yytext, yyleng, yylineno, yy, yystate /* action[1] */, $$ /* vstack */, _$ /* lstack */) {
/* this == yyval */

var $0 = $$.length - 1;
switch (yystate) {
case 1:return new yy.Eq($$[$0-3], $$[$0-2], $$[$0-1]);
break;
case 2:return $$[$0-1];
break;
case 3:return new yy.Add([]);
break;
case 4:this.$ = $$[$0];
break;
case 5:this.$ = yy.Add.createOrAppend($$[$0-2], $$[$0]);
break;
case 6:this.$ = yy.Add.createOrAppend($$[$0-2], yy.Mul.handleNegative($$[$0], "subtract"));
break;
case 7:this.$ = $$[$0];
break;
case 8:this.$ = yy.Mul.fold(yy.Mul.createOrAppend($$[$0-1], $$[$0]));
break;
case 9:this.$ = yy.Mul.fold(yy.Mul.createOrAppend($$[$0-2], $$[$0]));
break;
case 10:this.$ = yy.Mul.fold(yy.Mul.handleDivide($$[$0-2], $$[$0]));
break;
case 11:this.$ = $$[$0];
break;
case 12:this.$ = yy.Mul.handleNegative($$[$0]);
break;
case 13:this.$ = $$[$0];
break;
case 14:this.$ = [yytext];
break;
case 15:this.$ = $$[$0];
break;
case 16:this.$ = $$[$0-2].concat($$[$0]);
break;
case 17:this.$ = [yytext];
break;
case 18:this.$ = yy.Log.natural();
break;
case 19:this.$ = yy.Log.common();
break;
case 20:this.$ = $$[$0];
break;
case 21:this.$ = yy.Trig.create($$[$0-1], $$[$0]);
break;
case 22:this.$ = yy.Log.create($$[$0-1], $$[$0]);
break;
case 23:this.$ = $$[$0];
break;
case 24:this.$ = new yy.Pow($$[$0-2], $$[$0]);
break;
case 25:this.$ = $$[$0];
break;
case 26:this.$ = yytext;
break;
case 27:this.$ = new yy.Var($$[$0-2], $$[$0]);
break;
case 28:this.$ = new yy.Var($$[$0]);
break;
case 29:this.$ = new yy.Const(yytext.toLowerCase());
break;
case 30:this.$ = yy.Int.create(Number(yytext));
break;
case 31:this.$ = yy.Float.create(Number(yytext));
break;
case 32:this.$ = $$[$0-1].completeParse();
break;
case 33:this.$ = $$[$0-1].completeParse().addHint('parens');
break;
case 34:this.$ = yytext;
break;
case 35:this.$ = yy.Pow.sqrt($$[$0-1]);
break;
case 36:this.$ = yy.Pow.sqrt($$[$0-1]);
break;
case 37:this.$ = new yy.Abs($$[$0-1]);
break;
case 38:this.$ = new yy.Abs($$[$0-1]);
break;
case 39:this.$ = new yy.Abs($$[$0-1]);
break;
case 40:this.$ = new yy.Func($$[$0-3], $$[$0-1]);
break;
case 41:this.$ = $$[$0];
break;
case 42:this.$ = $$[$0];
break;
case 43:this.$ = yy.Mul.fold(yy.Mul.handleDivide($$[$0-4], $$[$0-1]));
break;
}
},
table: [{3:1,4:2,6:[1,3],7:4,9:5,10:[1,7],11:8,13:6,15:12,16:[1,17],17:9,19:[1,13],20:10,21:[1,14],22:[1,15],24:18,25:11,26:16,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],34:[1,26],36:31,37:[1,33],38:19,39:[1,27],40:[1,28],41:[1,29],42:[1,30],44:[1,20]},{1:[3]},{5:[1,34],6:[1,35]},{1:[2,3]},{5:[2,4],6:[2,4],8:[1,36],10:[1,37]},{5:[2,7],6:[2,7],8:[2,7],10:[2,7],11:38,12:[1,39],14:[1,40],15:12,16:[1,17],17:9,19:[1,13],20:10,21:[1,14],22:[1,15],24:18,25:11,26:16,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],33:[2,7],34:[1,26],35:[2,7],36:31,37:[1,33],38:19,39:[1,27],40:[1,28],41:[2,7],42:[1,30],43:[2,7],44:[1,20]},{5:[2,11],6:[2,11],8:[2,11],10:[2,11],12:[2,11],14:[2,11],16:[2,11],19:[2,11],21:[2,11],22:[2,11],28:[2,11],29:[2,11],30:[2,11],31:[2,11],32:[2,11],33:[2,11],34:[2,11],35:[2,11],37:[2,11],39:[2,11],40:[2,11],41:[2,11],42:[2,11],43:[2,11],44:[2,11]},{10:[1,7],11:8,13:41,15:12,16:[1,17],17:9,19:[1,13],20:10,21:[1,14],22:[1,15],24:18,25:11,26:16,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],34:[1,26],36:31,37:[1,33],38:19,39:[1,27],40:[1,28],41:[1,29],42:[1,30],44:[1,20]},{5:[2,13],6:[2,13],8:[2,13],10:[2,13],12:[2,13],14:[2,13],16:[2,13],19:[2,13],21:[2,13],22:[2,13],28:[2,13],29:[2,13],30:[2,13],31:[2,13],32:[2,13],33:[2,13],34:[2,13],35:[2,13],37:[2,13],39:[2,13],40:[2,13],41:[2,13],42:[2,13],43:[2,13],44:[2,13]},{10:[1,7],11:8,13:42,15:12,16:[1,17],17:9,19:[1,13],20:10,21:[1,14],22:[1,15],24:18,25:11,26:16,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],34:[1,26],36:31,37:[1,33],38:19,39:[1,27],40:[1,28],41:[1,29],42:[1,30],44:[1,20]},{10:[1,7],11:8,13:43,15:12,16:[1,17],17:9,19:[1,13],20:10,21:[1,14],22:[1,15],24:18,25:11,26:16,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],34:[1,26],36:31,37:[1,33],38:19,39:[1,27],40:[1,28],41:[1,29],42:[1,30],44:[1,20]},{5:[2,23],6:[2,23],8:[2,23],10:[2,23],12:[2,23],14:[2,23],16:[2,23],19:[2,23],21:[2,23],22:[2,23],28:[2,23],29:[2,23],30:[2,23],31:[2,23],32:[2,23],33:[2,23],34:[2,23],35:[2,23],37:[2,23],39:[2,23],40:[2,23],41:[2,23],42:[2,23],43:[2,23],44:[2,23]},{10:[2,15],16:[2,15],18:[1,44],19:[2,15],21:[2,15],22:[2,15],28:[2,15],29:[2,15],30:[2,15],31:[2,15],32:[2,15],34:[2,15],37:[2,15],39:[2,15],40:[2,15],41:[2,15],42:[2,15],44:[2,15]},{10:[2,17],16:[2,17],19:[2,17],21:[2,17],22:[2,17],28:[2,17],29:[2,17],30:[2,17],31:[2,17],32:[2,17],34:[2,17],37:[2,17],39:[2,17],40:[2,17],41:[2,17],42:[2,17],44:[2,17]},{10:[2,18],16:[2,18],19:[2,18],21:[2,18],22:[2,18],28:[2,18],29:[2,18],30:[2,18],31:[2,18],32:[2,18],34:[2,18],37:[2,18],39:[2,18],40:[2,18],41:[2,18],42:[2,18],44:[2,18]},{10:[2,19],16:[2,19],19:[2,19],21:[2,19],22:[2,19],23:[1,45],28:[2,19],29:[2,19],30:[2,19],31:[2,19],32:[2,19],34:[2,19],37:[2,19],39:[2,19],40:[2,19],41:[2,19],42:[2,19],44:[2,19]},{5:[2,25],6:[2,25],8:[2,25],10:[2,25],12:[2,25],14:[2,25],16:[2,25],18:[1,46],19:[2,25],21:[2,25],22:[2,25],28:[2,25],29:[2,25],30:[2,25],31:[2,25],32:[2,25],33:[2,25],34:[2,25],35:[2,25],37:[2,25],39:[2,25],40:[2,25],41:[2,25],42:[2,25],43:[2,25],44:[2,25]},{10:[2,14],16:[2,14],18:[2,14],19:[2,14],21:[2,14],22:[2,14],28:[2,14],29:[2,14],30:[2,14],31:[2,14],32:[2,14],34:[2,14],37:[2,14],39:[2,14],40:[2,14],41:[2,14],42:[2,14],44:[2,14]},{5:[2,41],6:[2,41],8:[2,41],10:[2,41],12:[2,41],14:[2,41],16:[2,41],18:[2,41],19:[2,41],21:[2,41],22:[2,41],28:[2,41],29:[2,41],30:[2,41],31:[2,41],32:[2,41],33:[2,41],34:[2,41],35:[2,41],37:[2,41],39:[2,41],40:[2,41],41:[2,41],42:[2,41],43:[2,41],44:[2,41]},{5:[2,42],6:[2,42],8:[2,42],10:[2,42],12:[2,42],14:[2,42],16:[2,42],18:[2,42],19:[2,42],21:[2,42],22:[2,42],28:[2,42],29:[2,42],30:[2,42],31:[2,42],32:[2,42],33:[2,42],34:[2,42],35:[2,42],37:[2,42],39:[2,42],40:[2,42],41:[2,42],42:[2,42],43:[2,42],44:[2,42]},{32:[1,47]},{5:[2,28],6:[2,28],8:[2,28],10:[2,28],12:[2,28],14:[2,28],16:[2,28],18:[2,28],19:[2,28],21:[2,28],22:[2,28],23:[1,48],28:[2,28],29:[2,28],30:[2,28],31:[2,28],32:[2,28],33:[2,28],34:[2,28],35:[2,28],37:[2,28],39:[2,28],40:[2,28],41:[2,28],42:[2,28],43:[2,28],44:[2,28]},{5:[2,29],6:[2,29],8:[2,29],10:[2,29],12:[2,29],14:[2,29],16:[2,29],18:[2,29],19:[2,29],21:[2,29],22:[2,29],28:[2,29],29:[2,29],30:[2,29],31:[2,29],32:[2,29],33:[2,29],34:[2,29],35:[2,29],37:[2,29],39:[2,29],40:[2,29],41:[2,29],42:[2,29],43:[2,29],44:[2,29]},{5:[2,30],6:[2,30],8:[2,30],10:[2,30],12:[2,30],14:[2,30],16:[2,30],18:[2,30],19:[2,30],21:[2,30],22:[2,30],28:[2,30],29:[2,30],30:[2,30],31:[2,30],32:[2,30],33:[2,30],34:[2,30],35:[2,30],37:[2,30],39:[2,30],40:[2,30],41:[2,30],42:[2,30],43:[2,30],44:[2,30]},{5:[2,31],6:[2,31],8:[2,31],10:[2,31],12:[2,31],14:[2,31],16:[2,31],18:[2,31],19:[2,31],21:[2,31],22:[2,31],28:[2,31],29:[2,31],30:[2,31],31:[2,31],32:[2,31],33:[2,31],34:[2,31],35:[2,31],37:[2,31],39:[2,31],40:[2,31],41:[2,31],42:[2,31],43:[2,31],44:[2,31]},{7:49,9:5,10:[1,7],11:8,13:6,15:12,16:[1,17],17:9,19:[1,13],20:10,21:[1,14],22:[1,15],24:18,25:11,26:16,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],34:[1,26],36:31,37:[1,33],38:19,39:[1,27],40:[1,28],41:[1,29],42:[1,30],44:[1,20]},{7:50,9:5,10:[1,7],11:8,13:6,15:12,16:[1,17],17:9,19:[1,13],20:10,21:[1,14],22:[1,15],24:18,25:11,26:16,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],34:[1,26],36:31,37:[1,33],38:19,39:[1,27],40:[1,28],41:[1,29],42:[1,30],44:[1,20]},{32:[1,52],34:[1,51]},{34:[1,53]},{7:54,9:5,10:[1,7],11:8,13:6,15:12,16:[1,17],17:9,19:[1,13],20:10,21:[1,14],22:[1,15],24:18,25:11,26:16,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],34:[1,26],36:31,37:[1,33],38:19,39:[1,27],40:[1,28],41:[1,29],42:[1,30],44:[1,20]},{7:55,9:5,10:[1,7],11:8,13:6,15:12,16:[1,17],17:9,19:[1,13],20:10,21:[1,14],22:[1,15],24:18,25:11,26:16,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],34:[1,26],36:31,37:[1,33],38:19,39:[1,27],40:[1,28],41:[1,29],42:[1,30],44:[1,20]},{34:[1,56]},{5:[2,26],6:[2,26],8:[2,26],10:[2,26],12:[2,26],14:[2,26],16:[2,26],18:[2,26],19:[2,26],21:[2,26],22:[2,26],23:[2,26],28:[2,26],29:[2,26],30:[2,26],31:[2,26],32:[2,26],33:[2,26],34:[2,26],35:[2,26],37:[2,26],39:[2,26],40:[2,26],41:[2,26],42:[2,26],43:[2,26],44:[2,26]},{34:[2,34]},{4:57,7:4,9:5,10:[1,7],11:8,13:6,15:12,16:[1,17],17:9,19:[1,13],20:10,21:[1,14],22:[1,15],24:18,25:11,26:16,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],34:[1,26],36:31,37:[1,33],38:19,39:[1,27],40:[1,28],41:[1,29],42:[1,30],44:[1,20]},{1:[2,2]},{9:58,10:[1,7],11:8,13:6,15:12,16:[1,17],17:9,19:[1,13],20:10,21:[1,14],22:[1,15],24:18,25:11,26:16,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],34:[1,26],36:31,37:[1,33],38:19,39:[1,27],40:[1,28],41:[1,29],42:[1,30],44:[1,20]},{9:59,10:[1,7],11:8,13:6,15:12,16:[1,17],17:9,19:[1,13],20:10,21:[1,14],22:[1,15],24:18,25:11,26:16,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],34:[1,26],36:31,37:[1,33],38:19,39:[1,27],40:[1,28],41:[1,29],42:[1,30],44:[1,20]},{5:[2,8],6:[2,8],8:[2,8],10:[2,8],12:[2,8],14:[2,8],16:[2,8],19:[2,8],21:[2,8],22:[2,8],28:[2,8],29:[2,8],30:[2,8],31:[2,8],32:[2,8],33:[2,8],34:[2,8],35:[2,8],37:[2,8],39:[2,8],40:[2,8],41:[2,8],42:[2,8],43:[2,8],44:[2,8]},{10:[1,7],11:8,13:60,15:12,16:[1,17],17:9,19:[1,13],20:10,21:[1,14],22:[1,15],24:18,25:11,26:16,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],34:[1,26],36:31,37:[1,33],38:19,39:[1,27],40:[1,28],41:[1,29],42:[1,30],44:[1,20]},{10:[1,7],11:8,13:61,15:12,16:[1,17],17:9,19:[1,13],20:10,21:[1,14],22:[1,15],24:18,25:11,26:16,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],34:[1,26],36:31,37:[1,33],38:19,39:[1,27],40:[1,28],41:[1,29],42:[1,30],44:[1,20]},{5:[2,12],6:[2,12],8:[2,12],10:[2,12],12:[2,12],14:[2,12],16:[2,12],19:[2,12],21:[2,12],22:[2,12],28:[2,12],29:[2,12],30:[2,12],31:[2,12],32:[2,12],33:[2,12],34:[2,12],35:[2,12],37:[2,12],39:[2,12],40:[2,12],41:[2,12],42:[2,12],43:[2,12],44:[2,12]},{5:[2,21],6:[2,21],8:[2,21],10:[2,21],12:[2,21],14:[2,21],16:[2,21],19:[2,21],21:[2,21],22:[2,21],28:[2,21],29:[2,21],30:[2,21],31:[2,21],32:[2,21],33:[2,21],34:[2,21],35:[2,21],37:[2,21],39:[2,21],40:[2,21],41:[2,21],42:[2,21],43:[2,21],44:[2,21]},{5:[2,22],6:[2,22],8:[2,22],10:[2,22],12:[2,22],14:[2,22],16:[2,22],19:[2,22],21:[2,22],22:[2,22],28:[2,22],29:[2,22],30:[2,22],31:[2,22],32:[2,22],33:[2,22],34:[2,22],35:[2,22],37:[2,22],39:[2,22],40:[2,22],41:[2,22],42:[2,22],43:[2,22],44:[2,22]},{10:[1,7],11:8,13:62,15:12,16:[1,17],17:9,19:[1,13],20:10,21:[1,14],22:[1,15],24:18,25:11,26:16,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],34:[1,26],36:31,37:[1,33],38:19,39:[1,27],40:[1,28],41:[1,29],42:[1,30],44:[1,20]},{24:63,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],34:[1,26]},{10:[1,7],11:8,13:64,15:12,16:[1,17],17:9,19:[1,13],20:10,21:[1,14],22:[1,15],24:18,25:11,26:16,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],34:[1,26],36:31,37:[1,33],38:19,39:[1,27],40:[1,28],41:[1,29],42:[1,30],44:[1,20]},{7:65,9:5,10:[1,7],11:8,13:6,15:12,16:[1,17],17:9,19:[1,13],20:10,21:[1,14],22:[1,15],24:18,25:11,26:16,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],34:[1,26],36:31,37:[1,33],38:19,39:[1,27],40:[1,28],41:[1,29],42:[1,30],44:[1,20]},{24:66,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],34:[1,26]},{8:[1,36],10:[1,37],33:[1,67]},{8:[1,36],10:[1,37],35:[1,68]},{7:69,9:5,10:[1,7],11:8,13:6,15:12,16:[1,17],17:9,19:[1,13],20:10,21:[1,14],22:[1,15],24:18,25:11,26:16,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],34:[1,26],36:31,37:[1,33],38:19,39:[1,27],40:[1,28],41:[1,29],42:[1,30],44:[1,20]},{7:70,9:5,10:[1,7],11:8,13:6,15:12,16:[1,17],17:9,19:[1,13],20:10,21:[1,14],22:[1,15],24:18,25:11,26:16,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],34:[1,26],36:31,37:[1,33],38:19,39:[1,27],40:[1,28],41:[1,29],42:[1,30],44:[1,20]},{7:71,9:5,10:[1,7],11:8,13:6,15:12,16:[1,17],17:9,19:[1,13],20:10,21:[1,14],22:[1,15],24:18,25:11,26:16,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],34:[1,26],36:31,37:[1,33],38:19,39:[1,27],40:[1,28],41:[1,29],42:[1,30],44:[1,20]},{8:[1,36],10:[1,37],41:[1,72]},{8:[1,36],10:[1,37],43:[1,73]},{7:74,9:5,10:[1,7],11:8,13:6,15:12,16:[1,17],17:9,19:[1,13],20:10,21:[1,14],22:[1,15],24:18,25:11,26:16,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],34:[1,26],36:31,37:[1,33],38:19,39:[1,27],40:[1,28],41:[1,29],42:[1,30],44:[1,20]},{6:[1,75]},{5:[2,5],6:[2,5],8:[2,5],10:[2,5],11:38,12:[1,39],14:[1,40],15:12,16:[1,17],17:9,19:[1,13],20:10,21:[1,14],22:[1,15],24:18,25:11,26:16,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],33:[2,5],34:[1,26],35:[2,5],36:31,37:[1,33],38:19,39:[1,27],40:[1,28],41:[2,5],42:[1,30],43:[2,5],44:[1,20]},{5:[2,6],6:[2,6],8:[2,6],10:[2,6],11:38,12:[1,39],14:[1,40],15:12,16:[1,17],17:9,19:[1,13],20:10,21:[1,14],22:[1,15],24:18,25:11,26:16,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],33:[2,6],34:[1,26],35:[2,6],36:31,37:[1,33],38:19,39:[1,27],40:[1,28],41:[2,6],42:[1,30],43:[2,6],44:[1,20]},{5:[2,9],6:[2,9],8:[2,9],10:[2,9],12:[2,9],14:[2,9],16:[2,9],19:[2,9],21:[2,9],22:[2,9],28:[2,9],29:[2,9],30:[2,9],31:[2,9],32:[2,9],33:[2,9],34:[2,9],35:[2,9],37:[2,9],39:[2,9],40:[2,9],41:[2,9],42:[2,9],43:[2,9],44:[2,9]},{5:[2,10],6:[2,10],8:[2,10],10:[2,10],12:[2,10],14:[2,10],16:[2,10],19:[2,10],21:[2,10],22:[2,10],28:[2,10],29:[2,10],30:[2,10],31:[2,10],32:[2,10],33:[2,10],34:[2,10],35:[2,10],37:[2,10],39:[2,10],40:[2,10],41:[2,10],42:[2,10],43:[2,10],44:[2,10]},{10:[2,16],16:[2,16],19:[2,16],21:[2,16],22:[2,16],28:[2,16],29:[2,16],30:[2,16],31:[2,16],32:[2,16],34:[2,16],37:[2,16],39:[2,16],40:[2,16],41:[2,16],42:[2,16],44:[2,16]},{10:[2,20],16:[2,20],19:[2,20],21:[2,20],22:[2,20],28:[2,20],29:[2,20],30:[2,20],31:[2,20],32:[2,20],34:[2,20],37:[2,20],39:[2,20],40:[2,20],41:[2,20],42:[2,20],44:[2,20]},{5:[2,24],6:[2,24],8:[2,24],10:[2,24],12:[2,24],14:[2,24],16:[2,24],19:[2,24],21:[2,24],22:[2,24],28:[2,24],29:[2,24],30:[2,24],31:[2,24],32:[2,24],33:[2,24],34:[2,24],35:[2,24],37:[2,24],39:[2,24],40:[2,24],41:[2,24],42:[2,24],43:[2,24],44:[2,24]},{8:[1,36],10:[1,37],33:[1,76]},{5:[2,27],6:[2,27],8:[2,27],10:[2,27],12:[2,27],14:[2,27],16:[2,27],18:[2,27],19:[2,27],21:[2,27],22:[2,27],28:[2,27],29:[2,27],30:[2,27],31:[2,27],32:[2,27],33:[2,27],34:[2,27],35:[2,27],37:[2,27],39:[2,27],40:[2,27],41:[2,27],42:[2,27],43:[2,27],44:[2,27]},{5:[2,32],6:[2,32],8:[2,32],10:[2,32],12:[2,32],14:[2,32],16:[2,32],18:[2,32],19:[2,32],21:[2,32],22:[2,32],28:[2,32],29:[2,32],30:[2,32],31:[2,32],32:[2,32],33:[2,32],34:[2,32],35:[2,32],37:[2,32],39:[2,32],40:[2,32],41:[2,32],42:[2,32],43:[2,32],44:[2,32]},{5:[2,33],6:[2,33],8:[2,33],10:[2,33],12:[2,33],14:[2,33],16:[2,33],18:[2,33],19:[2,33],21:[2,33],22:[2,33],28:[2,33],29:[2,33],30:[2,33],31:[2,33],32:[2,33],33:[2,33],34:[2,33],35:[2,33],37:[2,33],39:[2,33],40:[2,33],41:[2,33],42:[2,33],43:[2,33],44:[2,33]},{8:[1,36],10:[1,37],35:[1,77]},{8:[1,36],10:[1,37],33:[1,78]},{8:[1,36],10:[1,37],35:[1,79]},{5:[2,38],6:[2,38],8:[2,38],10:[2,38],12:[2,38],14:[2,38],16:[2,38],18:[2,38],19:[2,38],21:[2,38],22:[2,38],28:[2,38],29:[2,38],30:[2,38],31:[2,38],32:[2,38],33:[2,38],34:[2,38],35:[2,38],37:[2,38],39:[2,38],40:[2,38],41:[2,38],42:[2,38],43:[2,38],44:[2,38]},{5:[2,39],6:[2,39],8:[2,39],10:[2,39],12:[2,39],14:[2,39],16:[2,39],18:[2,39],19:[2,39],21:[2,39],22:[2,39],28:[2,39],29:[2,39],30:[2,39],31:[2,39],32:[2,39],33:[2,39],34:[2,39],35:[2,39],37:[2,39],39:[2,39],40:[2,39],41:[2,39],42:[2,39],43:[2,39],44:[2,39]},{8:[1,36],10:[1,37],35:[1,80]},{1:[2,1]},{32:[1,81]},{5:[2,35],6:[2,35],8:[2,35],10:[2,35],12:[2,35],14:[2,35],16:[2,35],18:[2,35],19:[2,35],21:[2,35],22:[2,35],28:[2,35],29:[2,35],30:[2,35],31:[2,35],32:[2,35],33:[2,35],34:[2,35],35:[2,35],37:[2,35],39:[2,35],40:[2,35],41:[2,35],42:[2,35],43:[2,35],44:[2,35]},{5:[2,36],6:[2,36],8:[2,36],10:[2,36],12:[2,36],14:[2,36],16:[2,36],18:[2,36],19:[2,36],21:[2,36],22:[2,36],28:[2,36],29:[2,36],30:[2,36],31:[2,36],32:[2,36],33:[2,36],34:[2,36],35:[2,36],37:[2,36],39:[2,36],40:[2,36],41:[2,36],42:[2,36],43:[2,36],44:[2,36]},{5:[2,37],6:[2,37],8:[2,37],10:[2,37],12:[2,37],14:[2,37],16:[2,37],18:[2,37],19:[2,37],21:[2,37],22:[2,37],28:[2,37],29:[2,37],30:[2,37],31:[2,37],32:[2,37],33:[2,37],34:[2,37],35:[2,37],37:[2,37],39:[2,37],40:[2,37],41:[2,37],42:[2,37],43:[2,37],44:[2,37]},{5:[2,40],6:[2,40],8:[2,40],10:[2,40],12:[2,40],14:[2,40],16:[2,40],18:[2,40],19:[2,40],21:[2,40],22:[2,40],28:[2,40],29:[2,40],30:[2,40],31:[2,40],32:[2,40],33:[2,40],34:[2,40],35:[2,40],37:[2,40],39:[2,40],40:[2,40],41:[2,40],42:[2,40],43:[2,40],44:[2,40]},{7:82,9:5,10:[1,7],11:8,13:6,15:12,16:[1,17],17:9,19:[1,13],20:10,21:[1,14],22:[1,15],24:18,25:11,26:16,27:21,28:[1,32],29:[1,22],30:[1,23],31:[1,24],32:[1,25],34:[1,26],36:31,37:[1,33],38:19,39:[1,27],40:[1,28],41:[1,29],42:[1,30],44:[1,20]},{8:[1,36],10:[1,37],33:[1,83]},{5:[2,43],6:[2,43],8:[2,43],10:[2,43],12:[2,43],14:[2,43],16:[2,43],18:[2,43],19:[2,43],21:[2,43],22:[2,43],28:[2,43],29:[2,43],30:[2,43],31:[2,43],32:[2,43],33:[2,43],34:[2,43],35:[2,43],37:[2,43],39:[2,43],40:[2,43],41:[2,43],42:[2,43],43:[2,43],44:[2,43]}],
defaultActions: {3:[2,3],33:[2,34],35:[2,2],75:[2,1]},
parseError: function parseError(str, hash) {
    if (hash.recoverable) {
        this.trace(str);
    } else {
        throw new Error(str);
    }
},
parse: function parse(input) {
    var self = this, stack = [0], vstack = [null], lstack = [], table = this.table, yytext = '', yylineno = 0, yyleng = 0, recovering = 0, TERROR = 2, EOF = 1;
    var args = lstack.slice.call(arguments, 1);
    this.lexer.setInput(input);
    this.lexer.yy = this.yy;
    this.yy.lexer = this.lexer;
    this.yy.parser = this;
    if (typeof this.lexer.yylloc == 'undefined') {
        this.lexer.yylloc = {};
    }
    var yyloc = this.lexer.yylloc;
    lstack.push(yyloc);
    var ranges = this.lexer.options && this.lexer.options.ranges;
    if (typeof this.yy.parseError === 'function') {
        this.parseError = this.yy.parseError;
    } else {
        this.parseError = Object.getPrototypeOf(this).parseError;
    }
    function popStack(n) {
        stack.length = stack.length - 2 * n;
        vstack.length = vstack.length - n;
        lstack.length = lstack.length - n;
    }
    function lex() {
        var token;
        token = self.lexer.lex() || EOF;
        if (typeof token !== 'number') {
            token = self.symbols_[token] || token;
        }
        return token;
    }
    var symbol, preErrorSymbol, state, action, a, r, yyval = {}, p, len, newState, expected;
    while (true) {
        state = stack[stack.length - 1];
        if (this.defaultActions[state]) {
            action = this.defaultActions[state];
        } else {
            if (symbol === null || typeof symbol == 'undefined') {
                symbol = lex();
            }
            action = table[state] && table[state][symbol];
        }
                    if (typeof action === 'undefined' || !action.length || !action[0]) {
                var errStr = '';
                expected = [];
                for (p in table[state]) {
                    if (this.terminals_[p] && p > TERROR) {
                        expected.push('\'' + this.terminals_[p] + '\'');
                    }
                }
                if (this.lexer.showPosition) {
                    errStr = 'Parse error on line ' + (yylineno + 1) + ':\n' + this.lexer.showPosition() + '\nExpecting ' + expected.join(', ') + ', got \'' + (this.terminals_[symbol] || symbol) + '\'';
                } else {
                    errStr = 'Parse error on line ' + (yylineno + 1) + ': Unexpected ' + (symbol == EOF ? 'end of input' : '\'' + (this.terminals_[symbol] || symbol) + '\'');
                }
                this.parseError(errStr, {
                    text: this.lexer.match,
                    token: this.terminals_[symbol] || symbol,
                    line: this.lexer.yylineno,
                    loc: yyloc,
                    expected: expected
                });
            }
        if (action[0] instanceof Array && action.length > 1) {
            throw new Error('Parse Error: multiple actions possible at state: ' + state + ', token: ' + symbol);
        }
        switch (action[0]) {
        case 1:
            stack.push(symbol);
            vstack.push(this.lexer.yytext);
            lstack.push(this.lexer.yylloc);
            stack.push(action[1]);
            symbol = null;
            if (!preErrorSymbol) {
                yyleng = this.lexer.yyleng;
                yytext = this.lexer.yytext;
                yylineno = this.lexer.yylineno;
                yyloc = this.lexer.yylloc;
                if (recovering > 0) {
                    recovering--;
                }
            } else {
                symbol = preErrorSymbol;
                preErrorSymbol = null;
            }
            break;
        case 2:
            len = this.productions_[action[1]][1];
            yyval.$ = vstack[vstack.length - len];
            yyval._$ = {
                first_line: lstack[lstack.length - (len || 1)].first_line,
                last_line: lstack[lstack.length - 1].last_line,
                first_column: lstack[lstack.length - (len || 1)].first_column,
                last_column: lstack[lstack.length - 1].last_column
            };
            if (ranges) {
                yyval._$.range = [
                    lstack[lstack.length - (len || 1)].range[0],
                    lstack[lstack.length - 1].range[1]
                ];
            }
            r = this.performAction.apply(yyval, [
                yytext,
                yyleng,
                yylineno,
                this.yy,
                action[1],
                vstack,
                lstack
            ].concat(args));
            if (typeof r !== 'undefined') {
                return r;
            }
            if (len) {
                stack = stack.slice(0, -1 * len * 2);
                vstack = vstack.slice(0, -1 * len);
                lstack = lstack.slice(0, -1 * len);
            }
            stack.push(this.productions_[action[1]][0]);
            vstack.push(yyval.$);
            lstack.push(yyval._$);
            newState = table[stack[stack.length - 2]][stack[stack.length - 1]];
            stack.push(newState);
            break;
        case 3:
            return true;
        }
    }
    return true;
}};
/* generated by jison-lex 0.2.1 */
var lexer = (function(){
var lexer = {

EOF:1,

parseError:function parseError(str, hash) {
        if (this.yy.parser) {
            this.yy.parser.parseError(str, hash);
        } else {
            throw new Error(str);
        }
    },

// resets the lexer, sets new input
setInput:function (input) {
        this._input = input;
        this._more = this._backtrack = this.done = false;
        this.yylineno = this.yyleng = 0;
        this.yytext = this.matched = this.match = '';
        this.conditionStack = ['INITIAL'];
        this.yylloc = {
            first_line: 1,
            first_column: 0,
            last_line: 1,
            last_column: 0
        };
        if (this.options.ranges) {
            this.yylloc.range = [0,0];
        }
        this.offset = 0;
        return this;
    },

// consumes and returns one char from the input
input:function () {
        var ch = this._input[0];
        this.yytext += ch;
        this.yyleng++;
        this.offset++;
        this.match += ch;
        this.matched += ch;
        var lines = ch.match(/(?:\r\n?|\n).*/g);
        if (lines) {
            this.yylineno++;
            this.yylloc.last_line++;
        } else {
            this.yylloc.last_column++;
        }
        if (this.options.ranges) {
            this.yylloc.range[1]++;
        }

        this._input = this._input.slice(1);
        return ch;
    },

// unshifts one char (or a string) into the input
unput:function (ch) {
        var len = ch.length;
        var lines = ch.split(/(?:\r\n?|\n)/g);

        this._input = ch + this._input;
        this.yytext = this.yytext.substr(0, this.yytext.length - len - 1);
        //this.yyleng -= len;
        this.offset -= len;
        var oldLines = this.match.split(/(?:\r\n?|\n)/g);
        this.match = this.match.substr(0, this.match.length - 1);
        this.matched = this.matched.substr(0, this.matched.length - 1);

        if (lines.length - 1) {
            this.yylineno -= lines.length - 1;
        }
        var r = this.yylloc.range;

        this.yylloc = {
            first_line: this.yylloc.first_line,
            last_line: this.yylineno + 1,
            first_column: this.yylloc.first_column,
            last_column: lines ?
                (lines.length === oldLines.length ? this.yylloc.first_column : 0)
                 + oldLines[oldLines.length - lines.length].length - lines[0].length :
              this.yylloc.first_column - len
        };

        if (this.options.ranges) {
            this.yylloc.range = [r[0], r[0] + this.yyleng - len];
        }
        this.yyleng = this.yytext.length;
        return this;
    },

// When called from action, caches matched text and appends it on next action
more:function () {
        this._more = true;
        return this;
    },

// When called from action, signals the lexer that this rule fails to match the input, so the next matching rule (regex) should be tested instead.
reject:function () {
        if (this.options.backtrack_lexer) {
            this._backtrack = true;
        } else {
            return this.parseError('Lexical error on line ' + (this.yylineno + 1) + '. You can only invoke reject() in the lexer when the lexer is of the backtracking persuasion (options.backtrack_lexer = true).\n' + this.showPosition(), {
                text: "",
                token: null,
                line: this.yylineno
            });

        }
        return this;
    },

// retain first n characters of the match
less:function (n) {
        this.unput(this.match.slice(n));
    },

// displays already matched input, i.e. for error messages
pastInput:function () {
        var past = this.matched.substr(0, this.matched.length - this.match.length);
        return (past.length > 20 ? '...':'') + past.substr(-20).replace(/\n/g, "");
    },

// displays upcoming input, i.e. for error messages
upcomingInput:function () {
        var next = this.match;
        if (next.length < 20) {
            next += this._input.substr(0, 20-next.length);
        }
        return (next.substr(0,20) + (next.length > 20 ? '...' : '')).replace(/\n/g, "");
    },

// displays the character position where the lexing error occurred, i.e. for error messages
showPosition:function () {
        var pre = this.pastInput();
        var c = new Array(pre.length + 1).join("-");
        return pre + this.upcomingInput() + "\n" + c + "^";
    },

// test the lexed token: return FALSE when not a match, otherwise return token
test_match:function (match, indexed_rule) {
        var token,
            lines,
            backup;

        if (this.options.backtrack_lexer) {
            // save context
            backup = {
                yylineno: this.yylineno,
                yylloc: {
                    first_line: this.yylloc.first_line,
                    last_line: this.last_line,
                    first_column: this.yylloc.first_column,
                    last_column: this.yylloc.last_column
                },
                yytext: this.yytext,
                match: this.match,
                matches: this.matches,
                matched: this.matched,
                yyleng: this.yyleng,
                offset: this.offset,
                _more: this._more,
                _input: this._input,
                yy: this.yy,
                conditionStack: this.conditionStack.slice(0),
                done: this.done
            };
            if (this.options.ranges) {
                backup.yylloc.range = this.yylloc.range.slice(0);
            }
        }

        lines = match[0].match(/(?:\r\n?|\n).*/g);
        if (lines) {
            this.yylineno += lines.length;
        }
        this.yylloc = {
            first_line: this.yylloc.last_line,
            last_line: this.yylineno + 1,
            first_column: this.yylloc.last_column,
            last_column: lines ?
                         lines[lines.length - 1].length - lines[lines.length - 1].match(/\r?\n?/)[0].length :
                         this.yylloc.last_column + match[0].length
        };
        this.yytext += match[0];
        this.match += match[0];
        this.matches = match;
        this.yyleng = this.yytext.length;
        if (this.options.ranges) {
            this.yylloc.range = [this.offset, this.offset += this.yyleng];
        }
        this._more = false;
        this._backtrack = false;
        this._input = this._input.slice(match[0].length);
        this.matched += match[0];
        token = this.performAction.call(this, this.yy, this, indexed_rule, this.conditionStack[this.conditionStack.length - 1]);
        if (this.done && this._input) {
            this.done = false;
        }
        if (token) {
            return token;
        } else if (this._backtrack) {
            // recover context
            for (var k in backup) {
                this[k] = backup[k];
            }
            return false; // rule action called reject() implying the next rule should be tested instead.
        }
        return false;
    },

// return next match in input
next:function () {
        if (this.done) {
            return this.EOF;
        }
        if (!this._input) {
            this.done = true;
        }

        var token,
            match,
            tempMatch,
            index;
        if (!this._more) {
            this.yytext = '';
            this.match = '';
        }
        var rules = this._currentRules();
        for (var i = 0; i < rules.length; i++) {
            tempMatch = this._input.match(this.rules[rules[i]]);
            if (tempMatch && (!match || tempMatch[0].length > match[0].length)) {
                match = tempMatch;
                index = i;
                if (this.options.backtrack_lexer) {
                    token = this.test_match(tempMatch, rules[i]);
                    if (token !== false) {
                        return token;
                    } else if (this._backtrack) {
                        match = false;
                        continue; // rule action called reject() implying a rule MISmatch.
                    } else {
                        // else: this is a lexer rule which consumes input without producing a token (e.g. whitespace)
                        return false;
                    }
                } else if (!this.options.flex) {
                    break;
                }
            }
        }
        if (match) {
            token = this.test_match(match, rules[index]);
            if (token !== false) {
                return token;
            }
            // else: this is a lexer rule which consumes input without producing a token (e.g. whitespace)
            return false;
        }
        if (this._input === "") {
            return this.EOF;
        } else {
            return this.parseError('Lexical error on line ' + (this.yylineno + 1) + '. Unrecognized text.\n' + this.showPosition(), {
                text: "",
                token: null,
                line: this.yylineno
            });
        }
    },

// return next match that has a token
lex:function lex() {
        var r = this.next();
        if (r) {
            return r;
        } else {
            return this.lex();
        }
    },

// activates a new lexer condition state (pushes the new lexer condition state onto the condition stack)
begin:function begin(condition) {
        this.conditionStack.push(condition);
    },

// pop the previously active lexer condition state off the condition stack
popState:function popState() {
        var n = this.conditionStack.length - 1;
        if (n > 0) {
            return this.conditionStack.pop();
        } else {
            return this.conditionStack[0];
        }
    },

// produce the lexer rule set which is active for the currently active lexer condition state
_currentRules:function _currentRules() {
        if (this.conditionStack.length && this.conditionStack[this.conditionStack.length - 1]) {
            return this.conditions[this.conditionStack[this.conditionStack.length - 1]].rules;
        } else {
            return this.conditions["INITIAL"].rules;
        }
    },

// return the currently active lexer condition state; when an index argument is provided it produces the N-th previous condition state, if available
topState:function topState(n) {
        n = this.conditionStack.length - 1 - Math.abs(n || 0);
        if (n >= 0) {
            return this.conditionStack[n];
        } else {
            return "INITIAL";
        }
    },

// alias for begin(condition)
pushState:function pushState(condition) {
        this.begin(condition);
    },

// return the number of states currently on the stack
stateStackSize:function stateStackSize() {
        return this.conditionStack.length;
    },
options: {"flex":true},
performAction: function anonymous(yy,yy_,$avoiding_name_collisions,YY_START) {

var YYSTATE=YY_START;
switch($avoiding_name_collisions) {
case 0:/* skip whitespace */
break;
case 1:/* skip \space */
break;
case 2:/* skip '\ ' */
break;
case 3:return "INT"
break;
case 4:return "FLOAT"
break;
case 5:return "^"
break;
case 6:return "*"
break;
case 7:return "*"
break;
case 8:return "*"
break;
case 9:return "*"
break;
case 10:return "/"
break;
case 11:return "/"
break;
case 12:return "-"
break;
case 13:return "-"
break;
case 14:return "+"
break;
case 15:return "^"
break;
case 16:return "("
break;
case 17:return ")"
break;
case 18:return "("
break;
case 19:return ")"
break;
case 20:return "{"
break;
case 21:return "}"
break;
case 22:return "{"
break;
case 23:return "}"
break;
case 24:return "_"
break;
case 25:return "|"
break;
case 26:return "LEFT|"
break;
case 27:return "RIGHT|"
break;
case 28:return "!"
break;
case 29:return "SIGN"
break;
case 30:yy_.yytext = "<="; return "SIGN"
break;
case 31:yy_.yytext = ">="; return "SIGN"
break;
case 32:yy_.yytext = "<="; return "SIGN"
break;
case 33:yy_.yytext = ">="; return "SIGN"
break;
case 34:yy_.yytext = "<>"; return "SIGN"
break;
case 35:yy_.yytext = "<>"; return "SIGN"
break;
case 36:yy_.yytext = "<>"; return "SIGN"
break;
case 37:yy_.yytext = "<>"; return "SIGN"
break;
case 38:yy_.yytext = "<="; return "SIGN"
break;
case 39:yy_.yytext = ">="; return "SIGN"
break;
case 40:return "FRAC"
break;
case 41:return "FRAC"
break;
case 42:return "sqrt"
break;
case 43:return "abs"
break;
case 44:return "ln"
break;
case 45:return "log"
break;
case 46:return "TRIG"
break;
case 47:return "TRIG"
break;
case 48:return "TRIG"
break;
case 49:return "TRIG"
break;
case 50:yy_.yytext = "sin"; return "TRIG"
break;
case 51:yy_.yytext = "cos"; return "TRIG"
break;
case 52:yy_.yytext = "tan"; return "TRIG"
break;
case 53:yy_.yytext = "csc"; return "TRIG"
break;
case 54:yy_.yytext = "sec"; return "TRIG"
break;
case 55:yy_.yytext = "cot"; return "TRIG"
break;
case 56:yy_.yytext = "arcsin"; return "TRIG"
break;
case 57:yy_.yytext = "arccos"; return "TRIG"
break;
case 58:yy_.yytext = "arctan"; return "TRIG"
break;
case 59:yy_.yytext = "arccsc"; return "TRIG"
break;
case 60:yy_.yytext = "arcsec"; return "TRIG"
break;
case 61:yy_.yytext = "arccot"; return "TRIG"
break;
case 62:return "TRIGINV"
break;
case 63:return "TRIGINV"
break;
case 64:yy_.yytext = "sinh"; return "TRIG"
break;
case 65:yy_.yytext = "cosh"; return "TRIG"
break;
case 66:yy_.yytext = "tanh"; return "TRIG"
break;
case 67:yy_.yytext = "csch"; return "TRIG"
break;
case 68:yy_.yytext = "sech"; return "TRIG"
break;
case 69:yy_.yytext = "tanh"; return "TRIG"
break;
case 70:return "CONST"
break;
case 71:yy_.yytext = "pi"; return "CONST"
break;
case 72:yy_.yytext = "pi"; return "CONST"
break;
case 73:return "VAR"
break;
case 74:yy_.yytext = "theta"; return "VAR"
break;
case 75:yy_.yytext = "theta"; return "VAR"
break;
case 76:return "VAR"
break;
case 77:yy_.yytext = "phi"; return "VAR"
break;
case 78:yy_.yytext = "phi"; return "VAR"
break;
case 79:return yy.symbolLexer(yy_.yytext)
break;
case 80:return "EOF"
break;
case 81:return "INVALID"
break;
case 82:console.log(yy_.yytext);
break;
}
},
rules: [/^(?:\s+)/,/^(?:\\space)/,/^(?:\\ )/,/^(?:[0-9]+\.?)/,/^(?:([0-9]+)?\.[0-9]+)/,/^(?:\*\*)/,/^(?:\*)/,/^(?:\\cdot|·)/,/^(?:\\times|×)/,/^(?:\\ast)/,/^(?:\/)/,/^(?:\\div|÷)/,/^(?:-)/,/^(?:−)/,/^(?:\+)/,/^(?:\^)/,/^(?:\()/,/^(?:\))/,/^(?:\\left\()/,/^(?:\\right\))/,/^(?:\{)/,/^(?:\})/,/^(?:\\left\{)/,/^(?:\\right\})/,/^(?:_)/,/^(?:\|)/,/^(?:\\left\|)/,/^(?:\\right\|)/,/^(?:\!)/,/^(?:<=|>=|<>|<|>|=)/,/^(?:\\le)/,/^(?:\\ge)/,/^(?:\\leq)/,/^(?:\\geq)/,/^(?:=\/=)/,/^(?:\\ne)/,/^(?:\\neq)/,/^(?:≠)/,/^(?:≤)/,/^(?:≥)/,/^(?:\\frac)/,/^(?:\\dfrac)/,/^(?:sqrt|\\sqrt)/,/^(?:abs|\\abs)/,/^(?:ln|\\ln)/,/^(?:log|\\log)/,/^(?:sin|cos|tan)/,/^(?:csc|sec|cot)/,/^(?:sinh|cosh|tanh)/,/^(?:csch|sech|coth)/,/^(?:\\sin)/,/^(?:\\cos)/,/^(?:\\tan)/,/^(?:\\csc)/,/^(?:\\sec)/,/^(?:\\cot)/,/^(?:\\arcsin)/,/^(?:\\arccos)/,/^(?:\\arctan)/,/^(?:\\arccsc)/,/^(?:\\arcsec)/,/^(?:\\arccot)/,/^(?:arcsin|arccos|arctan)/,/^(?:arccsc|arcsec|arccot)/,/^(?:\\sinh)/,/^(?:\\cosh)/,/^(?:\\tanh)/,/^(?:\\csch)/,/^(?:\\sech)/,/^(?:\\coth)/,/^(?:pi)/,/^(?:π)/,/^(?:\\pi)/,/^(?:theta)/,/^(?:θ)/,/^(?:\\theta)/,/^(?:phi)/,/^(?:φ)/,/^(?:\\phi)/,/^(?:[a-zA-Z])/,/^(?:$)/,/^(?:.)/,/^(?:.)/],
conditions: {"INITIAL":{"rules":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82],"inclusive":true}}
};
return lexer;
})();
parser.lexer = lexer;
function Parser () {
  this.yy = {};
}
Parser.prototype = parser;parser.Parser = Parser;
return new Parser;
})();

KAS.parser = parser;
})(KAS);
(function(KAS) {

/*  The node hierarcy is as follows:

    (Expr)
        (Seq)           2+ children
            Add
            Mul
        Pow             2 children
        Log             2 children
        Eq              2 children
        Trig            1 child
        Abs             1 child
        (Symbol)
            Func        1 child     e.g. f(x)
            Var         leaf node   e.g. x, x_n
            Const       leaf node   e.g. pi, e, <i>
        (Num)           leaf node
            Rational                e.g. 2/3
                Int
            Float

    (abstract, not meant to be instantiated)

    == Key design concepts ==
    Functional: All methods return new nodes - nodes are never mutated.
    Ignore commutativity: Commutative inputs should be parsed equivalently.
    Exploit commutativity: Output should take advantage of ordering.
*/

/* non user-facing functions */

// assert that all abstract methods have been overridden
var abstract = function() {
    // Try to give people a bit of information when this happens
    throw new Error("Abstract method - must override for expr: " +
            this.print());
};

// throw an error that is meant to be caught by the test suite (not user facing)
var error = function(message) { throw new Error(message); };

// reliably detect NaN
var isNaN = function(object) { return object !== object; };

// return a random float between min (inclusive) and max (exclusive),
// not that inclusivity means much, probabilistically, on floats
var randomFloat = function(min, max) {
    var extent = max - min;
    return Math.random() * extent + min;
};

/* constants */
var ITERATIONS = 12;
var TOLERANCE = 9; // decimal places


/* abstract base expression node */
function Expr() {}

_.extend(Expr.prototype, {

    // this node's immediate constructor
    func: abstract,

    // an array of the arguments to this node's immediate constructor
    args: abstract,

    // make a new node with the given arguments
    construct: function(args) {
        var instance = new this.func();
        this.func.apply(instance, args);
        return instance;
    },

    // an abstraction for chainable, bottom-up recursion
    recurse: function(method) {
        var passed = Array.prototype.slice.call(arguments, 1);
        var args = _.map(this.args(), function(arg) {
            return _.isString(arg) ? arg : arg[method].apply(arg, passed);
        });
        return this.construct(args);
    },

    // evaluate numerically with given variable mapping
    eval: abstract,

    codegen: abstract,

    compile: function() {
        var code = this.codegen();
        try {
            return new Function("vars", "return " + code + ";");
        } catch (e) {
            throw new Error("Function did not compile: " + code);
        }
    },

    // returns a string unambiguously representing the expression
    // should be valid as input
    // e.g. this.equals(parse(this.print())) === true
    print: abstract,

    // returns a TeX string representing the expression
    tex: abstract,

    // returns a TeX string, modified by the given options
    asTex: function(options) {

        options = options || {};
        _.defaults(options, {
            display: true,
            dynamic: true,
            times: false
        });

        var tex = this.tex();

        if (options.display) {
            tex = "\\displaystyle " + tex;
        }
        if (options.dynamic) {
            tex = tex.replace(/\(/g, "\\left(");
            tex = tex.replace(/\)/g, "\\right)");
            tex = tex.replace(/\[/g, "\\left[");
            tex = tex.replace(/\]/g, "\\right]");
        }
        if (options.times) {
            tex = tex.replace(/\\cdot/g, "\\times");
        }

        return tex;
    },

    // returns the name of this expression's constructor as a string
    // only used for testing and debugging (the ugly regex is for IE8)
    name: function() {
        if (this.func.name) {
            return this.func.name;
        } else {
            return this.func.toString().match(/^function\s*([^\s(]+)/)[1];
        }
    },

    // returns a string representing current node structure
    repr: function() {
        return this.name() + "(" + _.map(this.args(), function(arg) {
            return _.isString(arg) ? arg : arg.repr();
        }).join(",") + ")";
    },

    // removes all negative signs
    strip: function() { return this.recurse("strip"); },

    // canonically reorders all commutative elements
    normalize: function() { return this.recurse("normalize"); },

    // expands the expression
    expand: function() { return this.recurse("expand"); },

    // naively factors out like terms
    factor: function(options) { return this.recurse("factor", options); },

    // collect all like terms
    collect: function(options) { return this.recurse("collect", options); },

    // strict syntactic equality check
    equals: function(other) {
        return this.normalize().print() === other.normalize().print();
    },

    // expand and collect until the expression no longer changes
    simplify: function(options) {
        options = _.extend({
            once: false
        }, options);

        // Attempt to factor and collect
        var step1 = this.factor(options);
        var step2 = step1.collect(options);

        // Rollback if collect didn't do anything
        if (step1.equals(step2)) {
            step2 = this.collect(options);
        }

        // Attempt to expand and collect
        var step3 = step2.expand(options);
        var step4 = step3.collect(options);

        // Rollback if collect didn't do anything
        if (step3.equals(step4)) {
            step4 = step2.collect(options);
        }

        // One round of simplification complete
        var simplified = step4;

        if (options.once || this.equals(simplified)) {
            return simplified;
        } else {
            return simplified.simplify(options);
        }
    },

    // check whether this expression is simplified
    isSimplified: function() {
        return this.equals(this.simplify());
    },

    // return the child nodes of this node
    exprArgs: function() {
        return _.filter(this.args(), function(arg) {
            return arg instanceof Expr;
        });
    },

    // return the variables (function and non) within the expression
    getVars: function(excludeFunc) {
        return _.uniq(_.flatten(_.invoke(this.exprArgs(), "getVars", excludeFunc))).sort();
    },

    // check whether this expression node is of a particular type
    is: function(func) {
        return this instanceof func;
    },

    // check whether this expression has a particular node type
    has: function(func) {
        if (this instanceof func) {
            return true;
        }
        return _.any(this.exprArgs(), function(arg) { return arg.has(func); });
    },

    // raise this expression to a given exponent
    // most useful for eventually implementing i^3 = -i, etc.
    raiseToThe: function(exp) {
        return new Pow(this, exp);
    },

    // does this expression have a specific rendering hint?
    // rendering hints are picked up while parsing, but are lost during transformations
    isSubtract: function() { return false; },
    isDivide:  function() { return false; },
    isRoot:  function() { return false; },

    // whether this node needs an explicit multiplication sign if following a Num
    needsExplicitMul: function() {
        return this.args()[0].needsExplicitMul();
    },

    // check that the variables in both expressions are the same
    sameVars: function(other) {
        var vars1 = this.getVars();
        var vars2 = other.getVars();

        // the other Expr can have more variables than this one
        // this lets you multiply equations by other variables
        var same = function(array1, array2) {
            return !_.difference(array1, array2).length;
        };

        var lower = function(array) {
            return _.uniq(_.invoke(array, "toLowerCase")).sort();
        };

        var equal = same(vars1, vars2);
        var equalIgnoringCase = same(lower(vars1), lower(vars2));

        return {equal: equal, equalIgnoringCase: equalIgnoringCase};
    },

    // semantic equality check, call after sameVars() to avoid potential false positives
    // plug in random numbers for the variables in both expressions
    // if they both consistently evaluate the same, then they're the same
    compare: function(other) {
        // equation comparisons are handled by Eq.compare()
        if (other instanceof Eq) {
            return false;
        }

        var varList = _.union(
            this.getVars(/* excludeFunc */ true),
            other.getVars(/* excludeFunc */ true));

        // If the numbers are large we would like to do a relative comparison
        // rather than an absolute one, but if they're small enough then an
        // absolute comparison makes more sense
        var getDelta = function(num1, num2) {
            if (Math.abs(num1) < 1 || Math.abs(num2) < 1) {
                return Math.abs(num1 - num2);
            } else {
                return Math.abs(1 - num1 / num2);
            }
        };

        var equalNumbers = function(num1, num2) {
            var delta = getDelta(num1, num2);
            return ((num1 === num2) || /* needed if either is +/- Infinity */
                    (isNaN(num1) && isNaN(num2)) ||
                    (delta < Math.pow(10, -TOLERANCE)));
        };

        // if no variables, only need to evaluate once
        if (!varList.length) {
            return equalNumbers(this.eval(), other.eval());
        }

        // collect here to avoid sometimes dividing by zero, and sometimes not
        // it is better to be deterministic, e.g. x/x -> 1
        // TODO(alex): may want to keep track of assumptions as they're made
        var expr1 = this.collect();
        var expr2 = other.collect();

        for (var i = 0; i < ITERATIONS; i++) {

            var vars = {};
            // one third total iterations each with range 10, 100, and 1000
            var range = Math.pow(10, 1 + Math.floor(3 * i / ITERATIONS));

            _.each(varList, function(v) {
                vars[v] = randomFloat(-range, range);
            });

            var equal;
            if (expr1.has(Func) || expr2.has(Func)) {
                var result1 = expr1.partialEval(vars);
                var result2 = expr2.partialEval(vars);

                equal = result1.simplify().equals(result2.simplify());
            } else {
                var result1 = expr1.eval(vars);
                var result2 = expr2.eval(vars);

                equal = equalNumbers(result1, result2);
            }

            if (!equal) {
                return false;
            }
        }

        return true;
    },

    // evaluate as much of the expression as possible
    partialEval: function(vars) {
        if (!this.has(Func)) {
            return new Float(this.eval(vars).toFixed(TOLERANCE)).collect();
        } else if (this instanceof Func) {
            return new Func(this.symbol, this.arg.partialEval(vars));
        } else {
            return this.recurse("partialEval", vars);
        }
    },

    // check that the structure of both expressions is the same
    // all negative signs are stripped and the expressions are converted to
    // a canonical commutative form
    // should only be done after compare() returns true to avoid false positives
    sameForm: function(other) {
        return this.strip().equals(other.strip());
    },

    // returns the GCD of this expression and the given factor
    findGCD: function(factor) {
        return this.equals(factor) ? factor : Num.One;
    },

    // return this expression's denominator
    getDenominator: function() {
        return Num.One;
    },

    // return this expression as a Mul
    asMul: function() {
        return new Mul(Num.One, this);
    },

    // TODO(alex): rename to isDefinitePositive or similar?
    // return whether this expression is 100% positive
    isPositive: abstract,

    // TODO(alex): rename to hasNegativeSign or similar?
    // return whether this expression has a negative sign
    isNegative: function() { return false; },

    // return a factor of this expression that is 100% positive
    asPositiveFactor: function() {
        return this.isPositive() ? this : Num.One;
    },

    // return a copy of the expression with a new hint set (preserves hints)
    addHint: function(hint) {
        if (!hint) {
            return this;
        }

        var expr = this.construct(this.args());
        expr.hints = _.clone(this.hints);
        expr.hints[hint] = true;
        return expr;
    },

    hints: {
        parens: false
    },

    // currently unused!
    asExpr: function() { return this; },

    // complete parse by performing a few necessary transformations
    completeParse: function() { return this.recurse("completeParse"); },

    abs: abstract,

    negate: function() {
        return new Mul(Num.Neg, this);
    }
});


/* abstract sequence node */
function Seq() {}
Seq.prototype = new Expr();

_.extend(Seq.prototype, {
    args: function() { return this.terms; },

    normalize: function() {
        var terms = _.sortBy(_.invoke(this.terms, "normalize"), function(term) {
            return term.print();
        });

        return new this.func(terms);
    },

    expand: function() {
        return this.recurse("expand").flatten();
    },

    // partition the sequence into its numeric and non-numeric parts
    // makes no guarantees about the validity of either part!
    partition: function() {
        var terms = _.groupBy(this.terms, function(term) {
            return term instanceof Num;
        });

        var numbers = terms[true] || [];
        var others = terms[false] || [];

        return [new this.func(numbers), new this.func(others)];
    },

    // ensure that sequences have 2+ terms and no nested sequences of the same type
    // this is a shallow flattening and will return a non-Seq if terms.length <= 1
    flatten: function() {
        var type = this;
        var terms = _.reject(this.terms, function(term) {
            return term.equals(type.identity);
        });

        if (terms.length === 0) {
            return type.identity;
        }
        if (terms.length === 1) {
            return terms[0];
        }

        var grouped = _.groupBy(terms, function(term) {
            return term instanceof type.func;
        });

        // same contains the children which are Seqs of the same type as this Seq
        var same = grouped[true] || [];
        var others = grouped[false] || [];

        var flattened = others.concat(_.flatten(_.pluck(same, "terms"), /* shallow: */ true));
        return new type.func(flattened);
    },

    // the identity associated with the sequence
    identity: undefined,

    // reduce a numeric sequence to a Num
    reduce: abstract,

    isPositive: function() {
        var terms = _.invoke(this.terms, "collect");
        return _.all(_.invoke(terms, "isPositive"));
    },

    // return a new Seq with a given term replaced by a different term
    // (or array of terms). given term can be passed directly, or by index
    // if no new term is provided, the old one is simply removed
    replace: function(oldTerm, newTerm) {
        var index;

        if (oldTerm instanceof Expr) {
            index = _.indexOf(this.terms, oldTerm);
        } else {
            index = oldTerm;
        }

        var newTerms = [];
        if (_.isArray(newTerm)) {
            newTerms = newTerm;
        } else if (newTerm) {
            newTerms = [newTerm];
        }

        var terms = this.terms.slice(0, index)
                    .concat(newTerms)
                    .concat(this.terms.slice(index + 1));

        return new this.func(terms);
    },

    // syntactic sugar for replace()
    remove: function(term) {
        return this.replace(term);
    },

    getDenominator: function() {
        // TODO(alex): find and return LCM
        return new Mul(_.invoke(this.terms, "getDenominator")).flatten();
    }
});


/* sequence of additive terms */
function Add() {
    if (arguments.length === 1) {
        this.terms = arguments[0];
    } else {
        this.terms = _.toArray(arguments);
    }
}
Add.prototype = new Seq();

_.extend(Add.prototype, {
    func: Add,

    eval: function(vars, options) {
        return _.reduce(this.terms, function(memo, term) { return memo + term.eval(vars, options); }, 0);
    },

    codegen: function() {
        return _.map(this.terms, function(term) {
            return "(" + term.codegen() + ")";
        }).join(" + ") || "0";
    },

    print: function() {
        return _.invoke(this.terms, "print").join("+");
    },

    tex: function() {
        var tex = "";

        _.each(this.terms, function(term) {
            if (!tex || term.isSubtract()) {
                tex += term.tex();
            } else {
                tex += "+" + term.tex();
            }
        });

        return tex;
    },

    collect: function(options) {
        var terms = _.invoke(this.terms, "collect", options);

        // [Expr expr, Num coefficient]
        var pairs = [];

        _.each(terms, function(term) {
            if (term instanceof Mul) {
                var muls = term.partition();
                pairs.push([muls[1].flatten(), muls[0].reduce(options)]);
            } else if (term instanceof Num) {
                pairs.push([Num.One, term]);
            } else {
                pairs.push([term, Num.One]);
            }
        });

        // { (Expr expr).print(): [[Expr expr, Num coefficient]] }
        var grouped = _.groupBy(pairs, function(pair) {
            return pair[0].normalize().print();
        });

        var collected = _.compact(_.map(grouped, function(pairs) {
            var expr = pairs[0][0];
            var sum = new Add(_.zip.apply(_, pairs)[1]);
            var coefficient = sum.reduce(options);
            return new Mul(coefficient, expr).collect(options);
        }));

        // TODO(alex): use the Pythagorean identity here
        // e.g. x*sin^2(y) + x*cos^2(y) -> x

        return new Add(collected).flatten();
    },

    // naively factor out anything that is common to all terms
    // if options.keepNegative is specified, won't factor out a common -1
    factor: function(options) {
        options = _.extend({
            keepNegative: false
        }, options);

        var terms = _.invoke(this.terms, "collect");
        var factors;

        if (terms[0] instanceof Mul) {
            factors = terms[0].terms;
        } else {
            factors = [terms[0]];
        }

        _.each(_.rest(this.terms), function(term) {
            factors = _.map(factors, function(factor) {
                return term.findGCD(factor);
            });
        });

        if (!options.keepNegative && this.isNegative()) {
            factors.push(Num.Neg);
        }

        factors = new Mul(factors).flatten().collect();

        var remainder = _.map(terms, function(term) {
            return Mul.handleDivide(term, factors).simplify();
        });
        remainder = new Add(remainder).flatten();

        return Mul.createOrAppend(factors, remainder).flatten();
    },

    reduce: function(options) {
        return _.reduce(this.terms, function(memo, term) {
            return memo.add(term, options);
        }, this.identity);
    },

    needsExplicitMul: function() { return false; },

    isNegative: function() {
        var terms = _.invoke(this.terms, "collect");
        return _.all(_.invoke(terms, "isNegative"));
    },

    negate: function() {
        return new Add(_.invoke(this.terms, "negate"));
    }
});


/* sequence of multiplicative terms */
function Mul() {
    if (arguments.length === 1) {
        this.terms = arguments[0];
    } else {
        this.terms = _.toArray(arguments);
    }
}
Mul.prototype = new Seq();

_.extend(Mul.prototype, {
    func: Mul,

    eval: function(vars, options) {
        return _.reduce(this.terms, function(memo, term) { return memo * term.eval(vars, options); }, 1);
    },

    codegen: function() {
        return _.map(this.terms, function(term) {
            return "(" + term.codegen() + ")";
        }).join(" * ") || "0";
    },

    print: function() {
        return _.map(this.terms, function(term) {
            return (term instanceof Add) ? "(" + term.print() + ")" : term.print();
        }).join("*");
    },

    // since we don't care about commutativity, we can render a Mul any way we choose
    // so we follow convention: first any negatives, then any numbers, then everything else
    tex: function() {
        var cdot = " \\cdot ";

        var terms = _.groupBy(this.terms, function(term) {
            if (term.isDivide()) {
                return "inverse";
            } else if (term instanceof Num) {
                return "number";
            } else {
                return "other";
            }
        });

        var inverses = terms.inverse || [];
        var numbers = terms.number || [];
        var others = terms.other || [];

        var negatives = "";
        var numerator;

        // check all the numbers to see if there is a rational we can extract,
        // since we would like 1/2x/y to come out as \frac{1}{2}\frac{x}{y},
        // and not \frac{1x}{2y}.
        for (var i = 0; i < numbers.length; i++) {
            var isRational = numbers[i] instanceof Rational &&
                                !(numbers[i] instanceof Int);
            if (isRational && others.length > 0 && inverses.length > 0) {
                var withThisRemoved = numbers.slice();
                withThisRemoved.splice(i, 1);
                var newTerms = withThisRemoved.concat(inverses).concat(others);
                return numbers[i].tex() + new Mul(newTerms).tex();
            }
        }

        numbers = _.compact(_.map(numbers, function(term) {
            var hasDenom = (term instanceof Rational) && !(term instanceof Int);
            var shouldPushDown = !term.hints.fraction || inverses.length > 0;
            if (hasDenom && shouldPushDown) {
                // e.g. 3x/4 -> 3/4*x (internally) -> 3x/4 (rendered)
                inverses.push(new Pow(new Int(term.d), Num.Div));
                var number = new Int(term.n);
                number.hints = term.hints;
                return _.any(term.hints) ? number : null;
            } else {
                return term;
            }
        }));

        if (numbers.length === 0 && others.length === 1) {
            // e.g. (x+y)/z -> \frac{x+y}{z}
            numerator = others[0].tex();
        } else {
            var tex = "";

            _.each(numbers, function(term) {
                if (term.hints.subtract && term.hints.entered) {
                    negatives += "-";
                    tex += (tex ? cdot : "") + term.abs().tex();
                } else if ((term instanceof Int) && (term.n === -1) &&
                    (term.hints.negate || term.hints.subtract)) {
                    // e.g. -1*-1 -> --1
                    // e.g. -1*x -> -x
                    negatives += "-";
                } else {
                    // e.g. 2*3 -> 2(dot)3
                    tex += (tex ? cdot : "") + term.tex();
                }
            });

            _.each(others, function(term) {
                if (term.needsExplicitMul()) {
                    // e.g. 2*2^3 -> 2(dot)2^3
                    tex += (tex ? cdot : "") + term.tex();
                } else if (term instanceof Add) {
                    // e.g. (a+b)*c -> (a+b)c
                    tex += "(" + term.tex() + ")";
                } else {
                    // e.g. a*b*c -> abc
                    tex += term.tex();
                }
            });

            numerator = tex ? tex : "1";
        }

        if (!inverses.length) {
            return negatives + numerator;
        } else {
            var denominator = new Mul(_.invoke(inverses, "asDivide")).flatten().tex();
            return negatives + "\\frac{" + numerator + "}{" + denominator + "}";
        }
    },

    strip: function() {
        var terms = _.map(this.terms, function(term) {
            return term instanceof Num ? term.abs() : term.strip();
        });
        return new Mul(terms).flatten();
    },

    // expand numerator and denominator separately
    expand: function() {

        var isAdd = function(term) {
            return term instanceof Add;
        };

        var isInverse = function(term) {
            return term instanceof Pow && term.exp.isNegative();
        };

        var isInverseAdd = function(term) {
            return isInverse(term) && isAdd(term.base);
        };

        var mul = this.recurse("expand").flatten();

        var hasAdd = _.any(mul.terms, isAdd);
        var hasInverseAdd = _.any(mul.terms, isInverseAdd);

        if (!(hasAdd || hasInverseAdd)) {
            return mul;
        }

        var terms = _.groupBy(mul.terms, isInverse);
        var normals = terms[false] || [];
        var inverses = terms[true] || [];

        if (hasAdd) {
            var grouped = _.groupBy(normals, isAdd);
            var adds = grouped[true] || [];
            var others = grouped[false] || [];

            // loop over each additive sequence
            var expanded = _.reduce(adds, function(expanded, add) {
                // loop over each expanded array of terms
                return _.reduce(expanded, function(temp, array) {
                    // loop over each additive sequence's terms
                    return temp.concat(_.map(add.terms, function(term) {
                        return array.concat(term);
                    }));
                }, []);
            }, [[]]);

            // join each fully expanded array of factors with remaining multiplicative factors
            var muls = _.map(expanded, function(array) {
                return new Mul(others.concat(array)).flatten();
            });

            normals = [new Add(muls)];
        }

        if (hasInverseAdd) {
            var denominator = new Mul(_.invoke(inverses, "getDenominator")).flatten();
            inverses = [new Pow(denominator.expand(), Num.Div)];
        }

        return new Mul(normals.concat(inverses)).flatten();
    },

    factor: function(options) {
        var factored = this.recurse("factor", options).flatten();
        if (! (factored instanceof Mul)) {
            return factored;
        }

        // Combine any factored out Rationals into one, but don't collect
        var grouped = _.groupBy(factored.terms, function(term) {
            return term instanceof Rational;
        });

        // Could also accomplish this by passing a new option
        // e.g. return  memo.mul(term, {autocollect: false});
        // TODO(alex): Decide whether this is a good use of options or not
        var rational = _.reduce(grouped[true], function(memo, term) {
            return {n: memo.n * term.n, d: memo.d * term.d};
        }, {n: 1, d: 1});

        if (rational.d === 1) {
            rational = new Int(rational.n);
        } else {
            rational = new Rational(rational.n, rational.d);
        }

        return new Mul((grouped[false] || []).concat(rational)).flatten();
    },

    collect: function(options) {
        var partitioned = this.recurse("collect", options).partition();
        var number = partitioned[0].reduce(options);

        // e.g. 0*x -> 0
        if (number.eval() === 0) {
            return Num.Zero;
        }

        var others = partitioned[1].flatten();

        // e.g. 2*2 -> 4
        // e.g. 2*2*x -> 4*x
        if (!(others instanceof Mul)) {
            return new Mul(number, others).flatten();
        }

        others = others.terms;

        // [Expr base, Expr exp]
        var pairs = [];

        _.each(others, function(term) {
            if (term instanceof Pow) {
                pairs.push([term.base, term.exp]);
            } else {
                pairs.push([term, Num.One]);
            }
        });

        // {(Expr base).print(): [[Expr base, Expr exp]]}
        var grouped = _.groupBy(pairs, function(pair) {
            return pair[0].normalize().print();
        });

        // [[Expr base, Expr exp]]
        var summed = _.compact(_.map(grouped, function(pairs) {
            var base = pairs[0][0];
            var sum = new Add(_.zip.apply(_, pairs)[1]);
            var exp = sum.collect(options);

            if (exp instanceof Num && exp.eval() === 0) {
                return null;
            } else {
                return [base, exp];
            }
        }));

        var pairs = _.groupBy(summed, function(pair) {
            if (pair[0] instanceof Trig && pair[0].isBasic()) {
                return "trig";
            } else if (pair[0] instanceof Log) {
                return "log";
            } else {
                return "expr";
            }
        });
        var trigs = pairs.trig || [];
        var logs = pairs.log || [];
        var exprs = pairs.expr || [];

        if (trigs.length > 1) {
            // combine sines and cosines into other trig functions

            // {Trig.arg.print(): [[Trig base, Expr exp]]}
            var byArg = _.groupBy(trigs, function(pair) {
                return pair[0].arg.normalize().print();
            });

            trigs = [];
            _.each(byArg, function(pairs) {
                var arg = pairs[0][0].arg;

                // {Trig.type: Expr exp}
                var funcs = {sin: Num.Zero, cos: Num.Zero};
                _.each(pairs, function(pair) {
                    funcs[pair[0].type] = pair[1];
                });

                if (Mul.handleNegative(funcs.sin).collect(options).equals(funcs.cos)) {
                    // e.g. sin^x(y)/cos^x(y) -> tan^x(y)
                    if (funcs.cos.isNegative()) {
                        funcs = {tan: funcs.sin};
                    } else {
                        funcs = {cot: funcs.cos};
                    }
                }

                // TODO(alex): combine even if exponents not a perfect match
                // TODO(alex): transform 1/sin and 1/cos into csc and sec

                _.each(funcs, function(exp, type) {
                    trigs.push([new Trig(type, arg), exp]);
                });
            });
        }

        if (logs.length > 1) {
            // combine logs with the same base

            // {Log.base.print(): [[Log base, Expr exp]]}
            var byBase = _.groupBy(logs, function(pair) {
                return pair[0].base.normalize().print();
            });

            logs = [];

            _.each(byBase, function(pairs) {
                // only combine two logs of the same base, otherwise commutative
                // differences result in different equally valid output
                // e.g. ln(x)/ln(z)*ln(y) -> log_z(x)*ln(y)
                // e.g. ln(x)*ln(y)/ln(z) -> ln(x)*log_z(y)
                if (pairs.length === 2 &&
                    Mul.handleNegative(pairs[0][1]).collect(options).equals(pairs[1][1])) {
                    // e.g. ln(x)^y/ln(b)^y -> log_b(x)^y
                    if (pairs[0][1].isNegative()) {
                        logs.push([new Log(pairs[0][0].power, pairs[1][0].power), pairs[1][1]]);
                    } else {
                        logs.push([new Log(pairs[1][0].power, pairs[0][0].power), pairs[0][1]]);
                    }
                } else {
                    logs = logs.concat(pairs);
                }
            });

            // TODO(alex): combine if all inverses are the same e.g. ln(y)*ln(z)/ln(x)/ln(x)
        }

        pairs = trigs.concat(logs).concat(exprs);

        var collected = _.map(pairs, function(pair) {
            return new Pow(pair[0], pair[1]).collect(options);
        });

        return new Mul([number].concat(collected)).flatten();
    },

    isSubtract: function() {
        return _.any(this.terms, function(term) {
            return term instanceof Num && term.hints.subtract;
        });
    },

    // factor a single -1 in to the Mul
    // combine with a Num if all Nums are positive, else add as a term
    factorIn: function(hint) {
        var partitioned = this.partition();
        var numbers = partitioned[0].terms;
        var fold = numbers.length && _.all(numbers, function(num) {
            return num.n > 0;
        });

        if (fold) {
            // e.g. - x*2*3 -> x*-2*3
            var num = numbers[0].negate();
            num.hints = numbers[0].hints;
            return this.replace(numbers[0], num.addHint(hint));
        } else {
            // e.g. - x*y -> -1*x*y
            // e.g. - x*-2 -> -1*x*-2
            return new Mul([Num.negativeOne(hint)].concat(this.terms));
        }
    },

    // factor out a single hinted -1 (assume it is the division hint)
    // TODO(alex): make more general or rename to be more specific
    factorOut: function() {
        var factored = false;
        var terms = _.compact(_.map(this.terms, function(term, i, list) {
            if (!factored && term instanceof Num && term.hints.divide) {
                factored = true;
                return term.n !== -1 ? term.negate() : null;
            } else {
                return term;
            }
        }));

        if (terms.length === 1) {
            return terms[0];
        } else {
            return new Mul(terms);
        }
    },

    reduce: function(options) {
        return _.reduce(this.terms, function(memo, term) {
            return memo.mul(term, options);
        }, this.identity);
    },

    findGCD: function(factor) {
        return new Mul(_.invoke(this.terms, "findGCD", factor)).flatten();
    },

    asMul: function() {
        return this;
    },

    asPositiveFactor: function() {
        if (this.isPositive()) {
            return this;
        } else {
            var terms = _.invoke(this.collect().terms, "asPositiveFactor");
            return new Mul(terms).flatten();
        }
    },

    isNegative: function() {
        return _.any(_.invoke(this.collect().terms, "isNegative"));
    },

    fold: function() {
        return Mul.fold(this);
    },

    negate: function() {
        var isNum = function(expr) { return expr instanceof Num; };
        if (_.any(this.terms, isNum)) {
            var num = _.find(this.terms, isNum);
            return this.replace(num, num.negate());
        } else {
            return new Mul([Num.Neg].concat(this.terms));
        }
    }
});

// static methods for the sequence types
_.each([Add, Mul], function(type) {
    _.extend(type, {
        // create a new sequence unless left is already one (returns a copy)
        createOrAppend: function(left, right) {
            if (left instanceof type) {
                return new type(left.terms.concat(right));
            } else {
                return new type(left, right);
            }
        }
    });
});

_.extend(Mul, {
    // negative signs should be folded into numbers whenever possible
    // never fold into a Num that's already negative or a Mul that has a negative Num
    // an optional hint is kept track of to properly render user input
    // an empty hint means negation
    handleNegative: function(expr, hint) {
        if (expr instanceof Num && expr.n > 0) {
            // e.g. - 2 -> -2
            var negated = expr.negate();
            // TODO(alex): rework hint system so that this isn't necessary
            negated.hints = expr.hints;
            return negated.addHint(hint);
        } else if (expr instanceof Mul) {
            // e.g. - x*2*3 -> x*-2*3
            // e.g. - x*y -> -1*x*y
            // e.g. - x*-2 -> -1*x*-2
            return expr.factorIn(hint);
        } else {
            // e.g. - x -> -1*x
            return new Mul(Num.negativeOne(hint), expr);
        }
    },

    // division can create either a Rational or a Mul
    handleDivide: function(left, right) {

        // dividing by a Mul is the same as repeated division by its terms
        if (right instanceof Mul) {
            var first = Mul.handleDivide(left, right.terms[0]);
            var rest = new Mul(_.rest(right.terms)).flatten();
            return Mul.handleDivide(first, rest);
        }

        var isInt = function(expr) { return expr instanceof Int; };
        var isRational = function(expr) { return expr instanceof Rational; };

        // for simplification purposes, fold Ints into Rationals if possible
        // e.g. 3x / 4 -> 3/4 * x (will still render as 3x/4)
        if (isInt(right) && left instanceof Mul && _.any(left.terms, isInt)) {

            // search from the right
            var reversed = left.terms.slice().reverse();
            var num = _.find(reversed, isRational);

            if (!isInt(num)) {
                return new Mul(left.terms.concat([new Rational(1, right.n).addHint("fraction")]));
            }

            var rational = new Rational(num.n, right.n);
            rational.hints = num.hints;

            // in the case of something like 1/3 * 6/8, we want the
            // 6/8 to be considered a fraction, not just a division
            if (num === reversed[0]) {
                rational = rational.addHint("fraction");
            }

            var result;
            if (num.n < 0 && right.n < 0) {
                rational.d = -rational.d;
                return left.replace(num, [Num.Neg, rational]);
            } else {
                return left.replace(num, rational);
            }
        }

        var divide = function(a, b) {
            if (b instanceof Int) {
                if (a instanceof Int) {
                    if (a.n < 0 && b.n < 0) {
                        // e.g. -2 / -3 -> -1*-2/3
                        return [Num.Neg, new Rational(a.n, -b.n).addHint("fraction")];
                    } else {
                        // e.g. 2 / 3 -> 2/3
                        // e.g. -2 / 3 -> -2/3
                        // e.g. 2 / -3 -> -2/3
                        return [new Rational(a.n, b.n).addHint("fraction")];
                    }
                } else {
                    // e.g. x / 3 -> x*1/3
                    // e.g. x / -3 -> x*-1/3
                    var inverse = new Rational(1, b.eval());
                    if (b.eval() < 0) {
                        return [a, inverse.addHint("negate")];
                    } else {
                        return [a, inverse];
                    }
                }
            } else {
                var pow;

                if (b instanceof Trig && b.exp) {
                    // e.g. sin^2(x) -> sin(x)^2
                    var exp = b.exp;
                    b.exp = undefined;
                    b = new Pow(b, exp);
                }

                if (b instanceof Pow) {
                    // e.g. (x^2) ^ -1 -> x^-2
                    // e.g. (x^y) ^ -1 -> x^(-1*y)
                    // e.g. (x^(yz)) ^ -1 -> x^(-1*y*z)
                    pow = new Pow(b.base, Mul.handleNegative(b.exp, "divide"));
                } else {
                    // e.g. x ^ -1 -> x^-1
                    pow = new Pow(b, Num.Div);
                }

                if (a instanceof Int && a.n === 1) {
                    // e.g. 1 / x -> x^-1
                    return [pow];
                } else {
                    // e.g. 2 / x -> 2*x^-1
                    return [a, pow];
                }
            }
        };

        if (left instanceof Mul) {
            var divided = divide(_.last(left.terms), right);
            return new Mul(_.initial(left.terms).concat(divided));
        } else {
            var divided = divide(left, right);
            return new Mul(divided).flatten();
        }
    },

    // fold negative signs into numbers if possible
    // negative signs are not the same as multiplying by negative one!
    // e.g. -x      ->  -1*x    simplified
    // e.g. -2*x    ->  -2*x    simplified
    // e.g. -x*2    ->  -1*x*2  not simplified -> x*-2 simplified
    // e.g. -1*x*2  ->  -1*x*2  not simplified

    // also fold multiplicative terms into open Trig and Log nodes
    // e.g. (sin x)*x -> sin(x)*x
    // e.g. sin(x)*x -> sin(x)*x
    // e.g. sin(x)*(x) -> sin(x)*x
    // e.g. sin(x)*sin(y) -> sin(x)*sin(y)
    fold: function(expr) {
        if (expr instanceof Mul) {
            // assuming that this will be second to last
            var trigLog = _.find(_.initial(expr.terms), function(term) {
                return (term instanceof Trig || term instanceof Log) && term.hints.open;
            });
            var index = _.indexOf(expr.terms, trigLog);

            if (trigLog) {
                var last = _.last(expr.terms);
                if (trigLog.hints.parens || last.hints.parens ||
                          last.has(Trig) || last.has(Log)) {
                    trigLog.hints.open = false;
                } else {
                    var newTrigLog;
                    if (trigLog instanceof Trig) {
                        newTrigLog = Trig.create([trigLog.type, trigLog.exp], Mul.createOrAppend(trigLog.arg, last).fold());
                    } else {
                        newTrigLog = Log.create(trigLog.base, Mul.createOrAppend(trigLog.power, last).fold());
                    }

                    if (index === 0) {
                        return newTrigLog;
                    } else {
                        return new Mul(expr.terms.slice(0, index).concat(newTrigLog)).fold();
                    }
                }
            }

            var partitioned = expr.partition();
            var numbers = partitioned[0].terms;

            var pos = function(num) { return num.n > 0; };
            var neg = function(num) { return num.n === -1 && num.hints.negate; };
            var posOrNeg = function(num) { return pos(num) || neg(num); };

            if (numbers.length > 1 &&
                _.some(numbers, neg) &&
                _.some(numbers, pos) &&
                _.every(numbers, posOrNeg)) {

                var firstNeg = _.indexOf(expr.terms, _.find(expr.terms, neg));
                var firstNum = _.indexOf(expr.terms, _.find(expr.terms, pos));

                // e.g. -x*2 -> x*-2
                if (firstNeg < firstNum) {
                    return expr.replace(firstNum,
                                        expr.terms[firstNum].negate())
                               .remove(firstNeg);
                }
            }
        }

        // in all other cases, make no change
        return expr;
    }
});


/* exponentiation */
function Pow(base, exp) { this.base = base; this.exp = exp; }
Pow.prototype = new Expr();

_.extend(Pow.prototype, {
    func: Pow,
    args: function() { return [this.base, this.exp]; },

    eval: function(vars, options) {
        return Math.pow(this.base.eval(vars, options), this.exp.eval(vars, options));
    },

    codegen: function() {
        return "Math.pow(" + this.base.codegen() +
            ", " + this.exp.codegen() + ")";
    },

    print: function() {
        var base = this.base.print();
        if (this.base instanceof Seq || this.base instanceof Pow) {
            base = "(" + base + ")";
        }
        return base + "^(" + this.exp.print() + ")";
    },

    tex: function() {
        if (this.isDivide()) {

            // e.g. x ^ -1 w/hint -> 1/x
            return "\\frac{1}{" + this.asDivide().tex() + "}";

        } else if (this.isRoot()) {

            // e.g. x ^ 1/2 w/hint -> sqrt(x)
            return "\\sqrt{" + this.base.tex() + "}";

        } else if (this.base instanceof Trig && !this.base.isInverse() &&
            this.exp instanceof Num && this.exp.isSimple() &&
            this.exp.eval() >= 0) {

            // e.g sin(x) ^ 2 -> sin^2(x)
            var split = this.base.tex({split: true});
            return split[0] + "^{" + this.exp.tex() + "}" + split[1];

        } else {

            // e.g. x ^ y -> x^y
            var base = this.base.tex();
            if (this.base instanceof Seq || this.base instanceof Pow ||
                (this.base instanceof Num && !this.base.isSimple())) {
                // e.g. a+b ^ c -> (a+b)^c
                base = "(" + base + ")";
            } else if (this.base instanceof Trig || this.base instanceof Log) {
                // e.g. ln(x) ^ 2 -> [ln(x)]^2
                base = "[" + base + "]";
            }
            return base + "^{" + this.exp.tex() + "}";
        }
    },

    needsExplicitMul: function() {
        return this.isRoot() ? false : this.base.needsExplicitMul();
    },

    expand: function() {
        var pow = this.recurse("expand");

        if (pow.base instanceof Mul) {
            // e.g. (ab)^c -> a^c*b^c

            var terms = _.map(pow.base.terms, function(term) {
                return new Pow(term, pow.exp);
            });

            return new Mul(terms).expand();

        } else if (pow.base instanceof Add && pow.exp instanceof Int && pow.exp.abs().eval() > 1) {
            // e.g. (a+b)^2 -> a*a+a*b+a*b+b*b
            // e.g. (a+b)^-2 -> (a*a+a*b+a*b+b*b)^-1

            var positive = pow.exp.eval() > 0;
            var n = pow.exp.abs().eval();

            var signed = function(mul) {
                return positive ? mul : new Pow(mul, Num.Div);
            };

            // compute and cache powers of 2 up to n
            var cache = { 1: pow.base };
            for (var i = 2; i <= n; i *= 2) {
                var mul = new Mul(cache[i / 2], cache[i / 2]);
                cache[i] = mul.expand().collect();
            }

            // if n is a power of 2, you're done!
            if (_.has(cache, n)) {
                return signed(cache[n]);
            }

            // otherwise decompose n into powers of 2 ...
            var indices = _.map(n.toString(2).split(""), function(str, i, list) {
                return Number(str) * Math.pow(2, list.length - i - 1);
            });
            indices = _.without(indices, 0);

            // ... then combine
            var mul = new Mul(_.pick(cache, indices)).expand().collect();
            return signed(mul);

        } else if (pow.exp instanceof Add) { // DEFINITELY want behind super-simplify() flag
            // e.g. x^(a+b) -> x^a*x^b

            var terms = _.map(pow.exp.terms, function(term) {
                return new Pow(pow.base, term).expand();
            });

            return new Mul(terms).expand();
        } else {
            return pow;
        }
    },

    factor: function() {
        var pow = this.recurse("factor");
        if (pow.base instanceof Mul) {
            var terms = _.map(pow.base.terms, function(term) {
                if (term instanceof Int && pow.exp.equals(Num.Div)) {
                    // Anything that can be a Rational should be a Rational
                    // e.g. 2^(-1) -> 1/2
                    return new Rational(1, term.n);
                } else {
                    return new Pow(term, pow.exp);
                }
            });
            return new Mul(terms);
        } else {
            return pow;
        }
    },

    collect: function(options) {

        if (this.base instanceof Pow) {
            // collect this first to avoid having to deal with float precision
            // e.g. sqrt(2)^2 -> 2, not 2.0000000000000004
            // e.g. (x^y)^z -> x^(yz)
            var base = this.base.base;
            var exp = Mul.createOrAppend(this.base.exp, this.exp);
            return new Pow(base, exp).collect(options);
        }

        var pow = this.recurse("collect", options);

        var isSimilarLog = function(term) {
            return term instanceof Log && term.base.equals(pow.base);
        };

        if (pow.exp instanceof Num &&
            pow.exp.eval() === 0) {

            // e.g. x^0 -> 1
            return Num.One;

        } else if (pow.exp instanceof Num &&
            pow.exp.eval() === 1) {

            // e.g. x^1 -> x
            return pow.base;

        } else if (isSimilarLog(pow.exp)) {

            // e.g. b^(log_b(x)) -> x
            return pow.exp.power;

        } else if (pow.exp instanceof Mul &&
            _.any(pow.exp.terms, isSimilarLog)) {

            // e.g. b^(2*y*log_b(x)) -> x^(2*y)
            var log = _.find(pow.exp.terms, isSimilarLog);
            var base = log.power;
            var exp = pow.exp.remove(log).flatten();
            return new Pow(base, exp).collect(options);

        } else if (pow.base instanceof Num &&
            pow.exp instanceof Num) {

            // TODO(alex): Consider encapsualting this logic (and similar logic
            // elsewhere) into a separate Decimal class for user-entered floats
            if (options && options.preciseFloats) {
                // Avoid creating an imprecise float
                // e.g. 23^1.5 -> 12167^0.5, not ~110.304

                // If you take the root as specified by the denominator and
                // end up with more digits after the decimal point,
                // the result is imprecise. This works for rationals as well
                // as floats, but ideally rationals should be pre-processed
                // e.g. (1/27)^(1/3) -> 1/3 to avoid most cases.
                // TODO(alex): Catch such cases and avoid converting to floats.
                var exp = pow.exp.asRational();
                var decimalsInBase = pow.base.getDecimalPlaces();
                var root = new Pow(pow.base, new Rational(1, exp.d));
                var decimalsInRoot = root.collect().getDecimalPlaces();

                if (decimalsInRoot > decimalsInBase) {
                    // Collecting over this denominator would result in an
                    // imprecise float, so avoid doing so.
                    var newBase = new Pow(pow.base, new Int(exp.n)).collect();
                    return new Pow(newBase, new Rational(1, exp.d));
                }
            }

            // e.g. 4^1.5 -> 8
            return pow.base.raiseToThe(pow.exp, options);
        } else {
            return pow;
        }
    },

    // checks whether this Pow represents user-entered division
    isDivide: function() {
        var isDiv = function(arg) { return arg instanceof Num && arg.hints.divide; };
        return isDiv(this.exp) || (this.exp instanceof Mul && _.any(this.exp.terms, isDiv));
    },

    // assuming this Pow represents user-entered division, returns the denominator
    asDivide: function() {
        if (this.exp instanceof Num) {
            if (this.exp.eval() === -1) {
                return this.base;
            } else {
                var negated = this.exp.negate();
                negated.hints = _.clone(this.exp.hints);
                negated.hints.divide = false;
                return new Pow(this.base, negated);
            }
        } else if (this.exp instanceof Mul) {
            return new Pow(this.base, this.exp.factorOut());
        } else {
            error("called asDivide() on an Expr that wasn't a Num or Mul");
        }
    },

    isRoot: function() {
        return this.exp instanceof Num && this.exp.hints.root;
    },

    isSquaredTrig: function() {
        return this.base instanceof Trig && !this.base.isInverse() &&
            this.exp instanceof Num && this.exp.eval() === 2;
    },

    // extract whatever denominator makes sense, ignoring hints
    // if negative exponent, will recursively include the base's denominator as well
    getDenominator: function() {
        if (this.exp instanceof Num && this.exp.eval() === -1) {
            return Mul.createOrAppend(this.base, this.base.getDenominator()).flatten();
        } else if (this.exp.isNegative()) {
            var pow = new Pow(this.base, Mul.handleNegative(this.exp).collect());
            return Mul.createOrAppend(pow, pow.collect().getDenominator()).flatten();
        } else if (this.base instanceof Num) {
            return new Pow(this.base.getDenominator(), this.exp).collect();
        } else {
            return Num.One;
        }
    },

    findGCD: function(factor) {
        var base, exp;
        if (factor instanceof Pow) {
            base = factor.base;
            exp = factor.exp;
        } else {
            base = factor;
            exp = Num.One;
        }

        // GCD is only relevant if same base
        if (this.base.equals(base)) {
            if (this.exp.equals(exp)) {
                // exact match
                // e.g. GCD(x^y^z, x^y^z) -> x^y^z
                return this;
            } else if (this.exp instanceof Num && exp instanceof Num) {
                // two numerical exponents
                // e.g. GCD(x^3, x^2) -> x^2
                return new Pow(this.base, Num.min(this.exp, exp)).collect();
            } else if (this.exp instanceof Num || exp instanceof Num) {
                // one numerical exponent
                // e.g. GCD(x^2, x^y) -> 1
                return Num.One;
            }

            var expA = this.exp.asMul().partition();
            var expB = exp.asMul().partition();

            if (expA[1].equals(expB[1])) {
                // exponents match except for coefficient
                // e.g. GCD(x^3y, x^y) -> x^y
                var coefficient = Num.min(expA[0].reduce(), expB[0].reduce());
                var mul = new Mul(coefficient, expA[1].flatten()).flatten();
                return new Pow(base, mul).collect();
            }
        }

        return Num.One;
    },

    isPositive: function() {
        if (this.base.isPositive()) {
            return true;
        }

        var exp = this.exp.simplify();
        return exp instanceof Int && exp.eval() % 2 === 0;
    },

    asPositiveFactor: function() {
        if (this.isPositive()) {
            return this;
        } else {
            var exp = this.exp.simplify();
            if (exp instanceof Int) {
                var n = exp.eval();
                if (n > 2) {
                    // e.g. x^3 -> x^2
                    return new Pow(this.base, new Int(n-1));
                } else if (n < -2) {
                    // e.g. x^-3 -> x^-2
                    return new Pow(this.base, new Int(n+1));
                }
            }
            return Num.One;
        }
    }
});

_.extend(Pow, {
    sqrt: function(arg) {
        return new Pow(arg, Num.Sqrt);
    }
});


/* logarithm */
function Log(base, power) { this.base = base; this.power = power; }
Log.prototype = new Expr();

_.extend(Log.prototype, {
    func: Log,
    args: function() { return [this.base, this.power]; },

    eval: function(vars, options) {
        return Math.log(this.power.eval(vars, options)) / Math.log(this.base.eval(vars, options));
    },

    codegen: function() {
        return "(Math.log(" + this.power.codegen() +
            ") / Math.log(" + this.base.codegen() + "))";
    },

    print: function() {
        var power = "(" + this.power.print() + ")";
        if (this.isNatural()) {
            return "ln" + power;
        } else {
            return "log_(" + this.base.print() + ") " + power;
        }
    },

    tex: function() {
        var power = "(" + this.power.tex() + ")";
        if (this.isNatural()) {
            return "\\ln" + power;
        } else {
            return "\\log_{" + this.base.tex() + "}" + power;
        }
    },

    collect: function(options) {
        var log = this.recurse("collect", options);

        if (log.power instanceof Num && log.power.eval() === 1) {

            // e.g. ln(1) -> 0
            return Num.Zero;

        } else if (log.base.equals(log.power)) {

            // e.g. log_b(b) -> 1
            return Num.One;

        } else if (log.power instanceof Pow &&
            log.power.base.equals(log.base)) {

            // e.g. log_b(b^x) -> x
            return log.power.exp;
        } else {
            return log;
        }
    },

    expand: function() {
        var log = this.recurse("expand");

        if (log.power instanceof Mul) {  // might want behind super-simplify() flag
            // e.g. ln(xy) -> ln(x) + ln(y)

            var terms = _.map(log.power.terms, function(term) {
                // need to expand again in case new log powers are Pows
                return new Log(log.base, term).expand();
            });

            return new Add(terms);

        } else if (log.power instanceof Pow) {
            // e.g. ln(x^y) -> y*ln(x)

            return new Mul(log.power.exp, new Log(log.base, log.power.base).expand()).flatten();
        } else if (!log.isNatural()) {
            // e.g. log_b(x) -> ln(x)/ln(b)

            return Mul.handleDivide(new Log(Const.e, log.power), new Log(Const.e, log.base));
        } else {
            return log;
        }
    },

    hints: _.extend(Log.prototype.hints, {
        open: false
    }),

    isPositive: function() {
        var log = this.collect();

        if (log.base instanceof Num &&
            log.power instanceof Num) {
            return this.eval() > 0;
        } else {
            return false;
        }
    },

    needsExplicitMul: function() { return false; },

    isNatural: function() { return this.base.equals(Const.e); }
});

_.extend(Log, {
    natural: function() { return Const.e; },
    common: function() { return Num.Ten; },

    create: function(base, power) {
        var log = new Log(base, power);
        if (!power.hints.parens) {
            log = log.addHint("open");
        }
        return log;
    }
});


/* trigonometric functions */
function Trig(type, arg) { this.type = type; this.arg = arg; }
Trig.prototype = new Expr();

_.extend(Trig.prototype, {
    func: Trig,
    args: function() { return [this.type, this.arg]; },

    functions: {
        sin: {
            eval: Math.sin,
            codegen: "Math.sin((",
            tex: "\\sin",
            expand: function() { return this; }
        },
        cos: {
            eval: Math.cos,
            codegen: "Math.cos((",
            tex: "\\cos",
            expand: function() { return this; }
        },
        tan: {
            eval: Math.tan,
            codegen: "Math.tan((",
            tex: "\\tan",
            expand: function() {
                return Mul.handleDivide(Trig.sin(this.arg), Trig.cos(this.arg));
            }
        },
        csc: {
            eval: function(arg) { return 1 / Math.sin(arg); },
            codegen: "(1/Math.sin(",
            tex: "\\csc",
            expand: function() {
                return Mul.handleDivide(Num.One, Trig.sin(this.arg));
            }
        },
        sec: {
            eval: function(arg) { return 1 / Math.cos(arg); },
            codegen: "(1/Math.cos(",
            tex: "\\sec",
            expand: function() {
                return Mul.handleDivide(Num.One, Trig.cos(this.arg));
            }
        },
        cot: {
            eval: function(arg) { return 1 / Math.tan(arg); },
            codegen: "(1/Math.tan(",
            tex: "\\cot",
            expand: function() {
                return Mul.handleDivide(Trig.cos(this.arg), Trig.sin(this.arg));
            }
        },
        arcsin: {
            eval: Math.asin,
            codegen: "Math.asin((",
            tex: "\\arcsin"
        },
        arccos: {
            eval: Math.acos,
            codegen: "Math.acos((",
            tex: "\\arccos"
        },
        arctan: {
            eval: Math.atan,
            codegen: "Math.atan((",
            tex: "\\arctan"
        },
        arccsc: {
            eval: function(arg) { return Math.asin(1 / arg); },
            codegen: "Math.asin(1/(",
            tex: "\\operatorname{arccsc}"
        },
        arcsec: {
            eval: function(arg) { return Math.acos(1 / arg); },
            codegen: "Math.acos(1/(",
            tex: "\\operatorname{arcsec}"
        },
        arccot: {
            eval: function(arg) { return Math.atan(1 / arg); },
            codegen: "Math.atan(1/(",
            tex: "\\operatorname{arccot}"
        },
        sinh: {
            eval: function(arg) {
                return (Math.exp(arg) - Math.exp(-arg)) / 2;
            },
            codegen: function(argStr) {
                return "((Math.exp(" + argStr + ") - Math.exp(-(" + argStr + "))) / 2)";
            },
            tex: "\\sinh",
            expand: function() { return this; }
        },
        cosh: {
            eval: function(arg) {
                return (Math.exp(arg) + Math.exp(-arg)) / 2;
            },
            codegen: function(argStr) {
                return "((Math.exp(" + argStr + ") + Math.exp(-(" + argStr + "))) / 2)";
            },
            tex: "\\cosh",
            expand: function() { return this; }
        },
        tanh: {
            eval: function(arg) {
                return (Math.exp(arg) - Math.exp(-arg)) / (Math.exp(arg) + Math.exp(-arg));
            },
            codegen: function(argStr) {
                return "(" +
                    "(Math.exp(" + argStr + ") - Math.exp(-(" + argStr + ")))" +
                    " / " +
                    "(Math.exp(" + argStr + ") + Math.exp(-(" + argStr + ")))" +
                    ")";
            },
            tex: "\\tanh",
            expand: function() {
                return Mul.handleDivide(Trig.sinh(this.arg), Trig.cosh(this.arg));
            }
        },
        csch: {
            eval: function(arg) { return 2 / (Math.exp(arg) - Math.exp(-arg)); },
            codegen: function(argStr) {
                return "(2 / (Math.exp(" + argStr + ") - Math.exp(-(" + argStr + "))))";
            },
            tex: "\\csch",
            expand: function() {
                return Mul.handleDivide(Num.One, Trig.sinh(this.arg));
            }
        },
        sech: {
            eval: function(arg) { return 2 / (Math.exp(arg) + Math.exp(-arg)); },
            codegen: function(argStr) {
                return "(2 / (Math.exp(" + argStr + ") + Math.exp(-(" + argStr + "))))";
            },
            tex: "\\sech",
            expand: function() {
                return Mul.handleDivide(Num.One, Trig.cosh(this.arg));
            }
        },
        coth: {
            eval: function(arg) {
                return (Math.exp(arg) + Math.exp(-arg)) / (Math.exp(arg) - Math.exp(-arg));
            },
            codegen: function(argStr) {
                return "(" +
                    "(Math.exp(" + argStr + ") + Math.exp(-(" + argStr + ")))" +
                    " / " +
                    "(Math.exp(" + argStr + ") - Math.exp(-(" + argStr + ")))" +
                    ")";
            },
            tex: "\\coth",
            expand: function() {
                return Mul.handleDivide(Trig.cosh(this.arg), Trig.sinh(this.arg));
            }
        },
    },

    isEven: function() {
        return _.contains(["cos", "sec"], this.type);
    },

    isInverse: function() {
        return this.type.indexOf("arc") === 0;
    },

    isBasic: function() {
        return _.contains(["sin", "cos"], this.type);
    },

    eval: function(vars, options) {
        var func = this.functions[this.type].eval;
        var arg = this.arg.eval(vars, options);
        return func(arg);
    },

    codegen: function() {
        var func = this.functions[this.type].codegen;
        if (typeof func === "function") {
            return func(this.arg.codegen());
        } else if (typeof func === "string") {
            return func + this.arg.codegen() + "))";
        } else {
            throw new Error("codegen not implemented for " + this.type);
        }
    },

    print: function() {
        return this.type + "(" + this.arg.print() + ")";
    },

    tex: function(options) {
        var func = this.functions[this.type].tex;
        var arg = "(" + this.arg.tex() + ")";
        return (options && options.split) ? [func, arg] : func + arg;
    },

    hints: _.extend(Trig.prototype.hints, {
        open: false
    }),

    isPositive: function() {
        var trig = this.collect();

        if (trig.arg instanceof Num) {
            return this.eval() > 0;
        } else {
            return false;
        }
    },

    completeParse: function() {
        if (this.exp) {
            var pow = new Pow(this, this.exp);
            this.exp = undefined;
            return pow;
        } else {
            return this;
        }
    },

    // TODO(alex): does every new node type need to redefine these?
    needsExplicitMul: function() { return false; },

    expand: function() {
        var trig = this.recurse("expand");
        if (!trig.isInverse()) {
            // e.g. tan(x) -> sin(x)/cos(x)
            var expand = trig.functions[trig.type].expand;
            return _.bind(expand, trig)();
        } else {
            return trig;
        }
    },

    collect: function(options) {
        var trig = this.recurse("collect", options);
        if (!trig.isInverse() && trig.arg.isNegative()) {
            var arg;
            if (trig.arg instanceof Num) {
                arg = trig.arg.abs();
            } else {
                arg = Mul.handleDivide(trig.arg, Num.Neg).collect(options);
            }

            if (trig.isEven()) {
                // e.g. cos(-x) -> cos(x)
                return new Trig(trig.type, arg);

            } else {
                // e.g. sin(-x) -> -sin(x)
                return new Mul(Num.Neg, new Trig(trig.type, arg));
            }
        } else {
            return trig;
        }
    }
});

_.extend(Trig, {
    create: function(pair, arg) {
        var type = pair[0];
        var exp = pair[1];

        if (exp && exp.equals(Num.Neg)) {
            // e.g. sin^-1(x) -> arcsin(x)
            type = "arc" + type;
            exp = undefined;
        }

        var trig = new Trig(type, arg);
        if (!arg.hints.parens) {
            trig = trig.addHint("open");
        }

        if (exp) {
            trig.exp = exp;
        }

        return trig;
    },

    sin: function(arg) {
        return new Trig("sin", arg);
    },

    cos: function(arg) {
        return new Trig("cos", arg);
    },

    sinh: function(arg) {
        return new Trig("sinh", arg);
    },

    cosh: function(arg) {
        return new Trig("cosh", arg);
    }
});


function Abs(arg) { this.arg = arg; }
Abs.prototype = new Expr();

_.extend(Abs.prototype, {
    func: Abs,
    args: function() { return [this.arg]; },
    eval: function(vars, options) { return Math.abs(this.arg.eval(vars, options)); },
    codegen: function() { return "Math.abs(" + this.arg.codegen() + ")"; },
    print: function() { return "abs(" + this.arg.print() + ")"; },

    tex: function() {
        return "\\left|" + this.arg.tex() + "\\right|";
    },

    collect: function(options) {
        var abs = this.recurse("collect", options);

        if (abs.arg.isPositive()) {
            // e.g. |2^x| -> 2^x
            return abs.arg;
        } else if (abs.arg instanceof Num) {
            // e.g. |-2| -> 2
            return abs.arg.abs();
        } else if (abs.arg instanceof Mul) {
            // e.g. |-2*pi*x| -> 2*pi*|x|
            var terms = _.groupBy(abs.arg.terms, function(term) {
                if (term.isPositive()) {
                    return "positive";
                } else if (term instanceof Num) {
                    return "number";
                } else {
                    return "other";
                }
            });

            var positives = terms.positive.concat(_.invoke(terms.number, "abs"));

            if (terms.other.length) {
                positives.push(new Abs(new Mul(terms.other).flatten()));
            }

            return new Mul(positives).flatten();
        } else {
            return abs;
        }
    },

    // this should definitely be behind a super-simplify flag
    expand: function() {
        var abs = this.recurse("expand");

        if (abs.arg instanceof Mul) {
            // e.g. |xyz| -> |x|*|y|*|z|
            var terms = _.map(abs.arg.terms, function(term) {
                return new Abs(term);
            });
            return new Mul(terms);
        } else {
            return abs;
        }
    },

    isPositive: function() { return true; }
});


/* equation */
function Eq(left, type, right) {
    this.left = left;
    this.type = type;
    this.right = right;
}
Eq.prototype = new Expr();

_.extend(Eq.prototype, {
    func: Eq,
    args: function() { return [this.left, this.type, this.right]; },

    needsExplicitMul: function() { return false; },

    print: function() {
        return this.left.print() + this.type + this.right.print();
    },

    signs: {
        "=": " = ",
        "<": " < ",
        ">": " > ",
        "<>": " \\ne ",
        "<=": " \\le ",
        ">=": " \\ge "
    },

    tex: function() {
        return this.left.tex() + this.signs[this.type] + this.right.tex();
    },

    normalize: function() {
        var eq = this.recurse("normalize");

        if (_.contains([">", ">="], eq.type)) {
            // inequalities should have the smaller side on the left
            return new Eq(eq.right, eq.type.replace(">", "<"), eq.left);
        } else {
            return eq;
        }
    },

    // convert this equation to an expression set to zero
    // the expression is normalized to a canonical form
    // e.g. y/2=x/4 -> y/2-x/4(=0) -> 2y-x(=0)
    // unless unfactored is specified, will then divide through
    asExpr: function(unfactored) {

        var isZero = function(expr) {
            return expr instanceof Num && expr.isSimple() && expr.eval() === 0;
        };

        // first convert to a sequence of additive terms
        var terms = [];

        if (this.left instanceof Add) {
            terms = _.clone(this.left.terms);
        } else if (!isZero(this.left)) {
            terms = [this.left];
        }

        if (this.right instanceof Add) {
            terms = terms.concat(this.right.negate().terms);
        } else if (!isZero(this.right)) {
            terms.push(this.right.negate());
        }

        var isInequality = !this.isEquality();

        // Collect over each term individually to transform simple expressions
        // into numbers that might have denominators, taking into account
        // float precision. We have to be very careful to not introduce any
        // irrational floats before asExpr() returns, because by definition
        // they do not have exact denominators...
        terms = _.invoke(terms, "collect", {preciseFloats: true});

        // ...and we multiply through by every denominator.
        for (var i = 0; i < terms.length; i++) {
            var denominator = terms[i].getDenominator();

            // Can't multiply inequalities by non 100% positive factors
            if (isInequality && !denominator.isPositive()) {
                denominator = denominator.asPositiveFactor();
            }

            if (!denominator.equals(Num.One)) {
                terms = _.map(terms, function(term) {
                    return Mul.createOrAppend(term, denominator).simplify({
                        once: true,
                        preciseFloats: true
                    });
                });
            }
        }

        var add = new Add(terms).flatten();
        return unfactored ? add : this.divideThrough(add);
    },

    // divide through by every common factor in the expression
    // e.g. 2y-4x(=0) -> y-2x(=0)
    // TODO(alex): Make it an option to only divide by variables/expressions
    // guaranteed to be nonzero
    divideThrough: function(expr) {
        var isInequality = !this.isEquality();

        var simplified = expr.simplify({once: true});
        var factored = simplified.factor({keepNegative: isInequality});

        if (!(factored instanceof Mul)) {
            return expr;
        }

        var terms = factored.terms;

        var isAdd = function(term) { return term instanceof Add; };
        var hasVar = function(term) { return !!term.getVars().length; };
        var isOne = function(term) { return term.equals(Num.One); };

        var grouped = _.groupBy(terms, isAdd);
        var adds = grouped[true] || [];
        var others = grouped[false] || [];

        if (adds.length && this.isEquality()) {
            // keep only Adds
            // e.g. 2xy(z+1)(=0) -> z+1(=0)
            return new Mul(adds).flatten();
        }

        var denominator = others;

        if (!adds.length) {
            // if no Adds, keep all variable terms to preserve meaning
            // e.g. 42xyz(=0) -> xyz(=0)
            denominator = _.reject(denominator, hasVar);
        }

        if (isInequality) {
            // can't divide inequalities by non 100% positive factors
            // e.g. 42x^2y(z+1)(=0) -> y(z+1)(=0)
            denominator = _.invoke(denominator, "asPositiveFactor");
        }

        // don't need to divide by one
        denominator = _.reject(denominator, isOne);

        denominator = _.map(denominator, function(term) {
            return new Pow(term, Num.Div);
        });

        var dividedResult = new Mul(terms.concat(denominator)).collect();

        // If the end result is the same as the original factoring,
        // rollback the factoring and discard all intermediate steps.
        if (dividedResult.equals(factored)) {
            return simplified;
        } else {
            return dividedResult;
        }
    },

    isEquality: function() {
        return _.contains(["=", "<>"], this.type);
    },

    compare: function(other) {
        // expression comparisons are handled by Expr.compare()
        if (!(other instanceof Eq)) {
            return false;
        }

        var eq1 = this.normalize();
        var eq2 = other.normalize();

        if (eq1.type !== eq2.type) {
            return false;
        }

        // need to collect to properly factor out common factors
        // e.g x+2x=6 -> 3x=6 -> 3x-6(=0) -> x-2(=0)
        var expr1 = eq1.divideThrough(eq1.asExpr(/* unfactored */ true).collect());
        var expr2 = eq2.divideThrough(eq2.asExpr(/* unfactored */ true).collect());

        if (eq1.isEquality()) {
            // equals and not-equals can be subtracted either way
            return expr1.compare(expr2) ||
                   expr1.compare(Mul.handleNegative(expr2));
        } else {
            return expr1.compare(expr2);
        }
    },

    // should only be done after compare() returns true to avoid false positives
    sameForm: function(other) {
        var eq1 = this.normalize();
        var eq2 = other.normalize();

        var same = eq1.left.sameForm(eq2.left) && eq1.right.sameForm(eq2.right);

        if (eq1.isEquality()) {
            // equals and not-equals can be commutative with respect to the sign
            return same || (eq1.left.sameForm(eq2.right) && eq1.right.sameForm(eq2.left));
        } else {
            return same;
        }
    },

    // we don't want to override collect because it would turn y=x into y-x(=0)
    // instead, we ask if the equation was in that form, would it be simplified?
    isSimplified: function() {
        var expr = this.asExpr(/* unfactored */ true);
        var simplified = this.divideThrough(expr).simplify();
        return expr.equals(simplified) &&
               this.left.isSimplified() &&
               this.right.isSimplified();
    }
});


/* abstract symbol node */
function Symbol() {}
Symbol.prototype = new Expr();

_.extend(Symbol.prototype, {

    needsExplicitMul: function() { return false; },

    findGCD: function(factor) {
        if (factor instanceof Symbol || factor instanceof Num) {
            return this.equals(factor) ? this : Num.One;
        } else {
            return factor.findGCD(this);
        }
    }
});


/* function variable */
function Func(symbol, arg) {
    this.symbol = symbol; this.arg = arg;
}
Func.prototype = new Symbol();

_.extend(Func.prototype, {
    func: Func,
    args: function() { return [this.symbol, this.arg]; },

    print: function() {
        return this.symbol + "(" + this.arg.print() + ")";
    },

    tex: function() {
        return this.symbol + "(" + this.arg.tex() + ")";
    },

    eval: function(vars, options) {
        var arg = this.arg;
        var func = vars[this.symbol];
        var newVars = _.extend(_.clone(vars), {
            x: arg.eval(vars, options)
        });
        var parsedFunc = KAS.parse(func, options);
        if (parsedFunc.parsed) {
            return parsedFunc.expr.eval(newVars, options);
        }
        // If parsedFunc isn't actually parsed, return its error
        return parsedFunc;
    },

    codegen: function() {
        return 'vars["' + this.symbol + '"](' +
            this.arg.codegen() + ')';
    },

    getVars: function(excludeFunc) {
        if (excludeFunc) {
            return this.arg.getVars();
        } else {
            return _.union(this.arg.getVars(), [this.symbol]).sort();
        }
    }
});


/* variable */
function Var(symbol, subscript) {
    this.symbol = symbol;
    this.subscript = subscript;
}
Var.prototype = new Symbol();

_.extend(Var.prototype, {
    func: Var,
    args: function() { return [this.symbol, this.subscript]; },

    exprArgs: function() { return []; },
    recurse: function() { return this; },

    print: function() {
        var sub = "";
        if (this.subscript) {
            sub = "_(" + this.subscript.print() + ")";
        }
        return this.symbol + sub;
    },

    // Provide a way to easily evalate expressions with the common case,
    // subscripts that consist of a single number or symbol e.g. x_a or x_42
    prettyPrint: function() {
        var sub = this.subscript;
        if (sub && (sub instanceof Num || sub instanceof Symbol)) {
            return this.symbol + "_" + sub.print();
        } else {
            return this.print();
        }
    },

    tex: function() {
        var sub = "";
        if (this.subscript) {
            sub = "_{" + this.subscript.tex() + "}";
        }
        var prefix = this.symbol.length > 1 ? "\\" : "";
        return prefix + this.symbol + sub;
    },

    repr: function() { return "Var(" + this.print() + ")"; },

    eval: function(vars, options) {
        return vars[this.prettyPrint()];
    },

    codegen: function() {
        return 'vars["' + this.prettyPrint() + '"]';
    },

    getVars: function() { return [this.prettyPrint()]; },

    isPositive: function() { return false; }
});


/* constant */
function Const(symbol) { this.symbol = symbol; }
Const.prototype = new Symbol();

_.extend(Const.prototype, {
    func: Const,
    args: function() { return [this.symbol]; },
    recurse: function() { return this; },

    eval: function(vars, options) {
        if (this.symbol === "pi") {
            return Math.PI;
        } else if (this.symbol === "e") {
            return Math.E;
        }
    },

    codegen: function() {
        if (this.symbol === "pi") {
            return "Math.PI";
        } else if (this.symbol === "e") {
            return "Math.E";
        }
    },

    print: function() { return this.symbol; },

    tex: function() {
        if (this.symbol === "pi") {
            return "\\pi ";
        } else if (this.symbol === "e") {
            return "e";
        }
    },

    isPositive: function() {
        return this.eval() > 0;
    },

    abs: function() {
        if (this.eval() > 0) {
            return this;
        } else {
            return Mul.handleNegative(this);
        }
    }
});

Const.e = new Const("e");
Const.pi = new Const("pi");


/* abstract number node */
function Num() {}
Num.prototype = new Expr();

_.extend(Num.prototype, {
    repr: function() { return this.print(); },
    strip: function() { return this.abs(); },
    recurse: function() { return this; },
    codegen: function() { return this.print(); },

    // takes another Num and returns a new Num
    add: abstract,
    mul: abstract,

    // returns this Num's additive inverse
    negate: abstract,

    isSubtract: function() { return this.hints.subtract; },

    // return the absolute value of the number
    abs: abstract,

    needsExplicitMul: function() { return true; },

    findGCD: abstract,

    isPositive: function() {
        return this.eval() > 0;
    },

    isNegative: function() {
        return this.eval() < 0;
    },

    asPositiveFactor: function() {
        return this.isPositive() ? this : this.abs();
    },

    // hints for interpreting and rendering user input
    hints: _.extend(Num.prototype.hints, {
        negate: false,
        subtract: false,
        divide: false,
        root: false,
        fraction: false,
        entered: false
    }),

    // whether a number is considered simple (one term)
    // e.g. for reals, ints and floats are simple
    isSimple: abstract,

    // Based on http://stackoverflow.com/a/10454560/2571482
    getDecimalPlaces: function() {
        var match = ("" + this.n).match(/(?:\.(\d+))?(?:[eE]([+-]?\d+))?$/);
        if (match) {
            return Math.max(
                0,
                // Number of digits right of decimal point
                (match[1] ? match[1].length : 0) -
                // Adjust for scientific notation
                (match[2] ? +match[2] : 0)
            );
        } else {
            return 0;
        }
    },

    asRational: abstract
});


/* rational number (n: numerator, d: denominator) */
function Rational(numerator, denominator) {
    var n = numerator; var d = denominator;
    if (d < 0) {
        n = -n; d = -d;
    }
    this.n = n; this.d = d;
}
Rational.prototype = new Num();

_.extend(Rational.prototype, {
    func: Rational,
    args: function() { return [this.n, this.d]; },
    eval: function() { return this.n / this.d; },

    print: function() {
        return this.n.toString() + "/" + this.d.toString();
    },

    tex: function() {
        var tex = "\\frac{" + Math.abs(this.n).toString() + "}{" + this.d.toString() + "}";
        return this.n < 0 ? "-" + tex : tex;
    },

    add: function(num, options) {
        if (num instanceof Rational) {
            return new Rational(this.n * num.d + this.d * num.n, this.d * num.d).collect();
        } else {
            return num.add(this, options);
        }
    },

    mul: function(num, options) {
        if (num instanceof Rational) {
            return new Rational(this.n * num.n, this.d * num.d).collect();
        } else {
            return num.mul(this, options);
        }
    },

    collect: function() {
        var gcd = Num.findGCD(this.n, this.d);

        var n = this.n / gcd;
        var d = this.d / gcd;

        if (d === 1) {
            return new Int(n);
        } else {
            return new Rational(n, d);
        }
    },

    negate: function() {
        return new Rational(-this.n, this.d);
    },

    abs: function() {
        return new Rational(Math.abs(this.n), this.d);
    },

    findGCD: function(factor) {
        // Attempt to factor out common numerators and denominators to return
        // a Rational instead of a Float
        if (factor instanceof Rational) {
            // For more background, see
            // http://math.stackexchange.com/questions/151081/gcd-of-rationals
            var numerator = Num.findGCD(this.n * factor.d, factor.n * this.d);
            var denominator = this.d * factor.d;
            // Create the rational, then call .collect() to simplify it
            return new Rational(numerator, denominator).collect();
        } else if (factor instanceof Int) {
            return new Rational(Num.findGCD(this.n, factor.n), this.d);
        } else {
            return factor.findGCD(this);
        }
    },

    // for now, assuming that exp is a Num
    raiseToThe: function(exp) {
        if (exp instanceof Int) {
            var positive = exp.eval() > 0;
            var abs = exp.abs().eval();
            var n = Math.pow(this.n, abs);
            var d = Math.pow(this.d, abs);
            if (positive) {
                return new Rational(n, d).collect();
            } else {
                return new Rational(d, n).collect();
            }
        } else {
            return new Float(this.eval()).raiseToThe(exp);
        }
    },

    getDenominator: function() {
        return new Int(this.d);
    },

    isSimple: function() { return false; },

    asRational: function() { return this; }
});


/* integer (n: numerator/number) */
function Int(number) { this.n = number; }
Int.prototype = new Rational(0, 1);

_.extend(Int.prototype, {
    func: Int,
    args: function() { return [this.n]; },
    print: function() { return this.n.toString(); },
    tex: function() { return this.n.toString(); },
    negate: function() { return new Int(-this.n); },
    abs: function() { return new Int(Math.abs(this.n)); },
    isSimple: function() { return true; },
    findGCD: function(factor) {
        if (factor instanceof Int) {
            return new Int(Num.findGCD(this.n, factor.n));
        } else {
            return factor.findGCD(this);
        }
    }
});

_.extend(Int, {
    create: function(n) { return new Int(n).addHint("entered"); }
});

/* float (n: number) */
function Float(number) { this.n = number; }
Float.prototype = new Num();

_.extend(Float.prototype, {
    func: Float,
    args: function() { return [this.n]; },
    eval: function() { return this.n; },

    // TODO(alex): when we internationalize number parsing/display
    // we should make sure to use the appropriate decimal mark here
    print: function() { return this.n.toString(); },
    tex: function() { return this.n.toString(); },

    add: function(num, options) {
        if (options && options.preciseFloats) {
            return Float.toDecimalPlaces(
                this.n + num.eval(),
                Math.max(this.getDecimalPlaces(), num.getDecimalPlaces())
            );
        } else {
            return new Float(this.n + num.eval()).collect();
        }
    },

    mul: function(num, options) {
        if (options && options.preciseFloats) {
            return Float.toDecimalPlaces(
                this.n * num.eval(),
                this.getDecimalPlaces() + num.getDecimalPlaces()
            );
        } else {
            return new Float(this.n * num.eval()).collect();
        }
    },

    collect: function() {
        var floor = Math.floor(this.n);
        if (this.n === floor) {
            return new Int(floor);
        } else {
            return this;
        }
    },

    negate: function() { return new Float(-this.n); },
    abs: function() { return new Float(Math.abs(this.n)); },

    findGCD: function(factor) {
        if (factor instanceof Num) {
            return new Float(Num.findGCD(this.eval(), factor.eval())).collect();
        } else {
            return factor.findGCD(this);
        }
    },

    // for now, assuming that exp is a Num
    raiseToThe: function(exp, options) {
        if (options && options.preciseFloats &&
                exp instanceof Int && exp.n > 1) {
            return Float.toDecimalPlaces(
                Math.pow(this.n, exp.n),
                this.getDecimalPlaces() * exp.n
            );
        } else {
            return new Float(Math.pow(this.n, exp.eval())).collect();
        }
    },

    // only to be used on non-repeating decimals (e.g. user-provided)
    asRational: function() {
        var parts = this.n.toString().split(".");
        var numerator = Number(parts.join(""));
        var denominator = Math.pow(10, parts[1].length);
        return new Rational(numerator, denominator).collect();
    },

    getDenominator: function() {
        return this.asRational().getDenominator();
    },

    isSimple: function() { return true; }
});

_.extend(Float, {
    create: function(n) { return new Float(n).addHint("entered"); },

    // Account for floating point imprecision by explicitly controlling the
    // number of decimal places in common operations (e.g. +, *, ^)
    toDecimalPlaces: function(n, places) {
        return new Float(+n.toFixed(Math.min(places, 20))).collect();
    }
});

// static methods and fields that are best defined on Num
_.extend(Num, {
    negativeOne: function(hint) {
        if (hint === "subtract") {
            return Num.Sub;
        } else if (hint === "divide") {
            return Num.Div;
        } else {
            return Num.Neg;
        }
    },

    // find the greatest common denominator
    findGCD: function(a, b) {
        var mod;

        a = Math.abs(a);
        b = Math.abs(b);

        // Euclid's method doesn't handle non-integers very well. For now
        // we just say we can't pull out a common factor. It might be
        // reasonable to do better than this in the future.
        if (a !== Math.floor(a) || b !== Math.floor(b)) {
            return 1;
        }

        while (b) {
            mod = a % b;
            a = b;
            b = mod;
        }

        return a;
    },

    min: function() {
        return _.min(_.toArray(arguments), function(num) {
            return num.eval();
        });
    },

    max: function() {
        return _.max(_.toArray(arguments), function(num) {
            return num.eval();
        });
    }
});

Num.Neg = new Int(-1).addHint("negate");
Num.Sub = new Int(-1).addHint("subtract");
Num.Div = new Int(-1).addHint("divide");

Num.Sqrt = new Rational(1, 2).addHint("root");

Num.Zero = new Int(0);
Num.One = new Int(1);
Num.Ten = new Int(10);


// set identities here
Add.prototype.identity = Num.Zero;
Mul.prototype.identity = Num.One;


var parser = KAS.parser;

var parseError = function(str, hash) {
    // return int location of parsing error
    throw new Error(hash.loc.first_column);
};

// expose concrete nodes to parser scope
// see http://zaach.github.io/jison/docs/#sharing-scope
parser.yy = {
    Add: Add,
    Mul: Mul,
    Pow: Pow,
    Log: Log,
    Trig: Trig,
    Eq: Eq,
    Abs: Abs,
    Func: Func,
    Const: Const,
    Var: Var,
    Int: Int,
    Float: Float,
    parseError: parseError,

    constants: ["e"],
    symbolLexer: function(symbol) {
        if (_.contains(parser.yy.constants, symbol)) {
            return "CONST";
        } else if (_.contains(parser.yy.functions, symbol)) {
            return "FUNC";
        } else {
            return "VAR";
        }
    }
};

KAS.parse = function(input, options) {
    try {
        if (options && options.functions) {
            // reserve the symbol "i" for complex numbers
            parser.yy.functions = _.without(options.functions, "i");
        } else {
            parser.yy.functions = [];
        }

        // If ',' is the decimal dividor in your country, replace any ','s
        // with '.'s.
        // This isn't perfect, since the output will all still have '.'s.
        // TODO(jack): Fix the output to have ','s in this case
        if (options && options.decimal_separator) {
            input = input.split(options.decimal_separator).join(".");
        }

        var expr = parser.parse(input).completeParse();
        return { parsed: true, expr: expr };
    } catch (e) {
        return { parsed: false, error: e.message };
    }
};

})(KAS);

(function(KAS) {

// assumes that both expressions have already been parsed
// TODO(alex): be able to pass a random() function to compare()
KAS.compare = function(expr1, expr2, options) {
    var defaults = {
        form: false,        // check that the two expressions have the same form
        simplify: false     // check that the second expression is simplified
    };

    /* more possible options:
        allow ratios e.g. 3/1 and 3 should both be accepted for something like slope
        allow student to choose their own variables names
    */

    if (options !== undefined) {
        options = _.extend(defaults, options);
    } else {
        options = defaults;
    }

    // variable check
    var vars = expr1.sameVars(expr2);
    if (!vars.equal) {
        var message = null;
        if (vars.equalIgnoringCase) {
            message = "Some of your variables are in the wrong case (upper vs. lower).";
        }
        return {equal: false, message: message};
    }

    // semantic check
    if (!expr1.compare(expr2)) {
        return {equal: false, message: null};
    }

    // syntactic check
    if (options.form && !expr1.sameForm(expr2)) {
        return {equal: false, message: "Your answer is not in the correct form."};
    }

    // syntactic check
    if (options.simplify && !expr1.isSimplified()) {
        return {equal: false, message: "Your answer is not fully expanded and simplified."};
    }

    return {equal: true, message: null};
};

})(KAS);
