题目

Given a compressed string, return its original form.

For example.

uncompress('3(ab)') // 'ababab'
uncompress('3(ab2(c))') // 'abccabccabcc'

a number k followed by a pair of parenthesis, meaning to repeat the substring inside the parenthesis by k times, k is positive integer. inputs are guaranteed to be valid input like above example, there is no numerical digit in original form.

解析：

Intuition

Look at example 3(ab2(c)). At first, we see 3( which means we need to repeat 3 times anything that lies ahead. But how do we know the final status of what's next and how do we store the number of times we need to repeat it? It leads us to the fact we need to process the deepest string first, gradually returning to the beginning. This basically means we have 2 ways of doing it:

1. Recursion — on each ( we recursively call the function until we reach the bottom and then bubble, constructing the final string until we return to the beginning.
2. Stack — the same as recursion, but in an iterative manner. I like it more because we don't have to process parentheses.

About regexp

I use it only for simplicity to tokenize the number. The solution doesn't rely on regexp so we can easily replace it with a dictionary or something like this.

function uncompress(str) {
  let stack = [];
  let count = [];

  stack.push('');

  let i = 0;

  while (i < str.length) {
    let char = str[i];

    if (/\d/.test(char)) {
      let start = i;
      while (/\d/.test(str[i + 1])) i++;
      count.push(Number(str.substring(start, i + 1)));
    } else if (char === '(') {
      stack.push('');
    } else if (char === ')') {
      let times = count.pop();
      let str = stack.pop();
      let tmp = '';

      for (let j = 0; j < times; j++) tmp += str;

      stack.push(stack.pop() + tmp);
    } else {
      stack.push(stack.pop() + char);
    }

    i++;
  }

  return stack.pop();
}