How to implement build in function .eval() with recursive function

Question

Hei Coders,

I have a string "1+1", with javascript build in function eval() i can do eval("1+1") so the return value will be 2

But how about if i want to implement this concept to recursive function in javascript?

function evaluate(str) {

}

evaluate("1+1");
evaluate("1-1");
evaluate("1*1");
evaluate("1/1");

What i've tried are

function evaluate(str) {
  if (str.length === 0) {
    return "";
  }else{
    let angka;
    let symbol;
    for (let i = 0; i < str.length; i++) {
      if (isNaN(str[i])) {
        symbol = str[i];
        break;
      }else{
        angka = str[i]; 
      }
    }
    switch (symbol) {
      case "+": 
        return angka + evaluate(str.slice(1));
      case "-":
          return angka - evaluate(str.slice(1));
      case "/":
        return angka / evaluate(str.slice(1));
      case "*":
        return angka * evaluate(str.slice(1));
      default:
        return parseInt(str[0]) + evaluate(str.slice(1));
    }
  }
}

function evaluate(str) { 
  if (str.length === 0) {
    return ""
  }

  let numbers = "";
  let operator = "";
  let lastIndex = 0;
  for (let i = 0; i <= str.length; i++) {
        if (!isNaN(parseInt(str[i]))) {
          numbers += parseInt(str[i]);          
        }else{
          operator = str[i];
          lastIndex = i;
          break;
        }
  }

  // console.log(numbers, " " , operator , " " , lastIndex);
  lastIndex  = lastIndex < 1 ? 1 : lastIndex;
  if (operator === "+") {
    return numbers + evaluate(str.slice(lastIndex));
  }
}

function evaluate(str) {
  if (str.length === 0) {
    return 1;
  }else{
    let numbers = "";
    for (let i = 0; i <= str.length; i++) {
      if(parseInt(str[i]) >= 0){
        numbers = numbers + "+" +  str[i];
      }else{
        let lengthNumbers = numbers.length > 1 ? numbers.length : 1;
        let tempNumbers = numbers;
        numbers = "";
        return tempNumbers + evaluate(str.slice(lengthNumbers))
      }
    }
  }
}

===========

UPDATED

How nub i am :), for now this is my answer (according to the solutions below), Thanks for all

function evaluate(str) {
 if(str.match(/[*/+-]/)){
   let numbers = "";
   for (let i = 0; i < str.length; i++) {
     switch (str[i]) {
       case "+":
        return parseInt(numbers) + evaluate(str.slice(numbers.length+1))     
      case "*":
          return parseInt(numbers) * evaluate(str.slice(numbers.length+1))       
      case "/":
          return parseInt(numbers) / evaluate(str.slice(numbers.length+1))       
      case "-":
          return parseInt(numbers) - evaluate(str.slice(numbers.length+1))       
      default:
        numbers += str[i];
        break;
     }     
   }
 }else{
   return parseInt(str[0]);
 }

}
console.log(evaluate('1+2+3+4+5')) // 15
console.log(evaluate('1*2*3*4*5')) // 120
console.log(evaluate('20/4')) // 5
console.log(evaluate('20-6')) // 14

And no one work! I know eval will save my day, but in this case i need to solve this case, thanks before.

Answer 1

Try this code

function evaluate(str) {
  var reg = /[*/+-]/
  if(str.match(reg)){
    var temp = ''
    for(let i = 0; i < str.length; i++){
      if(str[i] === '+') {
        return parseInt(temp) + evaluate(str.substring(i+1))
      }
      else if(str[i] === '-') {
        return parseInt(temp) - evaluate(str.substring(i+1))
      }
      else if(str[i] === '*') {
        return parseInt(temp) * evaluate(str.substring(i+1))
      }
      else if(str[i] === '/') {
        return parseInt(temp) / evaluate(str.substring(i+1))
      }
      else {
        temp += str[i]
      }
    }
  }
  else {
    return parseInt(str)
  }
}

