¿Cómo se determina la estructura de los pares abiertos y cerrados anidados en función de sus posiciones?
Tengo 2 matrices de posiciones abiertas y cerradas como esta:
closearr: (3) [3, 5, 6] openarr: (3) [1, 2, 4]Por ejemplo, a partir de estos valores, puede averiguar que la estructura es algo como esto:
<tag> <tag></tag> <tag></tag> </tag> Estos valores son sus posiciones relativas entre sí. Dado que openarr[1] > closearr[0] por ejemplo, sabe que la segunda etiqueta está anidada dentro de la primera.
Estoy tratando de encontrar un algoritmo que me proporcione el índice de la etiqueta de cierre en función del índice de la etiqueta abierta. Debería funcionar para cualquier tipo de anidamiento siempre que los valores estén en las matrices.
función findClosingTag (índice abierto, openarr, closearr) { volver cerrar }
findClosingTag(1, openarr, closearr) debe generar 6
findClosingTag(2, openarr, closearr) debe generar 3
Otro ejemplo de otro conjunto de valores:
closearr: (3) [3, 6, 7, 8] openarr: (3) [1, 2, 4, 5]a partir de aquí, la estructura que puedes descifrar es así:
<tag> <tag></tag> <tag> <tag></tag> </tag> </tag>entonces si lo hago
findClosingTag(4, openarr, closearr) debe generar 7
findClosingTag(1, openarr, closearr) debe generar 8
Puede lograr fácilmente resolver esto de manera similar a un algoritmo de coincidencia de corchetes.
Tienes que ordenarlo según la posición.
Si el type está open , solo tiene que empujarlo a la pila
Si el type está closed , puede tomar el elemento superior de la pila y abrirlo. Esta es la etiqueta emparejada que estás buscando.
function findClosingTag(pos, openArr, closedArr) { const closed = closedArr.map((position) => ({ type: 'closed', position })); const open = openArr.map((position) => ({ type: 'open', position })); const arr = [...open, ...closed].sort((a, b) => a.position - b.position); const stack = []; for (let { type, position } of arr) { if (type === 'open') stack.push(position); else { const lastOpenItemIndexInStack = stack.pop(); if (lastOpenItemIndexInStack === pos) return position; } } } const closearr = [3, 6, 7, 8]; const openarr = [1, 2, 4, 5]; console.log(findClosingTag(4, openarr, closearr)); Full Algorithm to find all pairs
function findAllMatchingTag(pos, openArr, closedArr) { const closed = closedArr.map((position) => ({ type: 'closed', position })); const open = openArr.map((position) => ({ type: 'open', position })); const arr = [...open, ...closed].sort((a, b) => a.position - b.position); const stack = []; let map = new Map(); for (let { type, position } of arr) { type === 'open' ? stack.push(position) : map.set(stack.pop(), position); } return map; } const closearr = [3, 6, 7, 8]; const openarr = [1, 2, 4, 5]; const allMatchingPairs = findAllMatchingTag(4, openarr, closearr); console.log(`2 - ${allMatchingPairs.get(2)}`); console.log(`1 - ${allMatchingPairs.get(1)}`); console.log(`4 - ${allMatchingPairs.get(4)}`); console.log(`5 - ${allMatchingPairs.get(5)}`);