Compression and Decompression challenge

decompress.js

// solution for https://techdevguide.withgoogle.com/paths/advanced/compress-decompression/#code-challenge

const assert = require('assert');

function isDigit(char) {
  return char >= '0' && char <= '9';
}

function isOpeningBrace(char) {
  return char === '[';
}

function isClosingBrace(char) {
  return char === ']';
}

function isLetter(char) {
  return (char >= 'a' && char <= 'z') || (char >= 'A' && char <= 'Z');
}

function tokenize(str) {
  const tokens = [];
  for (var i = 0; i < str.length; ) {
    var char = str[i];
    if (isDigit(char)) {
      let digit = '';
      while (isDigit(str[i])) {
        digit += str[i];
        i++;
      }
      tokens.push({
        type: 'number',
        value: parseInt(digit, 10),
      });
    }
    if (isLetter(char)) {
      let phrase = '';
      while (isLetter(str[i])) {
        phrase += str[i];
        i++;
      }
      tokens.push({
        type: 'phrase',
        value: phrase,
      });
    }
    if (isClosingBrace(char)) {
      tokens.push({
        type: ']',
      });
      i++;
    }
    if (isOpeningBrace(char)) {
      tokens.push({
        type: '[',
      });
      i++;
    }
  }
  return tokens;
}

function makeOperators(tokens) {
  let lastTokenType = null;
  const newTokens = [];
  tokens.map(token => {
    switch (token.type) {
      case '[':
        newTokens.push({
          type: '*',
        });
        break;
      case ']':
        break;
      case 'number':
        if (lastTokenType !== null && lastTokenType !== '[') {
          newTokens.push({
            type: '+',
          });
        }
        break;
      case 'phrase':
        if (lastTokenType == ']') {
          newTokens.push({
            type: '+',
          });
        }
    }
    lastTokenType = token.type;
    newTokens.push(token);
  });
  return newTokens;
}

function isOperatorToken(token) {
  return token.type === '+' || token.type === '*';
}

function printTokens(tokens) {
  console.log(tokens.map(token => token.value || token.type).join(' '));
}

function top(stack) {
  return stack[stack.length - 1];
}

function greaterOrEqualPrecedence(left, right) {
  if (left.type === right.type) {
    return true;
  }
  if (left.type === '+') {
    return false;
  }
  return true;
}

function convertToPostfix(tokens) {
  const stack = [];
  const queue = [];
  let token;
  while ((token = tokens.shift())) {
    if (token.type === 'phrase' || token.type === 'number') {
      queue.unshift(token);
    }
    if (token.type === '[') {
      stack.push(token);
    }
    if (isOperatorToken(token)) {
      while (
        top(stack) &&
        greaterOrEqualPrecedence(top(stack), token) &&
        top(stack).type !== '['
      ) {
        queue.unshift(stack.pop());
      }
      stack.push(token);
    }
    if (token.type === ']') {
      while (top(stack) && top(stack).type !== '[') {
        queue.unshift(stack.pop());
      }
      stack.pop();
    }
  }

  if (stack.length > 0) {
    queue.unshift(stack.pop());
  }

  return queue.reverse();
}

function compute(token, operand1, operand2) {
  switch (token.type) {
    case '+':
      return {
        type: 'phrase',
        value: operand2.value + operand1.value,
      };
    case '*':
      return {
        type: 'phrase',
        value: operand1.value.repeat(operand2.value),
      };
  }
}

function decompressTokens(tokens) {
  const stack = [];
  for (var token of tokens) {
    if (isOperatorToken(token)) {
      const operand1 = stack.pop();
      const operand2 = stack.pop();
      stack.push(compute(token, operand1, operand2));
    } else {
      stack.push(token);
    }
  }
  return stack.pop();
}

function decompress(str) {
  const tokens = makeOperators(tokenize(str));
  // console.log('infix');
  // printTokens(tokens);
  const postfixTokens = convertToPostfix(tokens);
  // console.log('postfix');
  // printTokens(postfixTokens);
  return decompressTokens(postfixTokens).value;
}

assert.equal(decompress('3[abc]'), 'abcabcabc');
assert.equal(decompress('3[abc]d'), 'abcabcabcd');
assert.equal(decompress('z3[abc]d'), 'zabcabcabcd');
assert.equal(decompress('3[abc]4[ab]c'), 'abcabcabcababababc');
assert.equal(decompress('10[a]'), 'aaaaaaaaaa');
assert.equal(decompress('2[3[a]b]'), 'aaabaaab');
assert.equal(decompress('0[abc]'), '');