1. Página principal
  2. Pregunta

Cómo convertir esta estructura de árbol en un JS MemberExpression de la estructura de árbol?

0

Pregunta

He descubierto una forma de representar la expresión a.b[c.d][e].f[g[h[i.j]]] el uso de mi propio formato de árbol. Esa expresión, representado como un árbol, se parece a esto:

{
  "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"
                }
              ]
            }
          ]
        }
      ]
    }
  ]
}

Ahora, esa misma expresión de cadena también está representado por este JS AST estructura de árbol para el 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
}

Así que esas dos estructuras de árbol representan la misma expresión de cadena a.b[c.d][e].f[g[h[i.j]]]. Te darás cuenta en la primera "nido" de la estructura, hay dos tipos de objetos, sitios y nidos. Un sitio es sólo un nombre, mientras que un nido significa un "calculada" de la propiedad en JS AST terminología. Así es como un nido parent[this_is_a_nest[and_another_nest]], mientras que parent.site1.site2.

¿Cómo se puede transformar la primera estructura de árbol en la segunda?

Lo que tengo hasta ahora no está realmente allí, es bastante confuso.

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"
                  }
                ]
              }
            ]
          }
        ]
      }
    ]
  }
}

No sé realmente cómo simplificar el problema en una forma para resolver todavía.

No sé si esto es de ayuda alguna (acornjs analizador para MemberExpression).

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

Mejor respuesta

1

Esto debe hacer es:

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));
  }
}

Por supuesto, usted puede simplificar el reductor sólo

props.reduce((lhs, rhs) => ({
  "type": "MemberExpression",
  "object": lhs,
  "property": transform(rhs),
  "computed": rhs.form == "nest",
}), transform(base));
2021-11-23 13:35:06
¡De ninguna manera! Usted simplificado que a su desnudo esencia! En realidad creo que yo sólo tengo demasiado, voy a publicar mi respuesta así :D
Lance Pollard
Entonces, ¿cuál fue tu técnica, ¿cómo lo solucionas con tanta elegancia? Yo tendría que decir que fue bastante complicado. Básicamente, ¿cómo puedo aprender a ser más como lo que hizo :)
Lance Pollard
@LancePollard Pensamiento funcional y grokking recursividad ayuda. Para mí era claro que tenía que ser una función pura, no uso de la pila y el lazo (aunque yo de hecho ni siquiera de leer completamente el código de su intento). Y hay dos direcciones de recorrido: uno abajo de una propiedad de la cadena, el otro en el anidado de expresiones. Dado que la cadena es lineal, lo que sería un simple pliegue en la matriz para generar el anidado MemberExpression lista enlazada, para la anidación de la recursividad es necesario. Entonces es sólo una cuestión de si la reducción a la izquierda o a la derecha y como caso especial el de comenzar
Bergi
1

Un corto solución recursiva:

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

Me acaba de resolver este ligeramente después de @Bergi la respuesta antes de que yo la vi, tan emocionada!

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 salida es:

{
  "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

En otros idiomas

Esta página está en otros idiomas

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

Popular en esta categoría

Las preguntas más habituales en esta categoría

La Amplitud De Búsqueda En Bucle Infinito
Cómo encontrar tres números más grandes en una matriz?
Algoritmo eficiente para calcular mejor tiempo en la distancia de intervalo
Comprobar si el array está ordenado el uso de una función en C
¿Cómo puedo calcular la desviación estándar de python sin el uso de numpy?
La segmentación de/la Diferenciación de las superficies reflectantes en las imágenes
Un árbol AVL con valores repetidos y doble comparación
c# identificador del tipo que existe, pero todavía estoy recibiendo un error que se espera [cerrado]
función de c# aceptar entero n y devuelva el número más bajo que se puede dividir números 1..n
Cómo calcular cada objeto de la matriz en la matriz independiente basado en truthy condición?