如何解决“解析和平衡尖括号”问题？ （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: ' + '<><<<>>>');

Answer 1

为了简化操作，而不是使用堆栈数组，请考虑使用just一个数字：到目前为止打开的<标签的数量。遇到>时，如果没有当前的打开标签，则在字符串的开头添加<（同时将打开标签的计数保持为0）。然后，最后添加与当前打开的标签数匹配的>个数：

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