如何使用递归函数实现内置函数.eval（）

问题描述 投票：3回答：3

Hei Coders，

我有一个字符串“ 1 + 1”，使用javascript内置函数eval（）我可以执行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))
      }
    }
  }
}

没有人工作！我知道eval会节省我的时间，但是在这种情况下，我需要解决此问题，谢谢。

javascript function recursion eval evaluate
3个回答
0
投票

你非常亲密。它需要更复杂一些。

请阅读代码中的注释以了解其工作方式：

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>

编辑

我不认为我们在这里尝试实现某种编译/解释引擎，但是出于测试结果的考虑，这里是一个以正确的顺序*, /, -, +执行每个算术运算的版本。

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>
0
投票

另一种方法是将您的字符串转换成可以作为堆栈进行评估的数组，然后对该堆栈进行简单评估。例如，我们可以将"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步骤实际上是处理该数组，在堆栈上添加和删除元素。当"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，将其他arity操作添加到缩减中（尽管将字符串转换为堆栈格式会比较棘手）。如果我们想处理十进制数字，我们可以将正则表达式更改为/([-+*\/])(\s)*(\-?\d+(:?\.\d+)?)/g。

并祝贺我们。我们刚刚写了Forth interpreter的开头！

0
投票

尝试此代码

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
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.