-
-
Save skorotkiewicz/48f9ffa1008a39dec49056acd62f0dae to your computer and use it in GitHub Desktop.
PEMDAS/BODMAS
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // with Shunting-Yard Algorithm | |
| const precedence = { "+": 1, "-": 1, "*": 2, "/": 2, "u+": 3, "u-": 3, "^": 4 }; | |
| const rightAssociative = new Set(["^"]); | |
| const binary = { | |
| "+": (a, b) => a + b, | |
| "-": (a, b) => a - b, | |
| "*": (a, b) => a * b, | |
| "/": (a, b) => a / b, | |
| "^": (a, b) => a ** b | |
| }; | |
| const constants = { pi: Math.PI, e: Math.E }; | |
| const number = /^(?:\d+(?:\.\d*)?|\.\d+)(?:e[+-]?\d+)?$/i; | |
| const identifier = /^[a-z_]\w*$/i; | |
| const owns = (object, key) => Object.prototype.hasOwnProperty.call(object, key); | |
| const isOperator = (token) => owns(precedence, token); | |
| const tokenize = (expression) => | |
| expression.match(/(?:\d+(?:\.\d*)?|\.\d+)(?:e[+-]?\d+)?|[a-z_]\w*|[()+\-*/^]|\S/gi) ?? []; | |
| function toRPN(expression) { | |
| const tokens = tokenize(expression); | |
| const output = []; | |
| const operators = []; | |
| let needsValue = true; | |
| for (let i = 0; i < tokens.length; i++) { | |
| let token = tokens[i]; | |
| if (number.test(token)) { | |
| if (!needsValue) throw new Error("Missing operator"); | |
| output.push(Number(token)); | |
| needsValue = false; | |
| continue; | |
| } | |
| if (identifier.test(token)) { | |
| if (!needsValue) throw new Error("Missing operator"); | |
| if (tokens[i + 1] === "(") operators.push(`@${token}`); | |
| else { | |
| output.push(`$${token}`); | |
| needsValue = false; | |
| } | |
| continue; | |
| } | |
| if (token === "(") { | |
| if (!needsValue) throw new Error("Missing operator before '('"); | |
| operators.push(token); | |
| continue; | |
| } | |
| if (token === ")") { | |
| if (needsValue) throw new Error("Missing value before ')'"); | |
| while (operators.length && operators.at(-1) !== "(") output.push(operators.pop()); | |
| if (!operators.length) throw new Error("Mismatched parentheses"); | |
| operators.pop(); | |
| if (operators.at(-1)?.startsWith("@")) output.push(operators.pop()); | |
| needsValue = false; | |
| continue; | |
| } | |
| if (!isOperator(token)) throw new Error(`Invalid character: '${token}'`); | |
| if ((token === "+" || token === "-") && needsValue) { | |
| operators.push(`u${token}`); | |
| continue; | |
| } | |
| if (needsValue) throw new Error(`Missing operand for '${token}'`); | |
| while (isOperator(operators.at(-1))) { | |
| const top = operators.at(-1); | |
| const pop = rightAssociative.has(token) | |
| ? precedence[token] < precedence[top] | |
| : precedence[token] <= precedence[top]; | |
| if (!pop) break; | |
| output.push(operators.pop()); | |
| } | |
| operators.push(token); | |
| needsValue = true; | |
| } | |
| if (needsValue) throw new Error("Invalid expression"); | |
| while (operators.length) { | |
| const token = operators.pop(); | |
| if (!isOperator(token)) throw new Error("Mismatched parentheses"); | |
| output.push(token); | |
| } | |
| return output; | |
| } | |
| function calculate(expression, variables = {}, functions = {}) { | |
| const stack = []; | |
| for (const token of toRPN(expression)) { | |
| if (typeof token === "number") { | |
| stack.push(token); | |
| continue; | |
| } | |
| if (token.startsWith("$")) { | |
| const name = token.slice(1); | |
| const value = owns(variables, name) ? variables[name] : constants[name]; | |
| if (typeof value !== "number") throw new Error(`Unknown variable: ${name}`); | |
| stack.push(value); | |
| continue; | |
| } | |
| if (token.startsWith("@")) { | |
| const name = token.slice(1); | |
| const fn = owns(functions, name) ? functions[name] : owns(Math, name) ? Math[name] : null; | |
| if (typeof fn !== "function") throw new Error(`Unknown function: ${name}`); | |
| if (!stack.length) throw new Error(`Missing argument for ${name}`); | |
| const value = fn(stack.pop()); | |
| if (typeof value !== "number") throw new Error(`${name} must return a number`); | |
| stack.push(value); | |
| continue; | |
| } | |
| if (token === "u+" || token === "u-") { | |
| if (!stack.length) throw new Error(`Missing operand for '${token.slice(1)}'`); | |
| stack.push((token === "u-" ? -1 : 1) * stack.pop()); | |
| continue; | |
| } | |
| if (stack.length < 2) throw new Error(`Missing operands for '${token}'`); | |
| const b = stack.pop(); | |
| stack.push(binary[token](stack.pop(), b)); | |
| } | |
| if (stack.length !== 1) throw new Error("Invalid expression"); | |
| return stack[0]; | |
| } | |
| for (const expression of [ | |
| "3 + 4 * 2 / (1 - 5)^2^3", | |
| "-2^2", | |
| "2*-3 + 4", | |
| "-(3 + 4) * 2", | |
| "2+2*2", | |
| "sin(30)", | |
| "sqrt(9)", | |
| "2+2*2" | |
| ]) { | |
| console.log(calculate(expression)); | |
| } | |
| if (calculate("-2^2 + sqrt(x)", { x: 9 }) !== -1) throw new Error("Self-check failed"); | |
| // console.assert(calculate("-2^2 + x + sqrt(9)", { x: 3 }) === 2, "Self-check failed"); | |
| // console.log(calculate("sin(30) + sqrt(9)")); | |
| // console.log(calculate("double(x)", { x: 4 }, { double: (x) => x * 2 })); |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // without Shunting-Yard Algorithm | |
| function calculate(expression, variables = {}) { | |
| const tokens = | |
| expression.match(/(?:\d+\.?\d*|\.\d+)(?:e[+-]?\d+)?|[a-z_]\w*|[^\s]/gi) ?? []; | |
| const operators = { | |
| "+": [1, (a, b) => a + b], | |
| "-": [1, (a, b) => a - b], | |
| "*": [2, (a, b) => a * b], | |
| "/": [2, (a, b) => a / b], | |
| "^": [4, (a, b) => a ** b] | |
| }; | |
| let i = 0; | |
| const fail = (token = tokens[i]) => { | |
| throw new Error(`Unexpected token: ${token ?? "end"}`); | |
| }; | |
| const parse = (minimum = 0) => { | |
| const token = tokens[i++]; | |
| let value; | |
| if (token === "+" || token === "-") { | |
| value = (token === "-" ? -1 : 1) * parse(3); | |
| } else if (token === "(") { | |
| value = parse(); | |
| if (tokens[i] !== ")") fail(); | |
| i++; | |
| } else if (!Number.isNaN(Number(token))) { | |
| value = Number(token); | |
| } else if (/^[a-z_]\w*$/i.test(token ?? "")) { | |
| const scope = Object.hasOwn(variables, token) ? variables : Math; | |
| if (!Object.hasOwn(scope, token)) fail(token); | |
| value = scope[token]; | |
| if (tokens[i] === "(") { | |
| if (typeof value !== "function") fail(token); | |
| i++; | |
| const args = []; | |
| while (tokens[i] !== ")") { | |
| args.push(parse()); | |
| if (tokens[i] !== ",") break; | |
| i++; | |
| } | |
| if (tokens[i] !== ")") fail(); | |
| i++; | |
| value = value(...args); | |
| } | |
| if (typeof value !== "number") fail(token); | |
| } else { | |
| fail(token); | |
| } | |
| while ((operators[tokens[i]]?.[0] ?? -1) >= minimum) { | |
| const operator = tokens[i++]; | |
| const [precedence, apply] = operators[operator]; | |
| value = apply(value, parse(precedence + (operator === "^" ? 0 : 1))); | |
| } | |
| return value; | |
| }; | |
| const value = parse(); | |
| if (i !== tokens.length) fail(); | |
| return value; | |
| } | |
| for (const expression of [ | |
| "3 + 4 * 2 / (1 - 5)^2^3", | |
| "-2^2", | |
| "2*-3 + 4", | |
| "-(3 + 4) * 2", | |
| "2+2*2", | |
| "sin(30)", | |
| "sqrt(9)", | |
| "2+2*2" | |
| ]) { | |
| console.log(calculate(expression)); | |
| } | |
| if (calculate("-2^2 + sqrt(x)", { x: 9 }) !== -1) throw new Error("Self-check failed"); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment