1. Maison
  2. La question

Comment faire pour convertir cette arborescence dans un JS MemberExpression structure de l'arbre?

0

La question

J'ai trouvé une façon de représenter l'expression a.b[c.d][e].f[g[h[i.j]]] en utilisant ma propre forme d'arbre. Cette expression, représenté comme un arbre, qui ressemble à ceci:

{
  "form": "nest",
  "link": [
    {
      "form": "site",
      "name": "a"
    },
    {
      "form": "site",
      "name": "b"
    },
    {
      "form": "nest",
      "link": [
        {
          "form": "site",
          "name": "c"
        },
        {
          "form": "site",
          "name": "d"
        }
      ]
    },
    {
      "form": "nest",
      "link": [
        {
          "form": "site",
          "name": "e"
        }
      ]
    },
    {
      "form": "site",
      "name": "f"
    },
    {
      "form": "nest",
      "link": [
        {
          "form": "site",
          "name": "g"
        },
        {
          "form": "nest",
          "link": [
            {
              "form": "site",
              "name": "h"
            },
            {
              "form": "nest",
              "link": [
                {
                  "form": "site",
                  "name": "i"
                },
                {
                  "form": "site",
                  "name": "j"
                }
              ]
            }
          ]
        }
      ]
    }
  ]
}

Maintenant, la même expression de chaîne est également représentée par la JS AST structure arborescente pour le MemberExpression:

{
  "type": "MemberExpression",
  "object": {
    "type": "MemberExpression",
    "object": {
      "type": "MemberExpression",
      "object": {
        "type": "MemberExpression",
        "object": {
          "type": "MemberExpression",
          "object": {
            "type": "Identifier",
            "name": "a"
          },
          "property": {
            "type": "Identifier",
            "name": "b"
          },
          "computed": false
        },
        "property": {
          "type": "MemberExpression",
          "object": {
            "type": "Identifier",
            "name": "c"
          },
          "property": {
            "type": "Identifier",
            "name": "d"
          },
          "computed": false
        },
        "computed": true
      },
      "property": {
        "type": "Identifier",
        "name": "e"
      },
      "computed": true
    },
    "property": {
      "type": "Identifier",
      "name": "f"
    },
    "computed": false
  },
  "property": {
    "type": "MemberExpression",
    "object": {
      "type": "Identifier",
      "name": "g"
    },
    "property": {
      "type": "MemberExpression",
      "object": {
        "type": "Identifier",
        "name": "h"
      },
      "property": {
        "type": "MemberExpression",
        "object": {
          "type": "Identifier",
          "name": "i"
        },
        "property": {
          "type": "Identifier",
          "name": "j"
        },
        "computed": false
      },
      "computed": true
    },
    "computed": true
  },
  "computed": true
}

Donc, ces deux structures en arbre représentent la même expression de chaîne a.b[c.d][e].f[g[h[i.j]]]. Vous remarquerez sur la première "nid" de la structure, il y a deux types d'objets, des sites et des nids. Un site est juste un nom, tandis qu'un nid à "calculé" de la propriété en JS AST terminologie. Si un nid est comme parent[this_is_a_nest[and_another_nest]]tandis que parent.site1.site2.

Comment transformer la première structure de l'arbre dans le second?

Ce que j'ai à ce jour n'est pas vraiment y arriver, c'est assez déroutant.

console.log(JSON.stringify(transform(getNest()), null, 2))

function transform(nest) {
  let i = 0
  let stack = []
  while (i < nest.link.length) {
    let object = nest.link[i++]
    let property = nest.link[i]
    let member = {
      type: 'MemberExpression'
    }
    stack.push(member)

    if (object.form === 'nest') {
      member.object = transform(object)
    } else {
      member.object = {
        type: 'Identifier',
        name: object.name
      }
    }

    if (property) {
      if (property.form === 'nest') {
        member.property = transform(property)
        member.computed = true
      } else {
        member.property = {
          type: 'Identifier',
          name: property.name
        }
      }
    }
  }

  let object = stack.pop()
  while (stack.length) {
    let nextObject = stack.pop()
    nextObject.object = object
    object = nextObject
  }

  return object
}


