递归树函数遍历

Question

我有一个表示 Excel 函数的树，其中节点包含 name : function_name （例如 SUM）; type : function_type （函数或数字）;参数：函数_参数。对我来说，整个问题是参数可以是另一个函数。我已经有一个适用于简单函数的算法，但由于大量嵌套，参数会丢失。我想知道如何解决这个问题。我将在下面附上我的代码。

function getSubFormulas(node) {
  if (node.type === "function") {
    var args = node.arguments.map(arg => {
   console.log(arg)
      if (arg.arguments) {
        // Если аргумент - это массив, извлекаем свойство name из каждого элемента
        console.log(arg.arguments.map(subArg => getSubFormulas(subArg).name).join(","))
        return arg.name +"(" +arg.arguments.map(subArg => getSubFormulas(subArg).name).join(",") + ")";
      } else {
        // Если аргумент не является массивом, извлекаем свойство name
        return getSubFormulas(arg).name;
      }
    }).join(",");
    console.log(args + " args ")
    
    var name = `${node.name}(${args})`;
  //  console.log(name);
    const formula = {
      name: name,
      depth: node.depth
    };
    return [formula, ...node.arguments.filter((elem) => elem.type == "function").map(getSubFormulas).flat()];
  } else {
    if (node.operand == null) {
      let temp_name = node.value;
      return {name: temp_name}
    }
    let temp_name = 0 - node.operand.value;
    return {name : temp_name}
  }
}

公式 =SUM(MAX(3,5),AVERAGE (1,2,3,4,SUM(MAX(1,3),AVERAGE (SUM(2,3,4,4)),MAX(1 ,2,1,2,1,2)))),ABS(SUM(-7,4,1)))

