javascript - JavaScript 中子字符串的行为存在明显问题

Question

我正在编写一个递归算法，通过解析正则表达式来构建有限状态自动机。自动机迭代表达式，将字符插入堆栈，将运算符插入“运算符堆栈”。当我遇到“(”(表示分组操作)时，我将一个“子自动机”压入堆栈，并将模式的其余部分传递给子自动机进行解析。当该自动机遇到“)”时，它会将其余的模式传递给子自动机进行解析。字符串一直到父自动机以完成解析。这是代码:

var NFA = function(par) {
  this.stack = [];
  this.op_stack = [];
  this.parent = par;

};

NFA.prototype.parse = function(pattern) {
  var done = false;
  for(var i in pattern) {
    if (done === true) {
      break;
    }
    switch(pattern.charAt(i)) {
      case "(":
        var sub_nfa = new NFA(this);
        this.stack.push(sub_nfa);
        sub_nfa.parse(pattern.substring(i+1, pattern.length));
        done = true;
        break;
      case ")":
        if (this.parent !== null) {
          var len = pattern.length;
          /*TROUBLE SPOT*/
          this.parent.parse(pattern.substring(i, pattern.length));
          done = true;
          break;
        }
      case "*":
        this.op_stack.push(operator.KLEENE);
        break;
      case "|":
        this.op_stack.push(operator.UNION);
        break;
      default:
        if(this.stack.length > 0) {
          //only push concat after we see at least one symbol
          this.op_stack.push(operator.CONCAT);        
        }
        this.stack.push(pattern.charAt(i));
    }
  }
};

注意标有“麻烦点”的区域。给定正则表达式“(a|b)a”，调用 this.parent.parse 只会被调用一次:当子自动机遇到“)”时。此时，pattern.substring(i,pattern.length) = ")a"。这“有效”，但它不正确，因为在将字符串传递给父自动机之前我需要使用“)”输入。但是，如果我将调用更改为 this.parent.parse(pattern.substring(i+1,pattern.length)，则解析会得到空字符串!我已尝试单步执行代码，但无法解释这种行为。什么是我失踪了？

根据 Juan 的建议，我制作了一个快速的 jsfiddle 来显示尝试使用此算法解析“(a|b)a”时的问题。在“)”情况下，它使用 i 索引处的子字符串和 i+1 索引处的子字符串填充一个空 div。可以看出，虽然 i 处的子串有 2 个字符，但 i+1 处的子串却是空串!链接如下:http://jsfiddle.net/XC6QM/1/

编辑:我编辑了这个问题以反射(reflect)使用 charAt(i) 不会改变算法的行为的事实。

Answer 1

我认为之前的答案是正确的。但在我看来，这也存在一个相差一的错误。您不应该增加子字符串的索引吗？您不想在父解析中包含“)”，对吗？

this.parent.parse(pattern.substring(i + 1, pattern.length));

但是由于 Juan 提到的错误，这仍然会失败。测试此问题的快速临时修复是将 i 转换为数字:

this.parent.parse(pattern.substring(+i + 1, pattern.length));

这可能适合你。但您可能应该返回并放弃字符串上的 for-in 循环。我认为这就是造成你问题的原因。使用str.split('')将其转为数组，然后使用整数进行循环。这将防止进一步出现此类问题。