function getNest() {
  return {
    "form": "nest",
    "link": [
      {
        "form": "site",
        "name": "a"
      },
      {
        "form": "site",
        "name": "b"
      },
      {
        "form": "nest",
        "link": [
          {
            "form": "site",
            "name": "c"
          },
          {
            "form": "site",
            "name": "d"
          }
        ]
      },
      {
        "form": "nest",
        "link": [
          {
            "form": "site",
            "name": "e"
          }
        ]
      },
      {
        "form": "site",
        "name": "f"
      },
      {
        "form": "nest",
        "link": [
          {
            "form": "site",
            "name": "g"
          },
          {
            "form": "nest",
            "link": [
              {
                "form": "site",
                "name": "h"
              },
              {
                "form": "nest",
                "link": [
                  {
                    "form": "site",
                    "name": "i"
                  },
                  {
                    "form": "site",
                    "name": "j"
                  }
                ]
              }
            ]
          }
        ]
      }
    ]
  }
}

Ne sais pas vraiment comment simplifier le problème en une manière de le résoudre encore.

Je ne sais pas si c' est de toute aide (acornjs analyseur pour MemberExpression).

abstract-syntax-tree algorithm javascript tree
2021-11-23 13:04:34
3

La meilleure réponse

1

Cela devrait le faire:

function transform(treeNode) {
  if (treeNode.form == "site") {
    return {
      "type": "Identifier",
      "name": treeNode.name,
    };
  } else if (treeNode.form == "nest") {
    const [base, ...props] = treeNode.link;
    console.assert(base.form == "site");
    return props.reduce((lhs, rhs) => {
      if (rhs.form == "nest") {
        return {
          "type": "MemberExpression",
          "object": lhs,
          "property": transform(rhs), // returns MemberExpression or (if singleton) Identifier
          "computed": true,
        };
      } else if (rhs.form == "site") {
        return {
          "type": "MemberExpression",
          "object": lhs,
          "property": transform(rhs), // returns Identifier
          "computed": false,
        };
      }
    }, transform(base));
  }
}

Bien sûr, vous pouvez simplifier le réducteur à juste

