如何解决这个“解析和平衡尖括号”的问题？（Javascript）

Question

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

问题：给定一串尖括号，编写一个函数，在字符串的开头和结尾添加括号，使所有括号匹配。如果每个 < 都有一个对应的 > 并且每个 > 都有一个对应的 <，则尖括号匹配。

示例输入字符串：><<><

输出字符串是<><<><>>

---

我的主要问题是如何处理输入字符串中的多个 < 字符，例如 <<。根据给出的例子，我最终会得到一些嵌套的尖括号，但我目前无法弄清楚如何做到这一点。

我可以解决示例输入，但是当我给它其他输入时，输出并不总是我所期望的（输入 #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

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