Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save wesleylhandy/5fddaeb5e735bdacf8a14e996db780a1 to your computer and use it in GitHub Desktop.
Save wesleylhandy/5fddaeb5e735bdacf8a14e996db780a1 to your computer and use it in GitHub Desktop.
This script incorporates the Shunting-yard algorithm to convert a stringified mathematical expression into postfix notation (RPN) and then evaluates that notation to provide the calculation for the mathematical expression provided.
const OPEN_PARENS = "(";
const CLOSED_PARENS = ")";
const ADD = "+";
const SUBTRACT = "-";
const MULTIPLY = "*";
const DIVIDE = "/";
const MODULUS = "%";
const TO_POWER_STAR = "**";
const TO_POWER_CARET = "^";
const LEFT = "left";
const RIGHT = "right";
const SPACE = " ";
const isOperator = /([\(\)\-\/\+%^]|[\*]{1,2})/;
const numOpenParen = /([0-9]\()/g;
function numTimesOpenParen(match) {
return match.split('').join('*');
}
const closeParenOpenParen = /(\)\()/g
function validateInput(str) {
const matches = [...str.matchAll(/[^0-9 .\/\*%\+\-\(\)\^]+/g)];
if (matches.length === 0) {
return { error: null };
}
return {
error: new Error(`Invalid Tokens: ${matches.map(match => match[0]).join(", ")}`),
};
}
const operations = new Map([
[ADD, {
precedence: 10,
associativity: LEFT,
operation: (a, b) => a + b,
}],
[SUBTRACT, {
precedence: 10,
associativity: LEFT,
operation: (a, b) => a - b,
}],
[MULTIPLY, {
precedence: 20,
associativity: LEFT,
operation: (a, b) => a * b,
}],
[DIVIDE, {
precedence: 20,
associativity: LEFT,
operation: (a, b) => a / b,
}],
[MODULUS, {
precedence: 20,
associativity: LEFT,
operation: (a, b) => a % b,
}],
[TO_POWER_STAR, {
precedence: 40,
associativity: RIGHT,
operation: (a, b) => Math.pow(a, b),
}],
[TO_POWER_CARET, {
precedence: 40,
associativity: RIGHT,
operation: (a, b) => Math.pow(a, b),
}],
]);
class Stack {
#data = [];
constructor() {}
get values() {
return this.#data;
}
empty() {
for(let i = this.values.length - 1; i >= 0; i--) {
this.pop()
}
}
get isEmpty() {
return this.values.length === 0;
}
pop() {
if (!this.isEmpty) {
return this.#data.pop();
}
return null;
}
push(value) {
this.#data.push(value);
}
get peek() {
if (!this.isEmpty) {
return this.values[this.values.length - 1];
}
return null;
}
}
function processOperation(operation, x, y) {
const process = operations.get(operation);
if (process) {
return process(x, y);
}
return 0;
}
function postFixFromExpression(expression = []) {
let outputQueue = "";
const operatorStack = new Stack();
for (let i = 0; i < expression.length; i++) {
const token = expression[i];
switch (token) {
case OPEN_PARENS:
operatorStack.push(token);
break;
case CLOSED_PARENS:
let current = operatorStack.peek;
while(current !== OPEN_PARENS) {
outputQueue += operatorStack.pop() + SPACE;
current = operatorStack.peek
}
operatorStack.pop();
break;
case ADD:
case SUBTRACT:
case MULTIPLY:
case DIVIDE:
case MODULUS:
case TO_POWER_STAR:
case TO_POWER_CARET:
const o1 = operations.get(token);
let o2 = operations.get(operatorStack.peek);
while (o2
&& ((
o1.associativity === LEFT
&& o1.precedence <= o2.precedence
) || (
o1.associativity === RIGHT
&& o1.precedence < o2.precedence
))
) {
outputQueue += operatorStack.pop() + SPACE;
o2 = operations.get(operatorStack.peek);
}
operatorStack.push(token);
break;
default:
outputQueue += token + SPACE;
break;
}
}
let isEmpty = operatorStack.isEmpty;
while(!isEmpty) {
outputQueue += operatorStack.pop() + SPACE;
isEmpty = operatorStack.isEmpty;
}
return outputQueue;
}
function valueFromPostFix(postFix) {
const expression = postFix.split(SPACE).filter(Boolean);
let stack = new Stack();
if (expression.length === 1) {
return !Number.isNaN(Number(expression[0])) ? Number(expression[0]) : 0;
}
for (let i = 0; i < expression.length; i++) {
const token = expression[i];
if (!Number.isNaN(Number(token))) {
stack.push(Number(token));
} else {
let rightOperand = stack.pop();
let leftOperand = stack.pop();
if (leftOperand === null || rightOperand === null) {
return "Invalid Input: Cannot perform postfix calculation";
}
const operation = operations.get(token).operation;
const value = operation(leftOperand, rightOperand);
stack.push(value);
}
}
return stack.pop()
}
function evaluate(str) {
const { error } = validateInput(str);
if (error) {
throw error;
}
const replaced = str
.replace(numOpenParen, numTimesOpenParen)
.replace(closeParenOpenParen, ")*(");
const expression = replaced
.split(isOperator)
.filter(Boolean)
const postFix = postFixFromExpression(expression);
return valueFromPostFix(postFix);
}
console.log(evaluate('(3+(4*5))'));
console.log(evaluate('3(51-7**2)'));
console.log(evaluate('3+(4*5)(21/7)'));
console.log(evaluate('apples + oranges')); // throws
console.log(evaluate('3x + 4y')); // throws
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment