Created
June 17, 2014 19:23
-
-
Save jeanlauliac/e234dda2e7fa249ed994 to your computer and use it in GitHub Desktop.
Solve the 'balanced delimiters' problem
This file contains 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
#!/usr/bin/env node | |
'use strict'; | |
var Delimiters = { | |
'[': ']' | |
, '(': ')' | |
, '{': '}' | |
} | |
// Javascript doesn't contain Sets, so we just use a map with booleans. | |
var Closers = { | |
']': true | |
, ')': true | |
, '}': true | |
} | |
// Checks that the string contains only matching delimiters. | |
// Delimiters are '(', '[' or '{' and their respective closing characters. | |
// See https://www.hackerrank.com/contests/programming-interview-questions/challenges/balanced-delimiters | |
// | |
// This algorithm time complexity is linear, that is, O(n). Space complexity is | |
// also linear in the worst case (eg. '[[[[[]]]]]'). A possible space | |
// improvement is to store a counter for consecutive similar delimiters in the | |
// stack, but it does not improve the worst case complexity | |
// (eg. '({[({[]})]})'). | |
// | |
function checkDelimiters(str) { | |
// We'll store all the expected closing characters in a stack. | |
var stack = [] | |
// Let's just go through the whole string. | |
for (var i = 0; i < str.length; ++i) { | |
// A closing character? | |
if (Closers.hasOwnProperty(str[i])) { | |
// If the stack is non-empty, and the character matches what we | |
// expect next (top of the stack), discard it and continue. | |
if (stack.length > 0 && str[i] === stack[stack.length - 1]) { | |
stack.pop() | |
continue | |
} | |
// Otherwise, that's a failure. | |
return false | |
} | |
// Ignore non-delimiter characters. | |
if (!Delimiters.hasOwnProperty(str[i])) | |
continue; | |
// Just push the expected closing character on our stack. | |
stack.push(Delimiters[str[i]]) | |
} | |
// If we went that far AND that we didn't expect more closing characters, | |
// that means the string is balanced. | |
return stack.length === 0 | |
} | |
// The boring stuff: reading and printing. | |
// | |
function processData(input) { | |
var res = checkDelimiters(input); | |
console.log(res ? 'True' : 'False'); | |
} | |
process.stdin.resume() | |
process.stdin.setEncoding('ascii') | |
var _input = '' | |
process.stdin.on('data', function (input) { | |
_input += input | |
}) | |
process.stdin.on('end', function () { | |
processData(_input) | |
}) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment