A Deterministic Pushdown Automaton ("DPA") that recognizes balanced parentheses

balanced-dpa.es6

// The Deterministic Pushdown Automata Engine

const END = Symbol('end');
const RECOGNIZED = Symbol('recognized');
const UNRECOGNIZED = Symbol('unrecognized');
const POP = Symbol('pop');

function DPA (start) {
  return string => {
    const stack = [];
    
    let currentState = start;
    for (const token of string) {
      const top = stack[stack.length - 1];
      
      const action = currentState(token, top);
      
      if (typeof action === 'function') {
        currentState = action;
      } else if (action === POP) {
        stack.pop();
      } else if (action === RECOGNIZED) {
        return true;
      } else if (action === UNRECOGNIZED || action == null) {
        return false;
      } else {
        stack.push(action);
      }
    }
    
    const finalTop = stack[stack.length - 1];
    const finalAction = currentState(END, finalTop);
    return finalAction === RECOGNIZED;
  }
}

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

// A DPA that recognizes simple balanced parentheses strings

const start = (token, top) => {
  if (token === '(') {
    // pushes token
    return token;
  } else if (token === ')') {
    // the recognizer halts if the stack is empty
    return POP;
  } else if (token === END && top === undefined) {
    // the top is undefined if the stack is empty
    return RECOGNIZED;
  }
};

const balanced = DPA(start);

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

// A DPA that recognizes mutiple balanced parentheses strings

const startMultiple = (token, top) => {
  // open parentheses
  if (token === '(') {
    return token; // pushes '('
  } else if (token === '[') {
    return token; // pushes '['
  } else if (token === '{') {
    return token; // pushes '{'
  }
  
  // closed parentheses
  if (token === ')' && top === '(') {
    return POP;
  } else if (token === ']' && top === '[') {
    return POP;
  } else if (token === '}' && top === '{') {
    return POP;
  }
  
  // end
  if (token === END && top === undefined) {
    return RECOGNIZED;
  }
};
  
const multipleBalanced = DPA(startMultiple);

test(multipleBalanced, [
  '', '(', '()', '()()', '{()}',
	'([()()]())', '([()())())',
	'())()', '((())(())'
]);
  //=>
    '' => true
    '(' => false
    '()' => true
    '()()' => true
    '{()}' => true
    '([()()]())' => true
    '([()())())' => false
    '())()' => false
    '((())(())' => false