props.reduce((lhs, rhs) => ({
  "type": "MemberExpression",
  "object": lhs,
  "property": transform(rhs),
  "computed": rhs.form == "nest",
}), transform(base));
2021-11-23 13:35:06
No way! Simplifiée, vous avez jusqu'à son strict essence! En fait je pense que je viens de recevoir trop, je vais poster ma réponse ainsi :D
Lance Pollard
Alors, quelle est votre technique, comment avez-vous comprendre si élégamment? Je dois dire que c'était assez difficile. En gros comment puis-je apprendre à être plus comme ce que vous avez fait :)
Lance Pollard
@LancePollard la Pensée fonctionnelle et grokking la récursivité permet de. Il était clair pour moi que cela a dû être une pure fonction, non pas à l'aide d'une pile et de la boucle (même si en fait je n'ai même pas lu entièrement le code de votre tentative). Et il y a les deux sens de parcours: sur une propriété de la chaîne, l'autre dans les expressions imbriquées. Compte tenu de la chaîne est linéaire, ce qui pourrait être une simple pli sur le tableau pour générer le imbriquée MemberExpression liste liée, pour la nidification de la récursivité est nécessaire. Alors c'était juste une question de savoir si la réduire à gauche ou à droite et la façon de cas à le commencer
Bergi
1

Une courte solution récursive:

function mem_tree(objs){
    var o = null;
    for (var obj of objs){
       if (obj.form === 'site'){
          o = (o === null) ? {type:"Identifier", name:obj.name} : {type: "MemberExpression", object:o, property:{type:"Identifier", name:obj.name}, computed:false}
       }
       else{
          var r = mem_tree(obj.link);
          o = (o === null) ? {object:r} : {type: "MemberExpression", object:o, property:r, computed:true}
       }
    }
    return o;
}
var d = {'form': 'nest', 'link': [{'form': 'site', 'name': 'a'}, {'form': 'site', 'name': 'b'}, {'form': 'nest', 'link': [{'form': 'site', 'name': 'c'}, {'form': 'site', 'name': 'd'}]}, {'form': 'nest', 'link': [{'form': 'site', 'name': 'e'}]}, {'form': 'site', 'name': 'f'}, {'form': 'nest', 'link': [{'form': 'site', 'name': 'g'}, {'form': 'nest', 'link': [{'form': 'site', 'name': 'h'}, {'form': 'nest', 'link': [{'form': 'site', 'name': 'i'}, {'form': 'site', 'name': 'j'}]}]}]}]}
var result = mem_tree(d.link)
2021-11-24 05:25:09
0

Je viens de résoudre ce peu après @Bergi la réponse avant que je l'ai vu, tellement excité!

function transform(nest) {
  let i = 0
  let stack = [{
    type: 'Identifier',
    name: nest.link[i++].name
  }]
  while (i < nest.link.length) {
    const object = stack.shift()
    const node = nest.link[i++]
    if (node.form === 'nest') {
      const property = transform(node)
      stack.push({
        object: object,
        property,
        computed: true
      })
    } else {
      let property = {
        type: 'Identifier',
        name: node.name
      }
      stack.push({
        object: object,
        property: property,
        computed: false
      })
    }
  }

  return stack.shift()
}

La sortie est:

{
  "object": {
    "object": {
      "object": {
        "object": {
          "object": {
            "type": "Identifier",
            "name": "a"
          },
          "property": {
            "type": "Identifier",
            "name": "b"
          },
          "computed": false
        },
        "property": {
          "object": {
            "type": "Identifier",
            "name": "c"
          },
          "property": {
            "type": "Identifier",
            "name": "d"
          },
          "computed": false
        },
        "computed": true
      },
      "property": {
        "type": "Identifier",
        "name": "e"
      },
      "computed": true
    },
    "property": {
      "type": "Identifier",
      "name": "f"
    },
    "computed": false
  },
  "property": {
    "object": {
      "type": "Identifier",
      "name": "g"
    },
    "property": {
      "object": {
        "type": "Identifier",
        "name": "h"
      },
      "property": {
        "object": {
          "type": "Identifier",
          "name": "i"
        },
        "property": {
          "type": "Identifier",
          "name": "j"
        },
        "computed": false
      },
      "computed": true
    },
    "computed": true
  },
  "computed": true
}
2021-11-23 13:45:28

Dans d'autres langues

Cette page est dans d'autres langues

Русский
..................................................................................................................
Ссылка
Italiano
..................................................................................................................
Link
Polski
..................................................................................................................
Link
Română
..................................................................................................................
Legătură
한국어
..................................................................................................................
링크
हिन्दी
..................................................................................................................
लिंक
Türk
..................................................................................................................
Atıf
Česk
..................................................................................................................
Odka
Português
..................................................................................................................
Referênci
ไทย
..................................................................................................................
เชื่อมโยง
中文
..................................................................................................................
链接
Español
..................................................................................................................
Referencia
Slovenský
..................................................................................................................
Odkaz

Populaires dans cette catégorie

Questions populaires dans cette catégorie

Largeur À La Recherche De Boucle Infinie
Comment trouver les trois plus grands nombres dans un tableau?
Algorithme efficace pour le calcul de la plus rapide sur la distance de l'intervalle de
Besoin de vérifier si le tableau est trié en utilisant une fonction en C
Comment dois-je calculer l'écart type en python sans utiliser numpy?
Segmentation/Différenciation des surfaces réfléchissantes en images
Un arbre AVL avec la répétition des valeurs et de la double comparaison
c# identificateur de type existe, mais je suis toujours à obtenir une erreur qu'il est prévu [fermé]
c# fonction qui accepte entier n et revenir plus petit nombre qui peut diviser les numéros 1..n
À calculer, pour chaque objet du tableau en tableau séparé basé sur truthy état?