Here is an equation parser that I just wrote. My focus was on readability and the prospect of adding new features in the future. Since I like a somewhat functional style, I also gave type annotations, especially for the more complex cases. I do know that this is not purely functional, and that was by no means the aim of this program. I did however keep the top-level functions completely pure, or at least I hope so.
"use strict";
Object.defineProperties(Array.prototype, {
head: { get() { return this[0] } },
tail: { get() { return this.slice(1, this.length) } },
last: { get() { return this[this.length - 1] } },
init: { get() { return this.slice(0, this.length - 1) } },
})
const id = x => x
const pipe = (...fns) => arg => fns.reduce((stack, f) => f(stack), arg)
const FN = {
/** trigonometric functions **/
sin: f => Math.sin(f),
cos: f => Math.cos(f),
tan: f => Math.tan(f),
sinh: f => Math.sinh(f),
cosh: f => Math.cosh(f),
tanh: f => Math.tanh(f),
asin: f => Math.asin(f),
acos: f => Math.acos(f),
atan: f => Math.atan(f),
asinh: f => Math.asinh(f),
acosh: f => Math.acosh(f),
atanh: f => Math.atanh(f),
deg: f => f * 180/Math.PI,
rad: f => f * Math.PI/180,
/** exponentiation etc. **/
exp: f => Math.exp(f),
ln: f => Math.log(f),
lg: f => Math.log10(f),
sqrt: f => Math.sqrt(f),
/** misc **/
fac: i => {
if (i !== Math.trunc(i)) { return undefined }
const __fac = _i => _i === 0 ? 1 : _i * __fac(_i - 1)
return __fac(i)
},
}
const CONST = {
e: Math.E,
pi: Math.PI,
}
// --------------------------- equation linter ------------------------------ //
// :: String -> String
const lintEqn = s => {
const startWithPlus = s => s.replace(/($|\()(.)/g, `1ドル + 2ドル`)
const condenseOperators = s => {
while (/[\+\-]\s*[\+\-]/.test(s)) {
s = s.replace(/\-\s*\-|\+\s*\+/g, '+')
.replace(/\-\s*\+|\+\s*\-/g, '-')
}
return s
}
const separateTokens = s => s.split('').reduce(
(acc, char) => /[\+\-\*\/\^\(\)]/.test(char) ? acc + ` ${char} ` : acc + char
, '').replace(/\s+/g, ' ')
const trimWhiteSpace = s => s.replace(/^\s*|\s*$/g, '')
return pipe(
startWithPlus,
condenseOperators,
separateTokens,
trimWhiteSpace,
)('+' + s)
}
// ------------------------------ main logic -------------------------------- //
// :: String -> StkTree
// StkTree = [{op: String, num: StkBranch, fns[(Num -> Num)]}]
// StkBranch = Num | StkTree
const buildStackTree = s => {
const isFloat = s => /^ *-?\d+(\.\d+)?([eE][+-]?\d+)? *$/.test(s)
const isConst = s => CONST.hasOwnProperty(s)
const isDeg = s => /^\d+(\.\d+)?°$/.test(s)
const isOp = c => /^[\+\-\*\/\^]$/.test(c)
const isFn = s => FN.hasOwnProperty(s)
const freshStack = () => ({
op: undefined,
num: undefined,
fns: [id],
})
const acc = {
tree: [freshStack()],
targets: [],
}
acc.targets.push(acc.tree)
return s.split(' ').reduce(({tree, targets}, tkn) => {
const tgtTree = targets.last
if (tgtTree.last.num !== undefined) {
tgtTree.push(freshStack())
}
const tgtStk = tgtTree.last
if (isOp(tkn)) {
if (!tgtStk.op) {
tgtStk.op = tkn
} else {
throw new Error(`Redundant operator: ${tkn}`)
}
} else if (isFloat(tkn)) {
tgtStk.num = (parseFloat(tkn))
} else if (isFn(tkn)) {
tgtStk.fns.unshift(FN[tkn])
} else if (isConst(tkn)) {
tgtStk.num = CONST[tkn]
} else if (isDeg(tkn)) {
tgtStk.num = CONST.pi * parseFloat(tkn) / 180
/** increase Nesting **/
} else if (tkn === '(') {
const newBranch = [freshStack()]
tgtStk.num = newBranch
targets.push(newBranch)
/** decrease Nesting **/
} else if (tkn === ')') {
if (tgtStk.op || tgtStk.num || tgtStk.fns.length > 1) {
throw new Error (`Denesting with unfinished operation`)
}
tgtTree.pop()
targets.pop()
} else {
throw new Error(`Unparsable token: ${tkn}`)
}
return {tree, targets}
}, acc).tree
}
// :: StkTree -> EqnTree
// StkTree = [{op: String, num: StkBranch, fns[(Num -> Num)]}]
// StkBranch = Num | StkTree
// EqnTree = [[{b:EqnBranch, e:EqnBranch, efn:(Num -> Num), bfn:(Num -> Num)]]
// EqnBranch = Num | EqnTree
const buildEqnTree = stackTree => {
return stackTree.reduce((eqnTree, stk) => {
const { op, fns } = stk
const fullfn = pipe(...fns)
const num = typeof stk.num === 'number' ? stk.num : buildEqnTree(stk.num)
if (op === '+') {
eqnTree.push([{ b: num, e: 1, bfn: fullfn, efn: id }])
} else if (op === '-') {
eqnTree.push([{ b: -num, e: 1, bfn: fullfn, efn: id }])
} else if (op === '*') {
eqnTree.last.push({ b: num, e: 1, bfn: fullfn, efn: id })
} else if (op === '/') {
eqnTree.last.push({ b: 1 / num, e: 1, bfn: fullfn, efn: id })
} else if (op === '^') {
eqnTree.last.last.e = num
eqnTree.last.last.efn = fullfn
} else {
throw new Error(`Unknown operator: ${op}`)
}
return eqnTree
}, [])
}
// spw = sum of product of powers
const evaluate = spw => {
if (!(spw instanceof Object)) return spw
return spw.reduce((s, pw) => {
return s + pw.reduce((p, w) => {
const b = typeof w.b === 'number' ? w.b : evaluate(w.b)
const e = typeof w.e === 'number' ? w.e : evaluate(w.e)
const {bfn, efn} = w
return p * (bfn(b) ** efn(e))
}, 1)
}, 0)
};
// :: Num -> Num
const precisionRound = (f, p) => {
const factor = 10 ** p
return Math.round(f * factor) / factor
}
// :: String -> Num
const parse = s => {
if (/[!"'§\$&\?,;:#]/.test(s)) {
throw new Error('You may only enter numbers, operators, or functions')
}
const v = pipe(
lintEqn,
buildStackTree,
buildEqnTree,
evaluate,
)(s)
return typeof v === 'number' ? v : NaN
};
I have also put emphasis on making this accept just about any string a user might throw at it. So these are the tests my parser will satisfy as of now:
const test = (string, expectation) => {
const approx = f => precisionRound(f, 15)
const result = parse(string)
console.log(approx(result) === approx(expectation))
}
test('1+2',3)
test('1+2+3+4',10)
test('2*3',6)
test('2*3*4*5',120)
test('1+2*3+4',11)
test('1*2+3*4',14)
test('2^3',8)
test('2^3 + 1',9)
test('2^3 * 3',24)
test('1 + 2^3 * 3',25)
test('3^2 + 4*2',17)
test('12 - 3*4',0)
test('12 * 3/4',9)
test('14/7 + 6',8)
test('sin 0',0)
test('sin 0 +1',1)
test('cos 0',1)
test('cos 90°',0)
test('cos 180°',-1)
test('cos 0°',1)
test('ln e',1)
test('1^ln e',1)
test('e^1',Math.E)
test('e^3',Math.E ** 3)
test('3^e',3 ** Math.E)
test('e^e',Math.E ** Math.E)
test('e^ln e',Math.E)
test('ln exp 1',1)
test('lg 1000',3)
test('sin exp 3.721', Math.sin(Math.exp(3.721)))
test('exp sin 3.721', Math.exp(Math.sin(3.721)))
test('4^sin 3.721', 4 ** (Math.sin(3.721)))
test('sin 1 + exp 3.721', Math.sin(1) + Math.exp(3.721))
test(' --4',4)
test('-- 4',4)
test('- - 4',4)
test(' - - 4',4)
test(' -- 4',4)
test('- -4',4)
test('--4',4)
test(' -4',-4)
test('-4',-4)
test(' -4',-4)
test('- 4',-4)
test('1+2', 3)
test('1+2*3+4', 11)
test('4+(1+2)*(3+4)', 25)
test('2^(3*(1+2))', 512)
My main concerns are readability/maintainability of the code. I do not know about performance optimization yet, so comments on that would be interesting as well. It is my first JS project, so any form of feedback is highly appreciated.
1 Answer 1
Errors, bugs, and precision.
This is not a complete review, just pointing out some problems with the code.
fac its Buggy
The factorial function is buggy and will throw a call stack overflow for negative inputs, and incorrect values for values over 22. Also I don't know why you have all the underscores, seems like you don't trust the language.
fac: i => { if (i !== Math.trunc(i)) { return undefined } const __fac = _i => _i === 0 ? 1 : _i * __fac(_i - 1) return __fac(i) },
Would be better as
fac: i => {
if (i !== Math.trunc(i) || i < 0) { return NaN }
if (i > 22) { return undefined }
const fac = i => i === 0 ? 1 : i * fac(i - 1); // No need for underscores
return fac(i);
},
However there are only 23 valid answers so the best way is via lookup rather than the dangerous and slow recursive solution.
// Declare all solutions outside the function
const factorials = [1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000,20922789888000,355687428096000,6402373705728000,121645100408832000,2432902008176640000,51090942171709440000];;
// Much quicker without worrying about being near the top of the call stack
fac: i => factorials[i] === undefined ? i > 22 ? undefined : NaN : factorials[i],
Precision testing is flawed...
...because precision function is flawed. JavaScript uses FLOATING point numbers, but you are treating them like fixed point numbers.
Consider "0.00000000000000013 * 2" (Small value is 1.3e-16) JavaScript will happily return the correct value 2.6e-16
I think you are trying to fix problems like "0.00000000000000013 ** 2" which JavaScript will calculate to be 1.6899999999999998e-32 which has an error of 2e-48
Both examples your code will round to zero, and the test will pass even if it is completely stuffing up the operators eg approx(1.3e-16 * 2) === approx(1.3e-16 ** 2) is true which is in fact out by 16 orders of magnitude.
You are better of providing the test function with the JavaScript calculated value. Don't test with the known result test("2 * 3", 6) but rather the calculated result test("2 * 3", 2 * 3) and remove the calls to precisionRound .
Euler's constant
Looking at the code it it seams to me that values entered as exponents will be incorrectly evaluated (maybe throw) eg parse("1.2e-16 * 2") will not work. Though I am not sure, I have not run your code?
Triming
Javascript has a trim function so there is no need for trimWhiteSpace
Thus
return pipe( startWithPlus, condenseOperators, separateTokens, trimWhiteSpace, )('+' + s)
becomes
return pipe(
startWithPlus,
condenseOperators,
separateTokens,
)('+' + s).trim()
Plus a +?
Why add the plus? your code can more easily add the plus in buildStackTree
A better parseFloat
A better way to parse a float is Number(numberAsString) because parseFloat tries to fix values while creating a Number will not.
console.log(parseFloat("10x")); // >> 10
console.log(Number("10x")); // >> NaN
console.log(parseFloat("10.0.0")); // >> 10
console.log(Number("10.0.0")); // >> NaN
Do like JavaScript does
Look at the previous section, when JavaScript parses the string value "10.0.0" it does not throw new Error("Too many decimal points!") but rather it returns NaN
You are throwing where the better option is NaN. A malformed equation results in a value that is not a number, not a variety of errors that would need to be trapped.
Personally I would remove all the error checking and let JavaScript throw if it needed (Dont think it would in this case), for the most part it would return NaN on its own.
And Please...
...add the semicolons ';' and reduce the risk of bugs.
Explore related questions
See similar questions with these tags.