How to calculate array of character expression like eval?

Question

I'm trying to mock eval like function. Let's say I have an input like this:

arr = [
"1" ,
"+" ,
"(" ,
"33" ,
"+" ,
"44" ,
")" ,
"+" ,
"2" ,
"+" ,
"(" ,
"55" ,
"+" ,
"66" ,
")" ,
"="
]

Now I want to calculate it like 1+(33+44)+2+(55+66)= without using eval

I have tried something like below with no result:

let result = 0;

  for (let i = 0; i < arr.length; i++) {
    var expr = arr[i];

    if (expr == '+' || expr == "-" || expr == "*" || expr == "(" || expr == ")") {

      if (expr == "(") {
        for (let j = i; j < arr.length; j++) {

          if(expr == "+"){

          }else if(expr == "-"){

          }else if(expr == "*"){

          }else if (expr == ")") {
            i = j+1;
            break;
          }else{
            result = result + parseFloat(expr);
          }

        }
      }

    } else {
      result = result + parseFloat(expr);
    }
    console.log(result)

I removed some code which I tried as it is giving me too many errors. Can any one help me on this. Kindly comments for further details is needed. Thanks in advance.

Answer 1

You could take a simplified approach with using a nested array as stack for the levels, indicated by parentheses and use only binary operator and omit =, because this not necessary. At the end all open calculations are made.

This is an object with arrow function and uses unary plus + for getting a number from a string. Then other operators does not need this, because the oparator coerces the value to a number by using these operators. + works for strings as well.

{
    '+': (a, b) => +a + +b
}

The rest is simple. If an open parentesis is found, a new level of the stack is opend and all tokens are collected to this level until a closing parenthesis is found, then the level is calculated and the value is returned to the level before.

calculate takes three items of the stack and performs an operation with left and right value and the middle operator. The result is returned in the array at index zero.

For unary minus, you could check it and remove this items and update the next value, depending on the count of found minus.

function evaluate(string) {

    function calculate(array) {

        function removeUnaryMinus(array, offset) {
            var nonMinusIndex = array.findIndex((s, i) => i >=offset && s !== '-');
            array.splice(offset, nonMinusIndex - offset);
            if (nonMinusIndex % 2) array[offset] *= -1;
        }

        removeUnaryMinus(array, 0);
        while (array.length > 2) {
            removeUnaryMinus(array, 2);                    
            array.splice(0, 3, ops[array[1]](array[0], array[2]));
        }
        return array[0];
    }

    var ops = {
            '+': (a, b) => +a + +b,
            '-': (a, b) => a - b,
            '*': (a, b) => a * b,
            '/': (a, b) => a / b
        },
        stack = [[]],
        level = 0;

    string
        .split(/([+\-*\/()])/)
        .filter(s => s && s !== ' ')
        .forEach(token => {
            if (!token || token === '=') return;
            if (token === '(') {
                ++level;
                stack[level] = [];
                return;
            }
            if (token === ')') {
                --level;
                stack[level].push(calculate(stack[level + 1]));
                return;
            }
            stack[level].push(token);
        });
    return calculate(stack[0]);
}

console.log(evaluate('12 + 3'));                  //   15
console.log(evaluate('-(12 + -23) * (-4 + -7)')); // -121

Answer 2

I recently stumbled upon a similar problem and had to had to come up with my own solution. The code consists of 2 functions, one will convert the code into a function tree and the other will execute it. I've slightly altered it to fill your needs:

var operations = {
  '+': function(left, right) {
    return left + right;
  },
  '-': function(left, right) {
    return left - right;
  },
  '/': function(left, right) {
    return left / right;
  },
  '*': function(left, right) {
    return left * right;
  }
};

var tree = extractEquation("1+(33+44)+2+(55+66)");
console.log(resolveTree(tree));
console.log(tree);

/**
 * Runs a parsed mathematical expression
 * @param {Array<Array|{}|string>} functionTree expression in tree form
 * @returns {number} result of the expression
 */
function resolveTree(functionTree) {
  var operator = "+";
  return functionTree.reduce(function(result, item) {
    if (item instanceof Array) {
      return operations[operator](result, resolveTree(item));
    } else if (typeof item === "object") {
      operator = item.operator;
      return result;
    } else {
      return operations[operator](result, +item);
    }
  }, 0);
}

/**
 * Parses a mathematical expression
 * @param {string} expr expression in text form
 * @returns {Array<Array|{}|string>} expression in tree form
 */
function extractEquation(txt) {
  var root = [];
  var result = [].reduce.call(txt.replace(/:?(\w|\d)+\s*(\*|\/)\s*:?(\w|\d)+/g, function(priorityOperation) {
    return "(" + priorityOperation + ")";
  }).replace(/\s/g, ""), function(result, char) {
    if (char === "(") {
      var newResult = [];
      newResult.parent = result;
      result.push(newResult);
      return newResult;
    } else if (char === ")") {
      if ("parent" in result) return result.parent;
      else throw SyntaxError("Found ) but missing (");
    } else if (Object.keys(operations).includes(char)) {
      if (result.length && typeof result[result.length - 1] !== "string" && "operator" in result[result.length - 1]) throw SyntaxError("Double operator");
      result.push({
        operator: char
      });
    } else {
      if (!result.length) result.push("");
      else if (typeof result[result.length - 1] !== "string" && "operator" in result[result.length - 1]) result.push("");
      result[result.length - 1] += char;
    }
    return result;
  }, root);
  if (result !== root) throw SyntaxError("Unclosed (");
  return root;
}

Here is a more interactive example:

var operations = {
  '+': function(left, right) {
    return left + right;
  },
  '-': function(left, right) {
    return left - right;
  },
  '/': function(left, right) {
    return left / right;
  },
  '*': function(left, right) {
    return left * right;
  }
};

document.getElementById("input").addEventListener("input", function() {
  document.getElementById("tree").innerHTML = "";
  try {
    var tree = extractEquation(document.getElementById("input").value);
    document.getElementById("result").textContent = resolveTree(tree);
    document.getElementById("error").textContent = "";
    fixUITree(document.getElementById("tree"), tree);
  } catch (err) {
    document.getElementById("error").textContent = err.message || err;
    document.getElementById("result").textContent = "";
  }
});

function fixUITree(dom, tree) {
  tree.forEach(function(item) {
    if (item instanceof Array) {
      fixUITree(dom.appendChild(document.createElement("ul")), item);
    } else if (typeof item === "object") {
      dom.appendChild(document.createElement("li")).textContent = item.operator;
    } else {
      dom.appendChild(document.createElement("li")).textContent = item;
    }
  }, 0);
}

/**
 * Runs a parsed mathematical expression
 * @param {Array<Array|{}|string>} functionTree expression in tree form
 * @returns {number} result of the expression
 */
function resolveTree(functionTree) {
  var operator = "+";
  return functionTree.reduce(function(result, item) {
    if (item instanceof Array) {
      return operations[operator](result, resolveTree(item));
    } else if (typeof item === "object") {
      operator = item.operator;
      return result;
    } else {
      return operations[operator](result, +item);
    }
  }, 0);
}

/**
 * Parses a mathematical expression
 * @param {string} expr expression in text form
 * @returns {Array<Array|{}|string>} expression in tree form
 */
function extractEquation(txt) {
  var root = [];
  var result = [].reduce.call(txt.replace(/:?(\w|\d)+\s*(\*|\/)\s*:?(\w|\d)+/g, function(priorityOperation) {
    return "(" + priorityOperation + ")";
  }).replace(/\s/g, ""), function(result, char) {
    if (char === "(") {
      var newResult = [];
      newResult.parent = result;
      result.push(newResult);
      return newResult;
    } else if (char === ")") {
      if ("parent" in result) return result.parent;
      else throw SyntaxError("Found ) but missing (");
    } else if (Object.keys(operations).includes(char)) {
      if (result.length && typeof result[result.length - 1] !== "string" && "operator" in result[result.length - 1]) throw SyntaxError("Double operator");
      result.push({
        operator: char
      });
    } else {
      if (!result.length) result.push("");
      else if (typeof result[result.length - 1] !== "string" && "operator" in result[result.length - 1]) result.push("");
      result[result.length - 1] += char;
    }
    return result;
  }, root);
  if (result !== root) throw SyntaxError("Unclosed (");
  return root;
}

#result {
  color: green;
}

