javascript - 如何解决这个 "parse and balance angle brackets"问题？ (JavaScript)

Question

我正在努力解决我看到(但失败了)的算法问题。现在，我正在尝试了解如何解决这个问题。

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: ' + '<<<>>>');

Answer 1

为了简化事情，而不是使用堆栈数组，考虑使用只是一个数字:打开的数量<到目前为止的标签。当 >遇到，如果没有当前打开的标签，加一个<到字符串的开头(同时将开放标记计数保持为 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: ' + '<><<<>>>');