看起来像 {"type":"function","name":"SUM","arguments":[{"type":"function","name":"MAX","arguments":[{"type ":"数字","值":3,"深度":2},{"类型":"数字","值":5,"深度":2}],"深度":1},{ “类型”：“函数”，“名称”：“平均值”，“参数”：[{“类型”：“数字”，“值”：1，“深度”：2}，{“类型”：“数字” ","值":2,"深度":2},{"类型":"数字","值":3,"深度":2},{"类型":"数字","值": 4,"深度":2},{"类型":"函数","名称":"SUM","参数":[{"类型":"函数","名称":"MAX","参数":[{"类型":"数字","值":1,"深度":4},{"类型":"数字","值":3,"深度":4}],"深度":3},{"类型":"函数","名称":"平均值","参数":[{"类型":"函数","名称":"SUM","参数":[{ “类型”：“数字”，“值”：2，“深度”：5}，{“类型”：“数字”，“值”：3，“深度”：5}，{“类型”：“数字” ","值":4,"深度":5},{"类型":"数字","值":4,"深度":5}],"深度":4},{"类型": “函数”，“名称”：“MAX”，“参数”：[{“类型”：“数字”，“值”：1，“深度”：5}，{“类型”：“数字”，“值":2,"深度":5},{"类型":"数字","值":1,"深度":5},{"类型":"数字","值":2,"深度":5},{"类型":"数字","值":1,"深度":5},{"类型":"数字","值":2,"深度":5}], "深度":4}],"深度":3}],"深度":2}],"深度":1},{"类型":"函数","名称":"ABS","参数":[{"类型":"函数","名称":"SUM","参数":[{"类型":"一元表达式","运算符":"-","操作数":{"类型":"数字","值":7},"深度":3},{"类型":"数字","值":4,"深度":3},{"类型":"数字","值":1,"深度":3}],"深度":2}],"深度":1}],"深度":0}

和预期产出

[{"名称":"SUM(MAX(3,5),AVERAGE(1,2,3,4,SUM(MAX(1,3)),AVERAGE(SUM(2,3,4,4),MAX (1,2,1,2,1,2)))),ABS(SUM(-7,4,1)))","深度":0,"分辨率":"11,1"},{ "名称":"MAX(3,5)","深度":1,"res":"5"},{"名称":"平均(1,2,3,4,SUM(,))" ,"深度":1,"分辨率":"2"},{"名称":"SUM(MAX(1,3),AVERAGE(,))","深度":2,"分辨率":"3 "},{"name":"MAX(1,3)","深度":3,"res":"3"},{"name":"AVERAGE(SUM(2,3,4,4) ,MAX(1,2,1,2,1,2))","深度":3,"分辨率":"7,5"},{"名称":"SUM(2,3,4,4 )","深度":4,"分辨率":"13"},{"名称":"MAX(1,2,1,2,1,2)","深度":4,"分辨率": "2"},{"name":"ABS(SUM(-7,4,1))","深度":1,"res":"2"},{"name":"SUM(-7) ,4,1)","深度":2,"分辨率":"-2"}]

Answer 1

这里我使用了两个函数，getFormula 递归地获取节点的公式，而 walkTree 递归地将输出对象构建到平面数组中。

const getFormula = (node) => {
  if (node.type === "function") { 
    return `${node.name}(${
      node.arguments.map(getFormula).join(",")
    })`;
  } else if (node.type === "unary-expression") {
    if (node.operator === "-") {
      return -node.operand.value;
    }
  } else {
    return node.value;
  }
};

const walkTree = (node, result=[], depth=0) => {
  if (node.type === "function") {
    result.push({
      name: getFormula(node),
      depth
    });
    if (node.arguments) {
      node.arguments.forEach(arg => walkTree(arg, result, depth + 1));
    }
  }
  return result;
};

let testNode = {
  "type": "function",
  "name": "SUM",
  "arguments": [
    {
      "type": "function",
      "name": "MAX",
      "arguments": [
        {
          "type": "number",
          "value": 3,
          "depth": 2
        },
        {
          "type": "number",
          "value": 5,
          "depth": 2
        }
      ],
      "depth": 1
    },
    {
      "type": "function",
      "name": "AVERAGE",
      "arguments": [
        {
          "type": "number",
          "value": 1,
          "depth": 2
        },
        {
          "type": "number",
          "value": 2,
          "depth": 2
        },
        {
          "type": "number",
          "value": 3,
          "depth": 2
        },
        {
          "type": "number",
          "value": 4,
          "depth": 2
        },
        {
          "type": "function",
          "name": "SUM",
          "arguments": [
            {
              "type": "function",
              "name": "MAX",
              "arguments": [
                {
                  "type": "number",
                  "value": 1,
                  "depth": 4
                },
                {
                  "type": "number",
                  "value": 3,
                  "depth": 4
                }
              ],
              "depth": 3
            },
            {
              "type": "function",
              "name": "AVERAGE",
              "arguments": [
                {
                  "type": "function",
                  "name": "SUM",
                  "arguments": [
                    {
                      "type": "number",
                      "value": 2,
                      "depth": 5
                    },
                    {
                      "type": "number",
                      "value": 3,
                      "depth": 5
                    },
                    {
                      "type": "number",
                      "value": 4,
                      "depth": 5
                    },
                    {
                      "type": "number",
                      "value": 4,
                      "depth": 5
                    }
                  ],
                  "depth": 4
                },
                {
                  "type": "function",
                  "name": "MAX",
                  "arguments": [
                    {
                      "type": "number",
                      "value": 1,
                      "depth": 5
                    },
                    {
                      "type": "number",
                      "value": 2,
                      "depth": 5
                    },
                    {
                      "type": "number",
                      "value": 1,
                      "depth": 5
                    },
                    {
                      "type": "number",
                      "value": 2,
                      "depth": 5
                    },
                    {
                      "type": "number",
                      "value": 1,
                      "depth": 5
                    },
                    {
                      "type": "number",
                      "value": 2,
                      "depth": 5
                    }
                  ],
                  "depth": 4
                }
              ],
              "depth": 3
            }
          ],
          "depth": 2
        }
      ],
      "depth": 1
    },
    {
      "type": "function",
      "name": "ABS",
      "arguments": [
        {
          "type": "function",
          "name": "SUM",
          "arguments": [
            {
              "type": "unary-expression",
              "operator": "-",
              "operand": {
                "type": "number",
                "value": 7
              },
              "depth": 3
            },
            {
              "type": "number",
              "value": 4,
              "depth": 3
            },
            {
              "type": "number",
              "value": 1,
              "depth": 3
            }
          ],
          "depth": 2
        }
      ],
      "depth": 1
    }
  ],
  "depth": 0
};

let result = walkTree(testNode);
console.log(result);