我正在努力解决我看到(但失败了)的算法问题。现在,我正在尝试了解如何解决这个问题。
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 <><<><>>
我的主要问题是如何处理输入字符串中的多个 < 字符,例如 <<。根据给出的例子,我最终会得到一些嵌套的尖括号,但我目前无法弄清楚如何做到这一点。
我可以解决示例输入,但是当我给它其他输入时,输出并不总是我所期望的(输入 #2 和输入 #6)。帮助将不胜感激。
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: ' + '<<<>>>');
最佳答案
为了简化事情,而不是使用堆栈数组,考虑使用只是一个数字:打开的数量<
到目前为止的标签。当 >
遇到,如果没有当前打开的标签,加一个<
到字符串的开头(同时将开放标记计数保持为 0)。然后,在最后,添加一个数字 >
s 匹配当前打开的标签数:
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: ' + '<><<<>>>');
关于javascript - 如何解决这个 "parse and balance angle brackets"问题? (JavaScript),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59097524/