遞回物件的遞回搜索

我有一些看起來像這樣的資料：

const data = {
  "type": "A",
  "items": [
    {
      "type": "B",
      "tokens": [
        {
          "type": "C"
        }
      ]
    },
    {
      "type": "B",
      "tokens": {
        "type": "A",
        "items": [
          {
            "type": "B",
            "tokens": [
              {
                "type": "D"
              },
              {
                "type": "A",
                "items": [
                  "..."
                ]
              }
            ]
          },
          {
            "type": "B",
            "tokens": []
          }
        ]
      }
    }
  ]
}

資料邏輯如下

• Objects of typeA包含 field items，該欄位僅包含 type 的物件，B并且必須至少包含其中 1 個。
• 型別的物件B包含tokens欄位，它包含除所有型別的B，并且必須包含它們中的至少一種，例如：D，C或A。
• 該B.tokens還可以包含物件A包含另一個items等等。這可以重復 10 層以上的深度。
• 這兩個A.items和B.tokens是型別Token[]。

type Token =
    | Tokens.A
    | Tokens.B
    | Tokens.C

namespace Tokens {
  export interface A {
    type: "A";
    items: Token.B[];
  }
  export interface B {
    type:"B"
    tokens: Token[];
  }
  export interface C {
    type: "C";
    content: string;
  }
}

我正在嘗試獲取 typeB內不是 type的所有條目的陣列A。A里面的型別B.tokens應該是遞回檢查的，以找到里面的條目B不是A并且包括深度的索引。

如果有人可以通過指出解決問題的方法或偽代碼來幫助我，那將是非常有幫助的。

提前致謝。

@Mulan請求的更新What does the final output look like for the example provided?

像這樣的東西

{
  "id": 0,
  "collection": [
    {
      "type": "C",
      "content": "BLA",
      "depth": 1
    },
    {
      "type": "D",
      "content": "BLO",
      "depth": 2
    }
  ]
}

雖然木蘭的回答比我的詳細和準確得多，但我應迪馬的要求留下了我嘗試過的東西

const filterTokens = (tokens: Token[], filtered: Token[] = []): Token[] => {
    for (const token of tokens) {
        if (token.type === "A") {
            filterTokens(token.items, filtered);
        } else if (token.type === "B") {
            filterTokens(token.tokens, filtered);
        } else {
            filtered.push(token);
        }
    }
    return filtered;
}
console.log(filterTokens(data.items));

uj5u.com熱心網友回復：

相互遞回是處理樹的一種有效方法。我會用一些功能開始f接受輸入t和初始depth的0。我們執行一個簡單的型別分析t并宣告每種型別t應該如何展平為一個陣列。在這種特殊情況下，Array是唯一給予特殊考慮的一項，所有其他專案都可以視為單個專案 -

const f = (t, depth = 0) => {
  switch (t?.constructor) {
    case Array: return t.flatMap(v => f(v, depth))
    default: return f1(t, depth)
  }
}

當我們遇到單個專案時，我們將它傳遞給f1只處理一個專案的某個函式。在這里，我們做了一個節點型別的分析type性能，并宣布了每個型別A，B等等，應該扁平化-

const f1 = (t, depth = 0) => {
  switch (t?.type) {
    case "A": return f(t.items, depth   1)
    case "B": return f(t.tokens, depth   1)
    default: return [{...t, depth}]
  }
}

在您的模擬資料中，我進行了更改以使其與樹形保持一致-

// ellipses
"..."

// replaced with
{type:"Z",content:"..."}

console.log(f(data))

[
  {
    "type": "C",
    "depth": 2
  },
  {
    "type": "D",
    "depth": 4
  },
  {
    "type": "Z",
    "content": "...",
    "depth": 5
  }
]

這是一個完整的作業演示 -

const f = (t, depth = 0) => {
  switch (t?.constructor) {
    case Array: return t.flatMap(v => f(v, depth))
    default: return f1(t, depth)
  }
}

const f1 = (t, depth) => {
  switch (t?.type) {
    case "A": return f(t.items, depth   1)
    case "B": return f(t.tokens, depth   1)
    default: return [{...t, depth}]
  }
}

const data =
  {type:"A",items:[{type:"B",tokens:[{type:"C"}]},{type:"B",tokens:{type:"A",items:[{type:"B",tokens:[{type:"D"},{type:"A",items:[{type:"Z",content:"..."}]}]},{type:"B",tokens:[]}]}}]}

console.log(f(data))

標籤：

上一篇：CodilityOddOccurrencesInArray問題-遞回和Python

下一篇：有沒有辦法在不添加到呼叫堆疊的情況下呼叫函式？