递归连接由抽象语法树状结构形成的数组时遇到问题

Question

我有一个粗略的类似 AST 的结构；包含字符串或对象的数组，其中对象具有 ID 和参数，其中参数是字符串或对象的数组，如上所述。

目标是从连接的字符串和对象的字符串中输出一个字符串，递归构建（由于结构的性质）。

更复杂的是对象实际上是函数调用，具有不同的参数消耗。但是，输出始终是一个字符串。

我尝试了多种方法将这种类似 AST 的结构转换为字符串，但都没有成功；下面是我目前的尝试，但除了明显的输出冲突之外它不起作用，我无法弄清楚实现目标所需的确切逻辑。

const argLists = [
  [
    "one",
    { id: "$id1", args: [["two", "three"], "4", "3", "-"] },
    "four",
    "five",
    { id: "$id1", args: [["six", "seven"], "3", "4", "-"] }
  ],
  ["(", "$+", "", "$+", "text", "$+", "", "$+", ")", "-"],
  [
    {
      id: "$id1",
      args: [
        [
          "one",
          "$+",
          { id: "$+", args: ["two", { id: "$chr", args: ["44"] }, "three"] },
          "$+",
          "four"
        ],
        "4",
        "5",
        "-"
      ]
    }
  ]
]

function joinArgs(args = [], output) {
      for (let i = 0; i < args.length; i++) {
        let arg = args[i];
        if (typeof arg === "string") {
          i--;
          let tempOutput = "",
            prev = args[i] || "",
            join = "",
            next = args[i + 2] || "";
          if (typeof prev === "string" && typeof next === "string") {
            join += arg === "$+" ? "" : `${arg}`;
            tempOutput = `${prev}${join}${next}`;
          } else if (typeof prev === "string" && typeof next === "object") {
            tempOutput = `${prev}${join}${joinArgs(
              next.args,
              output
            )}`;
          } else if (typeof prev === "object" && typeof next === "string") {
            tempOutput = `${joinArgs(
              prev.args,
              output
            )}${join}${next}`;
          }
          i += 3;
          output += tempOutput;
        } else if (typeof arg === "object") {
          if (Array.isArray(arg)) {
            output += joinArgs(arg, output);
          } else {
            if (arg.id === "$+") {
              output += joinArgs(arg.args, output);
            } else if (arg.id === "$chr") {
              output += String.fromCharCode(arg.args[0]);
            } else if (arg.id === "$id1") {
              const id1Args = [];
              for (
                let id1ArgIdx = 0;
                id1ArgIdx < arg.args.length;
                id1ArgIdx++
              ) {
                let id1Arg = arg.args[id1ArgIdx];

                if (Array.isArray(id1Arg)) {
                  id1Arg = joinArgs(id1Arg, output).trim();
                }
                id1Args.push(id1Arg);
              }
              output +=
                " "
                // This function is irrelevant to the problem; but it does return a string
                //id1(
                //  ...id1Args.slice(0, id1Args.length - 1),
                //  id1Args[id1Args.length - 1]
                //);
            }
          }
        }
      }
      return output;
}

argLists.forEach(arg => {
  console.log(joinArgs(arg, ""));
});

测试用例的数据：

const argLists = [
  [
    "one",
    { id: "$id1", args: [["two", "three"], "4", "3", "-"] },
    "four",
    "five",
    { id: "$id1", args: [["six", "seven"], "3", "4", "-"] }
  ],
  ["(", "$+", "", "$+", "text", "$+", "", "$+", ")", "-"],
  [
    {
      id: "$id1",
      args: [
        [
          "one",
          "$+",
          { id: "$+", args: ["two", { id: "$chr", args: ["44"] }, "three"] },
          "$+",
          "four"
        ],
        "4",
        "5",
        "-"
      ]
    }
  ]
];

预期输出：

const output = [
    "one (two three 4 3 -) four five (six seven 3 4 -)",
    "(text) -",
    "(onetwo,threefour 4 5 -)"
];

应根据以下规则连接输出：

如果参数是一个字符串并且是一个 $+，则将前一个值和下一个值连接起来，它们之间没有 space(prevnext)。
如果参数是字符串而不是 $+，则将前一个值、当前值和下一个值与它们之间的 space 连接起来(prev current next)。
如果参数是一个对象，从 args 属性中获取它的参数并根据需要进行递归，但是：
1. 如果对象 ID 是 $+，加入所有不带 space 的参数，根据需要对每个参数进行递归。
2. 如果对象 ID 是 $chr，return String.fromCharCode() 提供给该静态方法的对象的唯一参数。
3. 如果object id是$id1，按照上面的规则把第一个参数当作一个数组（如果是数组的话），把剩下的所有参数用一个space连接起来，然后换行括号中的所有内容。
4. 从技术上讲，对象的 id 可能不是前三种可能性中的任何一种，但这种可能性不是问题，因为对象调用的函数总是 return 一个字符串。

Answer 1

这适用于您提供的所有测试用例。

