Created
August 2, 2021 00:38
-
-
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.
This file contains 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
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