console.log(evaluate('1+2+3+4+5')) // 15
console.log(evaluate('1*2*3*4*5')) // 120
console.log(evaluate('20/4')) // 5
console.log(evaluate('20-6')) // 14

Answer 2

Another approach is to turn your string into a an array that can be evaluated as a stack, then do a simple evaluation of that stack. For instance, we might make "10 - 20 + 30 * 2 / 10" into [10, 20, "-", 30, "+", 2, "*", 10, "/"] and then evaluate it by sequentially replacing the top two elements of the stack with the value of the current operation applied to them.

This technique is only for the left-to-right operations. It ignores operator precedence, and cannot handle parentheses, or non-binary operations. But it might be enough for your needs.

Here's an implementation:

const evalExpr = (ops) => (expr) => expr
  .replace (/([-+*\/])(\s)*(\d+)/g, (_, a, b, c) => c + b + a)
  .split (/\s+/)                                             
  .map (n => Number(n) || n)
  .reduce (
    (stack, symbol, _, __, op = ops[symbol]) => op           
      ? [... stack.slice(0, -2), op(...stack.slice(-2))] 
      : [... stack, symbol]
    , []
  ) [0];
  
const ops = {
  '+': (a, b) => a + b,
  '-': (a, b) => a - b,
  '*': (a, b) => a * b,
  '/': (a, b) => a / b,
};

const evalNumericExpr = evalExpr (ops);

//  Test
[
  "1 + 1", 
  "1 - 1", 
  "1 * 1", 
  "1 / 1", 
  "2 + 4 + 7", 
  "5 - 7", 
  "5 * 2 + 10",
  "10 - 20 + 30 * 2 / 10",  
  "1 + 5 * 2 + 12 * 2 * 2",
  "10 + 13 - 5 * 3 + 12 / 3 + 3"
] 
.forEach (expr => console .log (`${expr} ==> ${evalNumericExpr (expr)}`))

The replace, split, and map steps together turn this string into a stack ready for processing. The reduce step actually processes that array, adding and removing elements on a stack. With "10 - 20 + 30 * 2 / 10" becoming [10, 20, "-", 30, "+", 2, "*", 10, "/"], the reduction would proceed like this:

stack: [],        next: 10   // Push 10 onto the stack
stack: [10],      next: 20   // Push 20 onto the stack
stack: [10, 20],  next: '-'  // Pop 10 and 20 from the stack.  Push (10 - 20) to it
stack: [-10],     next: 30   // Push 30 to the stack
stack: [-10, 30], next: '+'  // Pop -10 and 30 from the stack. Push (-10 + 30) to it
stack: [20],      next: 2    // Push 2 to the stack
stack: [20, 2],   next: '*'  // Pop 20 and 2 from the stack.   Push (20 * 2) to it
stack: [40],      next: 10   // Push 10 to the stack
stack: [40, 10],  next: '/'  // Pop 40 and 10 from the stack.  Push (40 / 10) to it
stack: [4]                   // For a well-formed expression, the stack now has just
                             // one element on it, and that's your result.

There are plenty of ways you could extend this. Obviously it's trivial to add new binary operations. We could also add other arity operations to the reduction (although it would be trickier to convert the string to the stack format) by replacing the -2's in the reduction with -op.length. If we wanted to handle decimal numbers, we could just change the regex to something like /([-+*\/])(\s)*(\-?\d+(:?\.\d+)?)/g.

And congratulations to us. We've just written the beginning of a Forth interpreter!

---

Update

The question specifically asked about how to do this recursively, and I wrote a recursive version which was overall simpler than the above. But then I realized how it could easily be extended to handle parentheses and to respect operator precedence. It's no longer necessarily simpler, but it's an interesting approach, one which we could easily extend with other operators and difference precedence levels:

