Last active
February 16, 2019 16:39
-
-
Save raganwald/bd5bf98a1e2d85e65e4199869987c433 to your computer and use it in GitHub Desktop.
A Deterministic Pushdown Automaton ("DPA") that recognizes balanced parentheses
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment