{"id":461,"date":"2016-11-28T12:36:51","date_gmt":"2016-11-28T17:36:51","guid":{"rendered":"http:\/\/www.ferociouscoder.com\/blog\/?p=461"},"modified":"2016-11-28T12:37:42","modified_gmt":"2016-11-28T17:37:42","slug":"hackerrank-cracking-coding-interview-stacks-balanced-brackets","status":"publish","type":"post","link":"https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-stacks-balanced-brackets-461.html","title":{"rendered":"Hackerrank: Cracking the Coding Interview \u2013 Stacks: Balanced Brackets"},"content":{"rendered":"

This is again a classic problem of detecting matching parenthesis. In fact, the title even tells you the appropriate data structure to use in order to solve this problem. The solution relies on the fact that if a left bracket (by bracket in this post I mean ‘(‘, ‘[‘ or ‘{‘) is found we can push it on to the stack and eventually whenever the corresponding right bracket (‘)’, ‘]’ or ‘}’) is found then we would be popping it off the stack. If the stack is empty after we are done with the entire input then we know that the input string was balanced properly.<\/p>\n

The code I have written should be easy to understand but is a bit lengthy. In retrospect I could have refactored the checking and comparing part into a function so it looks nicer.<\/p>\n

FYI this is what all those characters are actually called:<\/p>\n

( ) – Parenthesis
\n{ } – Braces
\n[ ] – Brackets<\/p>\n

Problem: https:\/\/www.hackerrank.com\/challenges\/ctci-balanced-brackets<\/a><\/p>\n

Solution:<\/p>\n

\r\nimport java.io.*;\r\nimport java.util.*;\r\nimport java.text.*;\r\nimport java.math.*;\r\nimport java.util.regex.*;\r\n\r\npublic class Solution {\r\n    \r\n    public static boolean isBalanced(String expression) {\r\n        LinkedList<Character> stack = new LinkedList<>();\r\n        char[] input = expression.toCharArray();\r\n        for (int i=0; i<input.length; i++) {\r\n            if (stack.isEmpty()) {\r\n                stack.push(input[i]);\r\n            } else {\r\n                if (stack.peek() == '{') {\r\n                    if (input[i] == ']' || input[i] == ')') {\r\n                        return false;\r\n                    } else if (input[i] == '}') {\r\n                        stack.pop();\r\n                    } else {\r\n                        stack.push(input[i]);\r\n                    }\r\n                } else if (stack.peek() == '[') {\r\n                    if (input[i] == '}' || input[i] == ')') {\r\n                        return false;\r\n                    } else if (input[i] == ']') {\r\n                        stack.pop();\r\n                    } else {\r\n                        stack.push(input[i]);\r\n                    }\r\n                } else if (stack.peek() == '(') {\r\n                    if (input[i] == ']' || input[i] == '}') {\r\n                        return false;\r\n                    } else if (input[i] == ')') {\r\n                        stack.pop();\r\n                    } else {\r\n                        stack.push(input[i]);\r\n                    }\r\n                }\r\n            }\r\n        }\r\n        return stack.isEmpty();\r\n    }\r\n  \r\n    public static void main(String[] args) {\r\n        Scanner in = new Scanner(System.in);\r\n        int t = in.nextInt();\r\n        for (int a0 = 0; a0 < t; a0++) {\r\n            String expression = in.next();\r\n            System.out.println( (isBalanced(expression)) ? "YES" : "NO" );\r\n        }\r\n    }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
This is again a classic problem of detecting matching parenthesis. In fact, the title even tells you the appropriate data structure to use in order to solve this problem. The solution relies on the fact that if a left bracket (by bracket in this post I mean ‘(‘, ‘[‘ or ‘{‘) is found we can … Continue reading Hackerrank: Cracking the Coding Interview \u2013 Stacks: Balanced Brackets<\/span> →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":true,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[14,28,29,19],"tags":[42,33,32,20,41],"class_list":["post-461","post","type-post","status-publish","format-standard","hentry","category-algorithms","category-cracking-the-coding-interview","category-hackerrank","category-java","tag-balanced-parentheses","tag-ctci","tag-hackerrank","tag-java-2","tag-valid-parentheses"],"yoast_head":"\nHackerrank: Cracking the Coding Interview \u2013 Stacks: Balanced Brackets - Ferocious Coder<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-stacks-balanced-brackets-461.html\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Hackerrank: Cracking the Coding Interview \u2013 Stacks: Balanced Brackets - Ferocious Coder\" \/>\n<meta property=\"og:description\" content=\"This is again a classic problem of detecting matching parenthesis. In fact, the title even tells you the appropriate data structure to use in order to solve this problem. The solution relies on the fact that if a left bracket (by bracket in this post I mean ‘(‘, ‘[‘ or ‘{‘) is found we can … Continue reading Hackerrank: Cracking the Coding Interview \u2013 Stacks: Balanced Brackets →\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-stacks-balanced-brackets-461.html\" \/>\n<meta property=\"og:site_name\" content=\"Ferocious Coder\" \/>\n<meta property=\"article:published_time\" content=\"2016-11-28T17:36:51+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2016-11-28T17:37:42+00:00\" \/>\n<meta name=\"author\" content=\"Rawrosaur\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Rawrosaur\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/archives\\\/hackerrank-cracking-coding-interview-stacks-balanced-brackets-461.html#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/archives\\\/hackerrank-cracking-coding-interview-stacks-balanced-brackets-461.html\"},\"author\":{\"name\":\"Rawrosaur\",\"@id\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/#\\\/schema\\\/person\\\/1fb5cbee546cffd619a7b301e3dc447a\"},\"headline\":\"Hackerrank: Cracking the Coding Interview \u2013 Stacks: Balanced Brackets\",\"datePublished\":\"2016-11-28T17:36:51+00:00\",\"dateModified\":\"2016-11-28T17:37:42+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/archives\\\/hackerrank-cracking-coding-interview-stacks-balanced-brackets-461.html\"},\"wordCount\":329,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/#\\\/schema\\\/person\\\/1fb5cbee546cffd619a7b301e3dc447a\"},\"keywords\":[\"balanced parentheses\",\"ctci\",\"hackerrank\",\"java\",\"valid parentheses\"],\"articleSection\":[\"Algorithms\",\"Cracking the Coding Interview\",\"HackerRank\",\"Java\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/archives\\\/hackerrank-cracking-coding-interview-stacks-balanced-brackets-461.html#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/archives\\\/hackerrank-cracking-coding-interview-stacks-balanced-brackets-461.html\",\"url\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/archives\\\/hackerrank-cracking-coding-interview-stacks-balanced-brackets-461.html\",\"name\":\"Hackerrank: Cracking the Coding Interview \u2013 Stacks: Balanced Brackets - Ferocious Coder\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/#website\"},\"datePublished\":\"2016-11-28T17:36:51+00:00\",\"dateModified\":\"2016-11-28T17:37:42+00:00\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/archives\\\/hackerrank-cracking-coding-interview-stacks-balanced-brackets-461.html#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/archives\\\/hackerrank-cracking-coding-interview-stacks-balanced-brackets-461.html\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/archives\\\/hackerrank-cracking-coding-interview-stacks-balanced-brackets-461.html#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Hackerrank: Cracking the Coding Interview \u2013 Stacks: Balanced Brackets\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/#website\",\"url\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/\",\"name\":\"Ferocious Coder\",\"description\":\"RAWR!\",\"publisher\":{\"@id\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/#\\\/schema\\\/person\\\/1fb5cbee546cffd619a7b301e3dc447a\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/#\\\/schema\\\/person\\\/1fb5cbee546cffd619a7b301e3dc447a\",\"name\":\"Rawrosaur\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/1372156bd3b16de375c8727c2c617467bf6ff38f1679a7912f48286349c17e96?s=96&d=retro&r=pg\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/1372156bd3b16de375c8727c2c617467bf6ff38f1679a7912f48286349c17e96?s=96&d=retro&r=pg\",\"contentUrl\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/1372156bd3b16de375c8727c2c617467bf6ff38f1679a7912f48286349c17e96?s=96&d=retro&r=pg\",\"caption\":\"Rawrosaur\"},\"logo\":{\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/1372156bd3b16de375c8727c2c617467bf6ff38f1679a7912f48286349c17e96?s=96&d=retro&r=pg\"},\"sameAs\":[\"http:\\\/\\\/www.ferociouscoder.com\\\/\"],\"url\":\"https:\\\/\\\/www.ferociouscoder.com\\\/blog\\\/archives\\\/author\\\/admin\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Hackerrank: Cracking the Coding Interview \u2013 Stacks: Balanced Brackets - Ferocious Coder","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-stacks-balanced-brackets-461.html","og_locale":"en_US","og_type":"article","og_title":"Hackerrank: Cracking the Coding Interview \u2013 Stacks: Balanced Brackets - Ferocious Coder","og_description":"This is again a classic problem of detecting matching parenthesis. In fact, the title even tells you the appropriate data structure to use in order to solve this problem. The solution relies on the fact that if a left bracket (by bracket in this post I mean ‘(‘, ‘[‘ or ‘{‘) is found we can … Continue reading Hackerrank: Cracking the Coding Interview \u2013 Stacks: Balanced Brackets →","og_url":"https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-stacks-balanced-brackets-461.html","og_site_name":"Ferocious Coder","article_published_time":"2016-11-28T17:36:51+00:00","article_modified_time":"2016-11-28T17:37:42+00:00","author":"Rawrosaur","twitter_misc":{"Written by":"Rawrosaur","Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-stacks-balanced-brackets-461.html#article","isPartOf":{"@id":"https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-stacks-balanced-brackets-461.html"},"author":{"name":"Rawrosaur","@id":"https:\/\/www.ferociouscoder.com\/blog\/#\/schema\/person\/1fb5cbee546cffd619a7b301e3dc447a"},"headline":"Hackerrank: Cracking the Coding Interview \u2013 Stacks: Balanced Brackets","datePublished":"2016-11-28T17:36:51+00:00","dateModified":"2016-11-28T17:37:42+00:00","mainEntityOfPage":{"@id":"https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-stacks-balanced-brackets-461.html"},"wordCount":329,"commentCount":0,"publisher":{"@id":"https:\/\/www.ferociouscoder.com\/blog\/#\/schema\/person\/1fb5cbee546cffd619a7b301e3dc447a"},"keywords":["balanced parentheses","ctci","hackerrank","java","valid parentheses"],"articleSection":["Algorithms","Cracking the Coding Interview","HackerRank","Java"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-stacks-balanced-brackets-461.html#respond"]}]},{"@type":"WebPage","@id":"https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-stacks-balanced-brackets-461.html","url":"https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-stacks-balanced-brackets-461.html","name":"Hackerrank: Cracking the Coding Interview \u2013 Stacks: Balanced Brackets - Ferocious Coder","isPartOf":{"@id":"https:\/\/www.ferociouscoder.com\/blog\/#website"},"datePublished":"2016-11-28T17:36:51+00:00","dateModified":"2016-11-28T17:37:42+00:00","breadcrumb":{"@id":"https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-stacks-balanced-brackets-461.html#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-stacks-balanced-brackets-461.html"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.ferociouscoder.com\/blog\/archives\/hackerrank-cracking-coding-interview-stacks-balanced-brackets-461.html#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/www.ferociouscoder.com\/blog"},{"@type":"ListItem","position":2,"name":"Hackerrank: Cracking the Coding Interview \u2013 Stacks: Balanced Brackets"}]},{"@type":"WebSite","@id":"https:\/\/www.ferociouscoder.com\/blog\/#website","url":"https:\/\/www.ferociouscoder.com\/blog\/","name":"Ferocious Coder","description":"RAWR!","publisher":{"@id":"https:\/\/www.ferociouscoder.com\/blog\/#\/schema\/person\/1fb5cbee546cffd619a7b301e3dc447a"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.ferociouscoder.com\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":["Person","Organization"],"@id":"https:\/\/www.ferociouscoder.com\/blog\/#\/schema\/person\/1fb5cbee546cffd619a7b301e3dc447a","name":"Rawrosaur","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/1372156bd3b16de375c8727c2c617467bf6ff38f1679a7912f48286349c17e96?s=96&d=retro&r=pg","url":"https:\/\/secure.gravatar.com\/avatar\/1372156bd3b16de375c8727c2c617467bf6ff38f1679a7912f48286349c17e96?s=96&d=retro&r=pg","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/1372156bd3b16de375c8727c2c617467bf6ff38f1679a7912f48286349c17e96?s=96&d=retro&r=pg","caption":"Rawrosaur"},"logo":{"@id":"https:\/\/secure.gravatar.com\/avatar\/1372156bd3b16de375c8727c2c617467bf6ff38f1679a7912f48286349c17e96?s=96&d=retro&r=pg"},"sameAs":["http:\/\/www.ferociouscoder.com\/"],"url":"https:\/\/www.ferociouscoder.com\/blog\/archives\/author\/admin"}]}},"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p1mYMV-7r","jetpack_likes_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.ferociouscoder.com\/blog\/wp-json\/wp\/v2\/posts\/461","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.ferociouscoder.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.ferociouscoder.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.ferociouscoder.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.ferociouscoder.com\/blog\/wp-json\/wp\/v2\/comments?post=461"}],"version-history":[{"count":1,"href":"https:\/\/www.ferociouscoder.com\/blog\/wp-json\/wp\/v2\/posts\/461\/revisions"}],"predecessor-version":[{"id":462,"href":"https:\/\/www.ferociouscoder.com\/blog\/wp-json\/wp\/v2\/posts\/461\/revisions\/462"}],"wp:attachment":[{"href":"https:\/\/www.ferociouscoder.com\/blog\/wp-json\/wp\/v2\/media?parent=461"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.ferociouscoder.com\/blog\/wp-json\/wp\/v2\/categories?post=461"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.ferociouscoder.com\/blog\/wp-json\/wp\/v2\/tags?post=461"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}