"use strict"; // Opt out of sloppy mode.
/** The Expr constructor function. */
function Expr(tokens, value, parenthesized) {
this.toArray = () => tokens; // The ordered tokens (terms and operands).
this.valueOf = () => value; // The value of the expression.
this.toString = () => parenthesized; // The expression with parentheses.
}
/** Evaluates an unparenthesized expression. */
Expr.eval = function(expr, type, startIndex, upperBound) { // INPUT: An expression specification.
const tokens = Expr.parseTokens(expr);
const lower = (startIndex === undefined) ? 0 : startIndex;
const upper = (upperBound === undefined) ? tokens.length : upperBound;
const ops = (type === "boolean") ? Expr.booleanOps : Expr.numericOps;
type = ops.type(); // Type will be "numeric" or "boolean".
if (upper - lower === 1) {
const token = tokens[lower]; let tokenValue; // CASE 1. There is only one term.
if (ops.tokenMapContainsKey(token)) // The term might be an operator.
tokenValue = ops.tokenMap[token].apply(); // If so, the operation takes no arguments.
else tokenValue = ops.parse(token); // Otherwise, the term is a literal.
return new Expr(tokens, tokenValue, token); // OUTPUT: A new Expr object.
}
for (let p = ops.MIN_PREC; p <= ops.MAX_PREC; p++) { // Repeat for each precedence level.
let j = -1;
for (let i = upper - 1; i >= lower; i--) { // Inspect tokens from right to left.
const token = tokens[i]; // Get the next token.
if (!ops.tokenMapContainsKey(token)) continue; // Token is not an operator. About.
const op = ops.tokenMap[token]; // Token is an operator. Get the operation.
if (op.precedence() !== p) continue; // Wrong precedence level. Abort.
if (op.lhsIsArg() && !op.rhsIsArg()) { // CASE 2. Operator takes 1 arg on LHS.
const lhs = Expr.eval(tokens, type, lower, i); // Evaluate the subexpression on the left.
return new Expr(tokens, // OUTPUT: An object containing the tokens,
op.apply(lhs.valueOf()), // the value of the expression, and
"(" + lhs.toString() + " " + token + ")"); // the parenthesized expression.
} else if (!op.lhsIsArg() && op.rhsIsArg()) { // CASE 3. Operator takes 1 arg on RHS.
j = i;
const rhs = Expr.eval(tokens, type, i + 1, upper); // Evaluate the subexpression on the right.
return new Expr(tokens, // OUTPUT: An object containing the tokens,
op.apply(rhs.valueOf()), // the value of the expression, and
"(" + token + " " + rhs.toString() + ")"); // the parenthesized expression.
} else if (op.lhsIsArg() && op.rhsIsArg()) { // CASE 4. Operator takes 2 args (LHS & RHS).
const lhs = Expr.eval(tokens, type, lower, i); // Evaluate the subexpression on the left.
const rhs = Expr.eval(tokens, type, i + 1, upper); // Evaluate the subexpression on the right.
return new Expr(tokens, // OUTPUT: An object containing the tokens,
op.apply(lhs.valueOf(), rhs.valueOf()), // the value of the expression, and
"(" + lhs.toString() + " " + token + // the parenthesized expression.
" " + rhs.toString() + ")");
}
}
if (j >= 0) {
const token = tokens[j], op = ops.tokenMap[token];
const rhs = Expr.eval(tokens, type, j + 1, upper);
return new Expr(tokens, op.apply(rhs.valueOf()),
"(" + token + " " + rhs.toString() + ")");
}
}
}
/** Converts various types of input into tokens (a frozen array of strings). */
Expr.parseTokens = function(input) {
if (Array.isArray(input)) return toStrings(input);
else if (typeof input === "string") return toStrings(input.split(" "));
else if (Number.isFinite(input)) return toStrings([input]);
else if (input instanceof Expr) return toStrings(input.toArray());
else if (input === true || input === false) return toStrings([input]);
throw Error("Invalid expression");
function toStrings(array) { // Returns a frozen array of strings.
const strings = [];
array.forEach((element) => strings.push(element.toString()));
return Object.freeze(strings);
}
};
/** Produces an array of tokens representing a Boolean or numeric expression. */
Expr.random = function(n, type) { // The expression will contain at least n operators.
const bagSize = (Number.isInteger(n) && n > 0) ? n : Expr.random.DEFAULT_SIZE;
if (type !== "boolean") type = "numeric";
const ops = (type === "boolean") ? Expr.booleanOps : Expr.numericOps;
// PART I. COLLECT RANDOM TOKENS
let bag = [], terms = [randomTerm()]; // Start with zero operations and one term.
while (bag.length < bagSize) { // Repeat until the bag of operations is full:
const op = ops.random(); // 1. Get the next random operation.
const lhsIsArg = op.lhsIsArg(); // a) Note whether an operand is needed on the left.
const rhsIsArg = op.rhsIsArg(); // b) Note whether an operand is needed on the right.
if (lhsIsArg && rhsIsArg) { // 2. If operands are needed on both sides,
terms.unshift(randomTerm()); // then add another term to the pile of terms,
bag.push(op); // and store the operation in the bag.
} // (Put literals at the bottom of the bag.)
else if (!(lhsIsArg || rhsIsArg)) // 3. If no operands are required, then
terms.push(op.operator()); // the operation's operator will function as a term.
else // 4. Otherwise, exactly one operand is needed,
bag.push(op); // which we have, so we only store the operation.
} // PART II. SEQUENCE THE TOKENS
let tokens = [], isComplete = false; // Initially, the expression is empty; it's incomplete.
while (bag.length > 0) { // Repeat until the bag of operation objects is empty:
const op = bag.pop(); // 1. Take an object out of the bag of operations.
const lhsIsArg = op.lhsIsArg(); // a) Note whether an operand is needed on the left.
const rhsIsArg = op.rhsIsArg(); // b) Note whether an operand is needed on the right.
if (lhsIsArg) { // 2. If an operand is needed on the left,
if (!isComplete) // and if the expression is not complete,
tokens.push(terms.pop()); // then we append a term to complete it.
tokens.push(op.operator()); // Next, append the operator token.
isComplete = !rhsIsArg; // The expression is complete if and only if a RHS
} // operand is not required.
else if (rhsIsArg) { // 3. But if we need a RHS (not a LHS) operand,
if (!isComplete) // and if the expression is not complete,
tokens.push(op.operator()); // then we append the operator (we put it at the end);
else // however, if the expression is complete,
tokens.unshift(op.operator()); // then we put the operator at the beginning instead.
}
} // PART III. TERMINATE
if (!isComplete) tokens.push(terms.pop()); // If needed, add a term to terminate the series.
return tokens; // Return tokens representing a valid expression.
function randomTerm() {
if (type === "boolean") return Math.random() < 0.5 ? "true" : "false";
else return Math.floor(Expr.random.MIN_TERM +
Math.random() * Expr.random.MAX_TERM - Expr.random.MIN_TERM);
};
};
Expr.random.MIN_TERM = -9;
Expr.random.MAX_TERM = 10;
Expr.random.DEFAULT_SIZE = 8;
(function() { // Anonymous IIFE (Immediately Invoked Function Expression)
function Operation(oper, prec, lhsIsArg, rhsIsArg, func) {
this.operator = () => oper;
this.precedence = () => prec;
this.apply = func;
this.lhsIsArg = () => lhsIsArg;
this.rhsIsArg = () => rhsIsArg;
}
function getOps(type) {
const Operations = (type === "boolean") ? [
new Operation("&&", 0, true, true, (a, b) => MyMath.logical.and(a, b)),
new Operation("||", 0, true, true, (a, b) => MyMath.logical.or(a, b)),
new Operation("!", 1, false, true, (b) => MyMath.logical.not(b))
] : (type === "numeric") ? [
new Operation("+", 0, true, true, (a, b) => MyMath.add(a, b)),
new Operation("-", 0, true, true, (a, b) => MyMath.sub(a, b)),
new Operation("*", 1, true, true, (a, b) => MyMath.mul(a, b)),
new Operation("/", 1, true, true, (a, b) => MyMath.div(a, b)),
new Operation("%", 1, true, true, (a, b) => MyMath.rem(a, b)),
new Operation("^", 2, true, true, (a, b) => MyMath.pow(a, b)),
new Operation("!", 3, true, false, (a) => MyMath.factorial(a)),
new Operation("neg", 3, false, true, (b) => MyMath.neg(b)),
new Operation("sin", 3, false, true, (b) => MyMath.sin(b)),
new Operation("cos", 3, false, true, (b) => MyMath.cos(b)),
new Operation("PI", 4, false, false, () => MyMath.pi())
] : undefined;
Operations.MIN_PREC = (function() {
let min = undefined;
Operations.forEach(function(op) {
const p = op.precedence();
if (min == undefined || p < min) min = p;
});
return min;
})();
Operations.MAX_PREC = (function() {
let max = undefined;
Operations.forEach(function(op) {
const p = op.precedence();
if (max == undefined || p > max) max = p;
});
return max;
})();
Operations.type = () => type === "boolean" ? "boolean" : "numeric";
Operations.parse = (type === "numeric") ?
parseFloat : (b) => b.toString() === "true";
Operations.random = function() {
const r = Math.random() * Operations.length;
const i = Math.floor(r);
return Operations[i];
};
Operations.tokenMap = {};
Operations.forEach(function(op) { Operations.tokenMap[op.operator()] = op; });
Operations.tokenMapContainsKey = (key) => Operations.tokenMap[key] !== undefined;
return Object.freeze(Operations);
};
Expr.numericOps = getOps("numeric");
Expr.booleanOps = getOps("boolean");
})();
Expr.evalBoolean = (e) => Expr.eval(e, "boolean");
Expr.evalNumeric = (e) => Expr.eval(e, "numeric");
Expr.randomBoolean = (n) => Expr.random(n, "boolean");
Expr.randomNumeric = (n) => Expr.random(n, "numeric");
Object.freeze(Expr);
const MyMath = Object.freeze({
pi: function() { return Math.PI; },
neg: function(b) { return -b; },
sin: function(b) { return Math.sin(b); },
cos: function(b) { return Math.cos(b); },
factorial: function(a) {
if (a < 0 || !Number.isInteger(a))
return -1;
else if (a === 0)
return 1;
else
return a * MyMath.factorial(a - 1);
},
pow: function(a, b) { return Math.pow(a, b); },
mul: function(a, b) { return a * b; },
div: function(a, b) { return a / b; },
rem: function(a, b) { return a % b; },
add: function(a, b) { return a + b; },
sub: function(a, b) { return a - b; },
logical: {
and: function(a, b) { return a && b; },
or: function(a, b) { return a || b; },
not: function(b) { return !b; }
}
});
/* EXERCISES
*
* 1. Describe and give examples of the following terms and phrases: literal, variable, operation,
* operator, operand, argument, parameter, arity of operation, nullary operation, unary operator,
* binary operator, ternary operator, prefix, infix, postfix, expression, term, precedence,
* order of operations.
*
* 2.
*
* n. Expr.eval is defective. Find the bug and try to fix it.
*
*/