#error {
  color: red;
}

<input id="input" type="text">

<span id="result"></span>
<span id="error"></span>

<ul id="tree">

</ul>

Step by Step

1. var tree = extractEquation("12 + 6 * 3");
2. "12 + 6 * 3".replace(/:?(\w|\d)+\s*(\*|\/)\s*:?(\w|\d)+/g, function(priorityOperation) { return "(" + priorityOperation + ")"; }) sets the priority operations. result is : 12 + (6 * 3)
3. "12 + (6 * 3)".replace(/\s/g, "") will remove the spaces, result is: 12+(6*3)
4. [].reduce.call("12 + (6 * 3)", function(result, char){}, []); will call function(result, char){} (where result is the return value of the last iteration, starting at [], and char is each character).
5. First iteration result = [], char = "1"
   • if ("1" === "(") => false
   • if ("1" === ")") => false
   • if (["+", "-", "*", "/"].includes("1")) => false
   • else
   • if (![].length) => true
   • [].push("")
   • [""][0] += "1"
6. Second iteration result = ["1"], char = "2"
   • if ("2" === "(") => false
   • if ("2" === ")") => false
   • if (["+", "-", "*", "/"].includes("2")) => false
   • else
   • if (![].length) => false
   • if ([""][0] is an operator) => false
   • ["1"][0] += "2"`
7. Third iteration result = ["12"], char = "+"
   • if ("+" === "(") => false
   • if ("+" === ")") => false
   • if (["+", "-", "*", "/"].includes("+")) => true
   • if (["12"].length && ["12"][0] is an operator) => false
   • ["12"].push({operator: "+"})
8. Fourth iteration result = ["12", {"+"}], char = "("
   • if ("(" === "(") => true
   • ["12", {"+"}].push([])
9. Fifth iteration result = [], char = "6"
   • if ("6" === "(") => false
   • if ("6" === ")") => false
   • if (["+", "-", "*", "/"].includes("6")) => false
   • else
   • if (![].length) => true
   • [].push("")
   • [""][0] += "6"
10. Sixth iteration result = ["6"], char = "*"
    • if ("*" === "(") => false
    • if ("*" === ")") => false
    • if (["+", "-", "*", "/"].includes("*")) => true
    • if (["6"].length && ["6"][0] is an operator) => false
    • ["6"].push({operator: "*"})
11. Seventh iteration result = ["6", {"*"}], char = "3"
    • if ("3" === "(") => false
    • if ("3" === ")") => false
    • if (["+", "-", "*", "/"].includes("3")) => false
    • else
    • if (!["6", {"*"}].length) => false
    • if (["6", {"*"}] is an operator) => true
    • ["6", {"*"}].push("")
    • ["6", {"*"}] += "3"
12. Eight iteration result = ["6", {"*"}, "3"], char = ")"
    • if (")" === "(") => false
    • if (")" === ")") => true
    • return ["12", {"+"}, ["6", {"*"}, "3"]]