How do you figure out the structure of nested open close pairs based on their positions?
I have 2 arrays of open and closed positions like this:
closearr: (3) [3, 5, 6]
openarr: (3) [1, 2, 4]
For example from these values you can figure out the structure is something like this:
<tag>
<tag></tag>
<tag></tag>
</tag>
These values are their positions relative to each other. Since openarr[1] > closearr[0] for example you know that the second tag is nested within the first.
I'm trying to figure out an algorithm that will get me the index of the closing tag based on the index of the open tag. It should work for any type of nesting so long as the values are in the arrays.
function findClosingTag (openindex, openarr, closearr) { return close }
findClosingTag(1, openarr, closearr) should output 6
findClosingTag(2, openarr, closearr) should output 3
Another example of another set of values:
closearr: (3) [3, 6, 7, 8]
openarr: (3) [1, 2, 4, 5]
from here the structure you can figure out is like this:
<tag>
<tag></tag>
<tag>
<tag></tag>
</tag>
</tag>
So if I do
findClosingTag(4, openarr, closearr) should output 7
findClosingTag(1, openarr, closearr) should output 8
You can easily achieve solve this similarly like a bracket matching algorithm.
You have to sort it as per the position
If the type is open then you just have to push it into the stack
If the type is closed then you can grab the top item from the stack, and pop it. This is the paired tag that you are looking for
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)}`);