javascript - 使用递归函数解决了 : How to implement build in function . eval()

Question

嘿编码器，

我有一个字符串“1+1”，在函数 eval() 中使用 javascript 构建我可以执行 eval("1+1") 所以返回值将是 2

但是如果我想在 javascript 中将这个概念实现到递归函数呢？

function evaluate(str) {

}

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

我试过的是

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))
      }
    }
  }
}

============

更新

我有多牛:)，现在这是我的答案(根据下面的解决方案)，谢谢大家

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

没有人工作!我知道 eval 会挽救我的一天，但在这种情况下，我需要解决这个案例，谢谢。

Answer 1

另一种方法是将您的字符串转换为一个可以作为堆栈求值的数组，然后对该堆栈进行简单的求值。例如，我们可以制作 "10 - 20 + 30 * 2 / 10"进入 [10, 20, "-", 30, "+", 2, "*", 10, "/"]然后通过将堆栈的顶部两个元素依次替换为应用于它们的当前操作的值来评估它。

此技术仅适用于从左到右的操作。它忽略运算符优先级，不能处理括号或非二元运算。但它可能足以满足您的需求。

这是一个实现:

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)}`))

replace , split , 和 map步骤一起将这个字符串变成一个准备处理的堆栈。 reduce step 实际上处理该数组，在堆栈上添加和删除元素。与 "10 - 20 + 30 * 2 / 10"成为 [10, 20, "-", 30, "+", 2, "*", 10, "/"] ，减少将如下进行:

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.

有很多方法可以扩展它。显然，添加新的二元运算是微不足道的。我们还可以通过替换 -2 来向缩减添加其他元操作(尽管将字符串转换为堆栈格式会更棘手)。与 -op.length 一起减少.如果我们想处理十进制数，我们可以将正则表达式更改为类似 /([-+*\/])(\s)*(\-?\d+(:?\.\d+)?)/g 的内容。 .

并向我们​​表示祝贺。我们刚刚写了 Forth interpreter 的开头!

更新

这个问题专门询问了如何递归地执行此操作，我编写了一个递归版本，总体上比上述更简单。但后来我意识到如何轻松扩展它以处理括号并尊重运算符优先级。它不再一定更简单，但它是一种有趣的方法，我们可以轻松地使用其他运算符和不同的优先级扩展它:

// 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)}`))

这种方法的一大优点是它可以轻松扩展到我们选择的任何数学运算符。并且还有进一步简化的空间。

更新 2

我对上次更新的代码并不满意。这个版本对我来说似乎更清晰，并且还增加了幂运算。这是它的第一遍:

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)}`))

我们通过将正则表达式与将用作 replace 的函数相关联来工作。与该正则表达式一起回调。每个这样的对都会重复运行，直到输入中不再有匹配项。

它首先处理带括号的分组(从内到外)，然后是求幂，然后是乘法、除法和余数，最后是加法和减法。此排序基于标准 JS operator precedence图表。括号的分组在继续之前在内部重复，并且所有函数在剩余的表达式上重复。请注意，与 right 相关联的求幂需要做一些额外的工作，包括将字符串的其余部分作为捕获组，测试它是否不包含任何求幂运算符；用负面的前瞻性来写这可能会更好，但我不是一个正则表达式专家。另请注意，我将插入符号 ( ^ ) 用于求幂运算符；如果愿意，更改为双星号 ( ** ) 应该很容易。

对于一个复杂的表达式，它可能是这样进行的:

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