I am struggling with an algorithm problem I saw (and failed). Now, I am trying to understand how to solve the problem.
Question: Given a string of angle brackets, write a function that add brackets at the beginning and end of the string to make all brackets match. The angle brackets match if for every < there is a corresponding > and for every > there is a corresponding <.
The example input string : ><<><
The output string is <><<><>>
My main problem is how to handle multiple < characters in the input string, like <<. Based on the example given, I will end up with some nested angle brackets, but I am not currently able to figure out how to do this.
I can solve the example input, but when I give it other inputs, the output is not always what I am expecting (input #2 and input #6). Help would be appreciated.
const process = (strInput) => {
let strOutput = [];
let stack = [];
let popped ='';
for (let i = 0; i < strInput.length; i++) {
if (strInput[i] === '>') {
if (stack[stack.length - 1] === '<') {
popped = stack.pop();
strOutput.push(popped);
strOutput.push(strInput[i]);
} else {
strOutput.push('<');
strOutput.push(strInput[i]);
}
} else {
if (stack[stack.length - 1] === '<') {
strOutput.push('<');
stack.push(strInput[i]);
} else {
stack.push(strInput[i]);
}
}
}
// After string has been read, check the stack for <
for (let i = 0; i < stack.length; i++) {
strOutput.push('>');
}
return strOutput.join('');
};
let result = '';
console.log('Input 1: ><<><');
result = process('><<><');
console.log('Output 1: ' + result);
console.log('Expected Output 1: ' + '<><<><>>');
console.log('Input 2: <><<');
result = process('<><<');
console.log('Output 2: ' + result);
console.log('Expected Output 2: ' + '<><<>>');
console.log('Input 3: <><<<>');
result = process('<><<<>');
console.log('Output 3: ' + result);
console.log('Expected Output 3: ' + '<><<<>>>');
console.log('Input 4: <><<<><');
result = process('<><<<><');
console.log('Output 4: ' + result);
console.log('Expected Output 4: ' + '<><<<><>>>');
console.log('Input 5: ><<>');
result = process('><<>');
console.log('Output 5: ' + result);
console.log('Expected Output 5: ' + '<><<>>');
console.log('Input 6: ><<<');
result = process('><<<');
console.log('Output 6: ' + result);
console.log('Expected Output 6: ' + '<><<<>>>');
console.log('Input 7: >>>');
result = process('>>>');
console.log('Output 7: ' + result);
console.log('Expected Output 7: ' + '<<<>>>');
To simplify things, rather than using a stack array, consider using just a single number: the number of open < tags so far. When a > is encountered, if there are no current open tags, add a < to the beginning of the string (while keeping the open tag count at 0). Then, at the end, add a number of >s matching the number of currently open tags:
const process = (str) => {
let openCount = 0;
let additionalLeadingOpenTags = 0;
for (const char of str) {
if (char === '>') {
if (openCount === 0) {
additionalLeadingOpenTags++;
} else {
openCount--;
}
} else {
openCount++;
}
}
return '<'.repeat(additionalLeadingOpenTags) + str + '>'.repeat(openCount);
};
console.log('Input 1: ><<><');
result = process('><<><');
console.log('Output 1: ' + result);
console.log('Expected Output 1: ' + '<><<><>>');
console.log('Input 2: <><<');
result = process('<><<');
console.log('Output 2: ' + result);
console.log('Expected Output 2: ' + '<><<>>');
console.log('Input 3: <><<<>');
result = process('<><<<>');
console.log('Output 3: ' + result);
console.log('Expected Output 3: ' + '<><<<>>>');
console.log('Input 4: <><<<><');
result = process('<><<<><');
console.log('Output 4: ' + result);
console.log('Expected Output 4: ' + '<><<<><>>>');
console.log('Input 5: ><<>');
result = process('><<>');
console.log('Output 5: ' + result);
console.log('Expected Output 5: ' + '<><<>>');
console.log('Input 6: ><<<');
result = process('><<<');
console.log('Output 6: ' + result);
console.log('Expected Output 6: ' + '<><<<>>>');