每当 $+ 出现时，只需将其留在字符串中，然后在末尾替换所有出现的地方。这样就不必处理任何 'prev' 或 'next' 的事情，而这些事情确实会增加复杂性。对于下面的代码片段，它每次都会在递归函数 returns.

之前删除它们

关键是要记住递归函数首先是最深的递归函数调用 returns，在这种情况下，不断在堆栈中构建更大的字符串。这行代码，

outputString += "(" + joinArgs(current_arg.args) + ") ";

我真的认为有助于理解下面的代码是如何工作的。请注意，右括号后有一个尾随空白字符，如果右括号是最终字符串中的最后一个字符，则该空白字符将被删除。

const argLists = [
  [
    "one",
    { id: "$id1", args: [["two", "three"], "4", "3", "-"] },
    "four",
    "five",
    { id: "$id1", args: [["six", "seven"], "3", "4", "-"] }
  ],
  ["(", "$+", "", "$+", "text", "$+", "", "$+", ")", "-"],
  [
    {
      id: "$id1",
      args: [
        [
          "one",
          "$+",
          { id: "$+", args: ["two", { id: "$chr", args: ["44"] }, "three"] },
          "$+",
          "four"
        ],
        "4",
        "5",
        "-"
      ]
    }
  ]
];

function joinArgs(args = []) {
  outputString = "";
  for (let i = 0; i < args.length; i++) {
    var current_arg = args[i];

    //check for string condition
    if (typeof current_arg === 'string') {
      outputString += current_arg + " ";
    }

    //check for object condition
    if (typeof current_arg === "object") {

      if (current_arg.id == '$id1'){
        //if object has $id1 id, call joinArgs with the object's args as args parameter
        //surround object's returned output with parenthesis
        outputString += "(" + joinArgs(current_arg.args) + ") ";
      }

      //no recursive call needed here
      if (current_arg.id == '$chr') {
        outputString += "$+ " + String.fromCharCode(current_arg.args);
      }

      //call joinArgs with object args as args parameter
      if (current_arg.id == '$+') {
        outputString += joinArgs(current_arg.args);
      }

      // if object is array call joinArgs with the array as args paramater
      if (Array.isArray(current_arg)) {
        outputString += joinArgs(current_arg);
      }
    }
  }

  //clean up outputString to remove unwanted " $+ "
  outputString = outputString.replace(/ $\+ /g, "");
  //remove whitespace before closing parenthesis
  outputString = outputString.replace(/ \)/g, "\)");

  return outputString;
}




argLists.forEach(arg => {
  //trim leading and trailing whitespace
  astString = joinArgs(arg).trim();
  console.log(astString);
});

Answer 2

此版本将通用值的处理分为数组、普通对象和其他值（刚刚返回）的处理。主要 joinArg 函数调用 joinObject 和 joinArray,每一个都可以递归回调到joinArg.

我认为 joinObject 中的细分清楚地说明了如何在需要时添加其他案例。它还有一个用于默认处理的地方，您提到但没有指定。

const joinObject = ({id, args}) => (({
  '$+': (ns) => ns .map (joinArgs) .join (''),
  '$chr': ([n]) => String .fromCharCode (n),
  '$id1': ([ns, ...more]) => `(${joinArgs (ns)} ${more .map (joinArgs) .join (' ')})`,
}) [id] || ((args) => args .map (joinArgs) .join (' '))) (args)
//          `----------------------------------------' 
//                                `--- default.  Not sure what belongs here

const joinArray = (args) => args .reduce(
  ({str, skip}, arg) => ({
    str: str + (skip || arg == '$+' ? '' : ' ') + (arg == '$+' ? '' : joinArgs(arg)), 
    skip: arg == '$+'
  }),
  {str: '', skip: true}
).str

const joinArgs = (args) =>
  Array .isArray (args) 
    ? joinArray (args) 
  : Object (args) === args 
    ? joinObject (args) 
  : args


const argLists = [["one", {id: "$id1", args: [["two", "three"], "4", "3", "-"]}, "four", "five", {id: "$id1", args: [["six", "seven"], "3", "4", "-"]}], ["(", "$+", "", "$+", "text", "$+", "", "$+", ")", "-"], [{id: "$id1", args: [["one", "$+", {id: "$+", args: ["two", {id: "$chr", args: ["44"]}, "three"]}, "$+", "four"], "4", "5", "-"]}]]

argLists.forEach(args => console.log(joinArgs(args)))

这处理您提供的样品。我很好奇它是否满足了您的全部需求，或者是否仍需要针对其他情况进行调整。

这里的大技巧是相互递归。它可以很好地简化您在这种情况下编写的代码。另一个有用的技术是对象将处理程序保存到运行以获取不同的对象 id 值。我发现这对于将逻辑的主要部分与将它们粘合在一起的部分分开非常有用。

递归连接由抽象语法树状结构形成的数组时遇到问题

Trouble with recursively joining an array formed from an abstract syntax tree-like structure

javascript

recursion

abstract-syntax-tree