【华为面试题】栈

思路

首先，遍历输入的压缩字符串。三种情况：
1.遇到字符 ‘{’：将其入栈。
2.遇到字符 ‘}’：计算重复次数，将栈中的字符组合成一个字符串，重复拼接后再入栈。
3.遇到字母字符：判断下一个字符是否是数字，若是数字，则将当前字母重复拼接后入栈；若不是数字，则直接将当前字母入栈。
最后，将栈中的字符串顺序拼接，得到解压缩后的字符串。

代码

function repeatString(str, times) {
  return str.repeat(times);
}

function decompressString(compressedStr) {
  let stack = [];

  for (let i = 0; i < compressedStr.length; i++) {
    let currentChar = compressedStr[i];

    // 当遇到开括号时，将其压入栈中
    if (currentChar === "{") {
      stack.push(currentChar);
    }
    // 当遇到闭括号时，从栈中取出对应的开括号之间的内容
    else if (currentChar === "}") {
      let pointer = i + 1;
      // 寻找闭括号后的数字，这代表了重复的次数
      while (
        pointer < compressedStr.length &&
        !isNaN(Number(compressedStr[pointer]))
      ) {
        pointer++;
      }

      let repeatTimes = Number(compressedStr.substring(i + 1, pointer));
      let contentToRepeat = "";

      // 从栈中提取并组装需要重复的内容
      while (stack[stack.length - 1] !== "{") {
        contentToRepeat = stack.pop() + contentToRepeat;
      }

      stack.pop(); // 移除开括号 "{"
      stack.push(repeatString(contentToRepeat, repeatTimes));
      i = pointer - 1; // 跳过处理过的数字
    }
    // 当遇到字母时
    else if (/[a-zA-Z]/.test(currentChar)) {
      let pointer = i + 1;
      // 寻找字母后的数字，这代表了重复的次数
      while (
        pointer < compressedStr.length &&
        !isNaN(Number(compressedStr[pointer]))
      ) {
        pointer++;
      }

      if (pointer !== i + 1) {
        let repeatTimes = Number(compressedStr.substring(i + 1, pointer));
        stack.push(repeatString(currentChar, repeatTimes));
        i = pointer - 1; // 跳过处理过的数字
      } else {
        stack.push(currentChar); // 如果字母后无数字，直接压入栈
      }
    }
  }
  return stack.join(""); // 合并栈内的内容为一个字符串
}

console.log(decompressString("{A3B1{C}3}3")); // 输出: AAABCCCAAABCCCAAABCCC