sc-ae.js

/**
* Resolve an arithmetic equation.
*
* Ex. '1+3*4/22^4-11'
*
* @param {String} equation - string representation of arithmetic equation
* @return {Number} - resolved number
*/

/**
 * Time Complexity: O(n)
 * Space: Complexity: O(n)
 */

const LEFT_BRACE = '(';
const RIGHT_BRACE = ')';
const OPERATORS = { '^': true , '/': true, '*': true , '%': true , '+': true, '-': true };

function stack() {
    const data = [];
    return {
        isEmpty: () => !data.length,
        peek: () => data[data.length - 1],
        pop: () => data.pop(),
        push: (char) => data.push(char),
        values: data
    };
}

function isNum(char) { // could also be isOperand
    return !isNaN(parseFloat(char)) && isFinite(char);
}

function isOperator(char) {
    return OPERATORS.hasOwnProperty(char);
}

function getPriority(char) {
    switch (char) {
        case '+':
        case '-':
            return 0;
        case '/':
        case '*':
            return 1;
        case '^':
            return 2;
        default: 
            return -1;
    }
}

function math(leftOperand, rightOperand, operator) {
  switch (operator) {
    case '^':
      return Math.pow(leftOperand, rightOperand);
    case '/':
      return leftOperand / rightOperand;
    case '*':
      return leftOperand * rightOperand;
    case '%':
      return leftOperand % rightOperand;
    case '+':
      return leftOperand + rightOperand;
    case '-':
      return leftOperand - rightOperand;
  }
}

function calculate(equation) {
  if (!equation || !equation.length) {
      return new Error();
  }

  const operands = stack();
  const operators = stack();
  let lastCharWasNum = false;
  
  function parse() {
    let rightOperand = operands.pop();
    let leftOperand = operands.pop();
    let operator = operators.pop();
    let value = math(Number(leftOperand), Number(rightOperand), operator);
    operands.push(value);
  }
  
  for (let i = 0; i < equation.length; ++i) {
    let char = equation[i];
    
    if (isNum(char)) { 
      // if num, add to the operands stack
      if (!lastCharWasNum) {
        operands.push(char);
      } else {
        operands.push(operands.pop() + char);
      }
      lastCharWasNum = true;
    } else if (operators.isEmpty() && isOperator(char)) {
      // add operand to empty stack
      operators.push(char);
      lastCharWasNum = false;
    } else if (!operators.isEmpty() && isOperator(char) && 
               getPriority(char) >= getPriority(operators.peek())) {
      // add operand to stack if it has a greater priority than the last one
      operators.push(char);
      lastCharWasNum = false;
    } else if (char === LEFT_BRACE) {
      operators.push(char);
      lastCharWasNum = false;
    } else if (char === RIGHT_BRACE) {
      parse();
      if (operators.pop() !== LEFT_BRACE) {
          return new Error(); // invalid expression
      }
      lastCharWasNum = false;
    } else {
      // if operand is lower priority, evaluate 
      while (!operators.isEmpty() && getPriority(char) <= getPriority(operators.peek())) { 
        parse();
      }
      operators.push(char);
      lastCharWasNum = false;
    }
  }
  
  // evaluate any remaining elements
  while (!operators.isEmpty()) {
    parse(); 
  }
  
  return operands.pop();
}

const assert = require('assert');
assert.equal(calculate('1+3*4/22^4-11'), -9.999948773990848);
assert.equal(calculate('1+2+3'), 6);
assert.equal(calculate('(1+2)*3'), 9);