When you see it...

parentheses-and-palindromes.es6

// Inspired by:
//
// "Eh, have another semi-periodic reminder that ()() is not a palindrome but ())( is"
//
// --https://twitter.com/_julesh_/status/1101262745092218882

const END = Symbol('end');

class PushdownAutomaton {
  constructor(internal = 'start', external = []) {
    this.internal = internal;
    this.external = external;
    this.halted = false;
    this.recognized = false;
  }

  push(token) {
    this.external.push(token);
    return this;
  }

  pop() {
    this.external.pop();
    return this;
  }

  replace(token) {
    this.external[this.external.length - 1] = token;
    return this;
  }

  top() {
    return this.external[this.external.length - 1];
  }

  hasEmptyStack() {
    return this.external.length === 0;
  }

  transitionTo(internal) {
    this.internal = internal;
    return this;
  }

  recognize() {
    this.recognized = true;
    return this;
  }

  halt() {
    this.halted = true;
    return this;
  }

  consume(token) {
    return [...this[this.internal](token)];
  }

  fork() {
    return new this.constructor(this.internal, this.external.slice(0));
  }

  static evaluate (string) {
    let states = [new this()];

    for (const token of string) {
      const newStates = states
        .flatMap(state => state.consume(token))
        .filter(state => state && !state.halted);

      if (newStates.length === 0) {
        return false;
      } else if (newStates.some(state => state.recognized)) {
        return true;
      } else {
        states = newStates;
      }
    }

    return states
      .flatMap(state => state.consume(END))
      .some(state => state && state.recognized);
  }
}

function test (recognizer, examples) {
  for (const example of examples) {
    console.log(`'${example}' => ${recognizer.evaluate(example)}`);
  }
}

function test (recognizer, examples) {
  for (const example of examples) {
    console.log(`'${example}' => ${recognizer.evaluate(example)}`);
  }
}

class ParenthesisPalindrome extends PushdownAutomaton {
  * start(token) {
    if (token === '(') {
      yield this
        .fork()
        .push(token)
        .transitionTo('opening');
    }
    if (token === ')') {
      yield this
        .fork()
        .push(token)
        .transitionTo('opening');
    }
    if (token === END) {
      yield this
        .fork()
        .recognize();
    }
  }

  * opening(token) {
    if (token === '(') {
      yield this
        .fork()
        .push(token);
    }
    if (token === ')') {
      yield this
        .fork()
        .push(token);
    }
    if (token === '(' && this.top() === '(') {
      yield this
        .fork()
        .pop()
        .transitionTo('closing');
    }
    if (token === ')' && this.top() === ')') {
      yield this
        .fork()
        .pop()
        .transitionTo('closing');
    }
  }

  * closing(token) {
    if (token === '(' && this.top() === '(') {
      yield this
        .fork()
        .pop();
    }
    if (token === ')' && this.top() === ')') {
      yield this
        .fork()
        .pop();
    }
    if (token === END && this.hasEmptyStack()) {
      yield this
        .fork()
        .recognize();
    }
  }
}

test(ParenthesisPalindrome, [
  '()()',
  '())('
]);
  //=>
    '()()' => false
    '())(' => true