// Does not test for well-formedness.  Will likely return NaN for
// ill-formed expression strings
const evalNumericExpr = (
  expr, 
  [regex, fn, ops] = [
    // parentheses
    [/\(([^())]*)\)/, (ops, expr, regex) => evalNumericExpr (expr.replace(regex, (_, e) => evalNumericExpr(e))), {}],
    // multiplication and division
    [/\s*(\-?\d+)\s*([/*])\s*(\-?\d+)/, (ops, expr, regex) => evalNumericExpr (expr .replace (
      regex,
      (_, a, op, b) => String(ops[op](Number(a),  Number(b)))
    )), {'*': (a, b) => a * b, '/': (a, b) => a / b}],
    // addition and subtraction
    [/\s*(\-?\d+)\s*([+-])\s*(\-?\d+)/, (ops, expr, regex) => evalNumericExpr (expr .replace (
      regex,
      (_, a, op, b) => String(ops[op](Number(a),  Number(b)))
    )), {'+': (a, b) => a + b, '-': (a, b) => a - b}],
    // everything else
    [/.?/, (ops, expr, regex) => Number(expr.trim()), {}]
  ].find(([regex, fn, ops]) => regex.test(expr))
) => fn(ops, expr, regex)


//  Test
; [
  "1 + 5", 
  "7 - 2", 
  "3 * 5", 
  "21 / 3", 
  "2 + 4 + 7", 
  "5 - 7", 
  "5 * 2 + 10",
  "5 * 2 + (3 * 5)",
  "10 - 20 + 30 * 2 / 10",  
  "10 - ((4 * 5) - (5 * 6)) * 2 / 10",  
  "10 - ((4 * (2 + 3)) - (5 * 6)) * 2 / 10",  
  "1 + 5 * 2 + 12 * 2 * 2",
  "10 + 13 - 5 * 3 + 12 / 3 + 3"
].forEach (expr => console .log (`${expr} ==> ${evalNumericExpr (expr)}`))

The big advantage to this approach is that it would make it easy to extend to any mathematical operators we choose. And there is room for further simplification.

Update 2

I wasn't really happy with the code from the previous update. This version seems cleaner to me and also adds exponentiation. Here's a first pass at it:

const evalNumericExpr = (() => {
  const ops = [
    [   // grouping
      /\(([^()]+)\)/,
      (evaluator, subexpr) => evaluator(subexpr)
    ], [ //exponentiation
      /([-+]?\d+)\s*[\^]\s*([-+]?\d+)([^\^]*)$/,
      (_, base, exp, rest) => `${base ** exp}${rest}`
    ], [ // multiplication, divide, remainder
      /([-+]?\d+)\s*([*%\/])\s*([-+]?\d+)/, 
      ((ops) => ((_, a, op, b) => ops [op] (Number (a), Number (b))))(
        {'*': (a, b) => a * b, '/': (a, b) => a / b, '%': (a, b) => a % b}
      )
    ], [ // addition, subtraction
      /([-+]?\d+)\s*([+-])\s*([-+]?\d+)/,
      ((ops) => ((_, a, op, b) => ops [op] (Number (a), Number (b))))(
        {'+': (a, b) => a + b, '-': (a, b) => a - b}
      )
    ]
  ]
  const evaluator = (expr) => Number(ops .reduce(
    (expr, [regex, fn]) => regex .test (expr) 
      ? evaluator(expr .replace (regex, (...args) => fn (evaluator, ...args .slice (1)))) 
      : expr,
    expr
  ))
  return evaluator
})()

// Test
; [
  "1 + 3", 
  "7 - 2", 
  "2 * 6", 
  "12 / 4", 
  "2 + 4 + 7", 
  "5 * 2 + 10",
  "10 - 20 + 30 * 2 / 10",  
  "1 + 5 * 2 + 12 * 2 * 2",
  "10 + 13 - 5 * 3 + 12 / 3 + 3",
  "10 + (13 - 5) * 3 + 12 / 3 + 3",
  "5 * (4 + (2 * (1 + 1 + 1)))",
  "5 ^ 2",
  "5 ^ 2 * 2",
  "2 ^ 3 ^ 2", // Note: should parse as `2 ^ (3 ^ 2)`, not `(2 ^ 3) ^ 2`
  "2 ^ 3 ^ 2 + 3 ^ 3 * 2",
] 
.forEach (expr => console .log (`${expr} ==> ${evalNumericExpr (expr)}`))

We work by associating a regular expression with a function that will be used as a replace callback alongside that regex. Each such pair is run repeatedly until there are no more matches in the input.

It first handles grouping with parentheses (from the inside out), then exponentiation, then multiplication, division, and remainders, and finally addition and subtraction. This ordering is based on the standard JS operator precedence chart. The parentheses' groupings recurs internally before continuing, and all function recur on the remaining expression. Note that exponentiation, which associates right, has a little extra work to do, including the remainder of the string as a capture group, testing that it doesn't include any exponentiation operators; this might be better written with a negative look-ahead, but I'm not much of a regex expert. Note also that I use the caret (^) for an exponentiation operator; it should be easy enough to change to a double asterisk (**) if that's preferred.

For a complex expression, this is how it might proceed:

2 ^ 3 ^ (4 ^ 2 - 5 * 3 + 1) - (((2 + 2) * (2 * 5) ^ 2) + (2 * 5 * 7))
         4 ^ 2 - 5 * 3 + 1                                             // grouping
           16  - 5 * 3 + 1                                             // exponentiation
           16 - 15     + 1                                             // multiplication
              1        + 1                                             // subtraction 
                    2                                                  // addition 
2 ^ 3 ^             2       - (((2 + 2) * (2 * 5) ^ 2) + (2 * 5 * 7))
                                 2 + 2                                 // grouping
                                   4                                   // addition
2 ^ 3 ^             2       - ((   4 *    (2 * 5) ^ 2) + (2 * 5 * 7))
                                           2 * 5                       // grouping
                                             10                        // multiplication
2 ^ 3 ^             2       - ((   4 *       10   ^ 2) + (2 * 5 * 7))
                                   4 *       10   ^ 2                  // grouping
                                   4 *          100                    // exponentiation
                                          400                          // multiplication 
2 ^ 3 ^             2       - (           400          + (2 * 5 * 7))
                                                          2 * 5 * 7    // grouping
                                                           10   * 7    // multiplication
                                                              70       // multiplication  
2 ^ 3 ^             2       - (           400          +      70)
                                          400          +      70       // grouping
                                                    470                // addition
2 ^ 3 ^             2       -                       470                
2 ^ 9                       -                       470                // expoentiation
512                         -                       470                // exponentiation
                            42                                         // subtraction

Answer 3

You were very close. It needs to be a little more sophisticated.

Please read the comments inside the code to understand how it's working:

function evaluate(str) { 
  if (str.length === 0) {
    return ""
  }

  // Function to apply the operator from right to left
  const applyOperator = (operator, left, right) => {
    result = left;

    switch(operator) {
      case '+':
        result += right;
        break;
      case '-':
        result -= right;
        break;
      case '*':
        result *= right;
        break;
      case '/':
        // Avoid division by zero
        if(right !== 0) {
          result /= right;
        }
        break;
    }

    return result;
  }
  
  let result = 0;
  let numbers = "";
  let operator = null;

  for (let i = 0; i < str.length; i++) {
    let c = str[i]; // Isolate the character
    let isLast = i === str.length - 1; // Flag to check if we're on the last character

    // Ignore spaces or tabs
    if (c === ' ' || c === '\t') {
      continue;
    }

    // Check if c is a number
    if (!isNaN(parseInt(c))) {
      // If it's a number add it to the number builder
      numbers += c;

      // If it's not the last character then continue to the next character
      if(!isLast) {
        continue;
      }
    } 
    
    // Convert the numbers stack into an integer and reset the stack
    let number = parseInt(numbers);
    numbers = '';
    
    // If there was no operator before,
    // then just set the result with the number and store the operator for the next calculation
    if(operator === null) {
      result = number;
      operator = c;
    } else {
      // Apply the previous operator the the result using the number
      result = applyOperator(operator, result, number);
      // Store the current operator for the next calculation
      operator = c;
    }
  }

  return result;
}

document.getElementById('results').textContent = 
[
  "1 + 1",
  "1 - 1",
  "1 * 1",
  "1 / 1",
  "2 + 4 + 7",
  "5 - 7",
  "5 * 2 + 10",
  "10 - 20 + 30 * 2 / 10"
].map(exp => `${exp} = ${evaluate(exp)}`).join('\n');

<pre id="results"></pre>

EDIT

I don't think we are trying to implement some kind of compiling/interpreting engine here, but for the sake of the test result here is a version that executes each arithmetic operation in correct order *, /, -, +:

function evaluate(str) { 
  if (str.length === 0) {
    return ""
  }

  // Function to apply the operator from right to left
  const applyOperator = (operator, left, right) => {
    result = left;

    switch(operator) {
      case '+':
        result += right;
        break;
      case '-':
        result -= right;
        break;
      case '*':
        result *= right;
        break;
      case '/':
        // Avoid division by zero
        if(right !== 0) {
          result /= right;
        }
        break;
    }

    return result;
  }

  const passApply = (exp, opApply) => {
    let result = 0;
    let numbers = "";
    let operator = null;
    let prevWasOp = false;
    let sign = '';

    let parsed = '';

    for (let i = 0; i < exp.length; i++) {
      let c = exp[i]; // Isolate the character
      let isLast = i === exp.length - 1; // Flag to check if we're on the last character

      // Ignore spaces or tabs
      if (c === ' ' || c === '\t') {
        continue;
      }

      // Check if c is a number
      if (!isNaN(parseInt(c))) {
        // If it's a number add it to the number builder
        numbers += c;
        prevWasOp = false;

        // If it's not the last character then continue to the next character
        if(!isLast) {
          continue;
        }
      } else if(prevWasOp || i === 0) {
        // Checked for signed number
        if(/[\+-]/.test(c)) {
          sign = c;
          continue;
        }
        prevWasOp = false;
      }
      
      // Convert the numbers stack into an integer and reset the stack
      let number = parseInt(`${sign}${numbers}`);

      // Reset the sign if there was any
      sign = '';

      // If there was no operator before,
      // then just set the result with the number and store the operator for the next calculation
      if(operator === null) {
        result = number;
        operator = c;
        if(opApply !== operator) {
          parsed += `${numbers}${operator}`;
          result = 0;
        }
      } else {
        if(opApply === operator) {
          // Apply the previous operator the the result using the number
          result = applyOperator(operator, result, number);
          // Store the current operator for the next calculation
          
          if(c !== opApply) {
            parsed += `${result}`;
            if(!isLast) {
              parsed += `${c}`;
            }
            result = 0;
          }
          operator = c;
        } else {          
          if(c !== opApply) {
            parsed += `${numbers}`;
            if(!isLast) {
              parsed += `${c}`;
            }
          }
          operator = c;
          result = number;
        }
      }

      numbers = '';
      prevWasOp = ['+', '-', '*', '/'].indexOf(c) >= 0;
    }

    return parsed;
  }

  // Exeture each operator pass
  const mulPass = passApply(str, '*');
  const divPass = passApply(mulPass, '/');
  const subPass = passApply(divPass, '-');
  const addPass = passApply(subPass, '+');

  // Convert result to int and return the result
  return parseInt(result);
}

document.getElementById('results').textContent = 
[
  "1 + 1",
  "1 - 1",
  "1 * 1",
  "1 / 1",
  "2 + 4 + 7",
  "5 - 7",
  "5 * 2 + 10",
  "10 - 20 + 30 * 2 / 10",
  "1 + 5 * 2 + 12 * 2 * 2",
  "10 + 13 - 5 * 3 + 12 / 3 + 3"
].map(exp => {
  const result = evaluate(exp);
  return `${exp} = ${result}   eval(${result === eval(exp) ? 'OK' : 'ERROR'})`;
}).join('\n');

<pre id="results"></pre>