使用堆栈的Bencode解析器

Question

我正在尝试使用一种基于堆栈的方法来解析一个编码的字符串。https:/www.bittorrent.orgbepsbep_0003.html

我的 psuedocode 无法处理有嵌套列表的情况，例如。[1, [2]]和 [[1, 2]] 都将返回 [[1 ,2]]，即使明明是不同的编码。"li1eli2eee" 与...相比 "lli1ei2eee".

以下是我目前的suedocode

input: string
output: map/list/integer/string in a bencoded data structure
first, tokenize the string into valid tokens
Valid tokens "d, l, [words], [numbers], e, s (virtual token)"
Strings are tokenized as 4:spam becomes "s spam e" with s being a virtual token
Eg. li1el4:spamee becomes [l i 1 e i 22 e l s spam e i 2 e e e]
Parsing:
make two stacks:
stack1
stack2
for token in tokens:

    if stack is empty
        return error

    if the token isn’t an “e”
        push token onto stack1

    while the stack isn’t empty:
        elem = pop off the stack
        if elem is “i”
            elem2 = pop elem off stack2 and check if it can be converted to an int
            if not
                return error
            push elem2 onto stack2 again
        elif elem is “d”
            make a new dict
            while stack2 isn’t empty:
                key = pop off stack2
                if stack2 is empty:
                    return error (because then we have an odd key value encoding)
                value = pop off stack2
                dict[key] = value
            push dict onto stack2
        elif elem is “l”
            make a new list
            while stack2 isn’t empty:
                append pop off stack2 to l
            push l onto stack2
        elif elem is “s”
            dont need to do anything :P
        else
            push elem onto stack2

if stack2 isn’t empty:
    ret = pop the lone element off stack2
if stack2 isn’t empty:
    return error

return ret

Answer 1

我不太懂规范或伪代码，但要实现 "Bencoding "的一个子集来处理你所展示的两个字符串（列表和整数）似乎很直接。据我所知，其他的东西都是比较琐碎的（dicts和list差不多，字符串和其他非递归定义的数据类型基本和ints一样）。

我的算法如下。

• 做一个堆栈，然后把一个空数组放进去。
• 对于本编码字符串中的每个索引。
  • 如果当前字符是 i，解析整数并将索引快进至 e 来关闭整数。将整数追加到堆栈顶部的数组中。
  • 如果当前字符是 l，将一个新的arr推到堆栈上。
  • 如果当前字符是 e，弹出堆栈，并将弹出的数组推到它下面的数组上（即新的顶部）。
• 返回栈中唯一的元素。

这里是JS中的内容。

const tinyBencodeDecode = s => {
  const stack = [[]];

  for (let i = 0; i < s.length; i++) {
    if (s[i] === "i") {
      for (var j = ++i; s[j] !== "e"; j++);

      stack[stack.length-1].push(+s.slice(i, j));
      i = j;
    }
    else if (s[i] === "l") {
      stack.push([]);
    }
    else if (s[i] === "e") {
      stack[stack.length-2].push(stack.pop());
    }
  }

  return stack[0];
};

[
  "i1ei2e",     // => [1, 2]
  "lli1ei2eee", // => [[1, 2]]
  "li1eli2eee", // => [[1, [2]]]

  // [44, [1, [23, 561, [], 1, [78]]], 4]
  "i44eli1eli23ei561elei1eli78eeeei4e",
].forEach(e => console.log(JSON.stringify(tinyBencodeDecode(e))));

没有进行错误处理，所有的东西都被认为是形式良好的，但是错误处理并不影响基本的算法，只是在你工作的时候添加一堆条件来检查索引，栈和字符串。

下面是一个（公认的懒惰）的例子，说明你如何支持这4种数据类型。同样，错误处理被省略了。这个想法基本上和上面的一样，只是需要更多的小题大做来确定我们是在构建一个字典还是一个列表。由于 null 根据规范，它似乎不是一个有效的键，我用它作为一个占位符来将值标记与相应的键配对。

在这两种情况下，如果发现bencoding只有一个根元素(list或dictionary)，就需要做一些小的调整。在这种情况下。s = "i42ei43e" 会在顶层无效，我们会从一个空栈开始。

const back = (a, n=1) => a[a.length-n];

const append = (stack, data) => {
  if (Array.isArray(back(stack))) {
    back(stack).push(data);
  }
  else {
    const emptyKey = Object.entries(back(stack))
                           .find(([k, v]) => v === null);

    if (emptyKey) {
      back(stack)[emptyKey[0]] = data;
    }
    else {
      back(stack)[data] = null;
    }
  }
};

const bencodeDecode = s => {
  const stack = [[]];

  for (let i = 0; i < s.length; i++) {
    if (s[i] === "i") {
      for (var j = ++i; s[j] !== "e"; j++);

      append(stack, +s.slice(i, j));
      i = j;
    }
    else if (/\d/.test(s[i])) {
      for (var j = i; s[j] !== ":"; j++);
      
      const num = +s.slice(i, j++);
      append(stack, s.slice(j, j + num));
      i = j + num - 1;
    }
    else if (s[i] === "l") {
      stack.push([]);
    }
    else if (s[i] === "d") {
      stack.push({});
    }
    else if (s[i] === "e") {
      append(stack, stack.pop());
    }
  }

  return stack[0];
};

[
  "i1ei2e",     // => [1, 2]
  "lli1ei2eee", // => [[1, 2]]
  "li1eli2eee", // => [[1, [2]]]
  "li1e4:spamli2eee", // => [[1, "spam", [2]]]

  // [[1, "spam", {"cow": "moo", "spam": {"eggs": [6, "rice"]}}, [2]]]
  "li1e4:spamd3:cow3:moo4:spamd4:eggsli6e4:riceeeeli2eee",

  // [44, [1, [23, 561, [], 1, [78]]], 4]
  "i44eli1eli23ei561elei1eli78eeeei4e",
].forEach(e => console.log(JSON.stringify(bencodeDecode(e))));