Skip to content

Instantly share code, notes, and snippets.

@krebernisak
Last active June 1, 2020 18:55
Show Gist options
  • Save krebernisak/238f1a06fc37f207919713df4e9866e9 to your computer and use it in GitHub Desktop.
Save krebernisak/238f1a06fc37f207919713df4e9866e9 to your computer and use it in GitHub Desktop.
A function that accepts as an argument a string of addition/subtraction operations.
// Write a function that accepts as an argument a string of addition/subtraction operations.
// The function should return the result of the operations as an integer
// ex: calculate("1 - 2 + 3") => 2
// will not see: "1 - -2"
/**
* Solution:
* 1. Build a stack using Reverse Polish (Post-fix) notation
* 2. Build a stack machine that reads and executes Reverse Polish (Post-fix) notation
*
* Example: "1 - 2 + 3"
* 1. ["+", 3, "-", 2, 1]
* 2. ["+", 3, -1]
* 3. [2]
*/
const _add = (a, b) => a + b;
const _subtract = (a, b) => a - b;
const _operatorMap = {
"+": _add,
"-": _subtract,
};
const _numbersRegex = () => /\d+/g;
const _findNumbers = (str) => str.match(_numbersRegex());
const _operatorsRegex = () => /[+-]/g;
const _findOperators = (str) => str.match(_operatorsRegex());
// Build a Reverse Polish (Post-fix) notation stack from string
const _buildStack = (str) => {
const nums = _findNumbers(str);
const ops = _findOperators(str);
const _nextOp = () => ops.pop();
const _nextNum = () => parseInt(nums.pop());
if (!nums) throw Error("No numbers found!");
if (nums.length === 1) return [_nextNum()]; // as stack with only one item
if (nums.length !== ops.length + 1)
throw Error("Should always have one less operator than numbers!");
const stack = [];
while (nums.length > 1) {
stack.push(_nextOp());
stack.push(_nextNum());
}
stack.push(_nextNum());
return stack;
};
// Few simple tests for helper functions
const _testStr = "1 - 2 + 3";
const _testStack = ["+", 3, "-", 2, 1];
console.assert(_findNumbers(_testStr).join("") === ["1", "2", "3"].join(""));
console.assert(_findOperators(_testStr).join("") === ["-", "+"].join(""));
console.assert(_buildStack(_testStr).join("") === _testStack.join(""));
// Executes Reverse Polish (Post-fix) notation operations on stack in-place
const _execute = (stack) => {
while (stack && stack.length >= 3) {
const a = stack.pop();
const b = stack.pop();
const opFunc = _operatorMap[stack.pop()];
const result = opFunc(a, b);
stack.push(result);
}
};
// Simple tests for _execute function
_execute(_testStack);
console.assert(_testStack.pop() === 2);
// Calculate result of a string math formula with addition/subtraction operations.
const calculate = (str) => {
const stack = _buildStack(str);
_execute(stack);
if (stack.length !== 1)
throw Error("Unexpected stack state -> operation unsuccessful!");
return stack.pop();
};
const _testCases = [
["3", 3],
["7", 7],
["1 - 1", 0],
["1 + 1", 2],
["1 - 2 + 3", 2],
["1 - 2 + 3 + 3", 5],
["1 - 2 + 3 + 5", 7],
["1 - 2 + 3 + 5 - 5", 2],
["1 - 2 + 3 + 10", 12],
["1 - 2 + 2 - 1", 0],
["2 - 1 + 1 - 2", 0],
["1 - 2 + 2 - 1 - 5", -5],
["1 - 2 + 2 - 1 - 5 - 11", -16],
["2 - 5 - 1 - 11 + 1 - 2", -16],
];
const _runTestCase = (_test) => {
const [input, expected] = _test;
return calculate(input) === expected;
};
const _all = _testCases.every(_runTestCase);
console.assert(_all === true, "Tests Failed!");
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment