{"id":27010,"date":"2018-01-02T20:44:07","date_gmt":"2018-01-02T15:14:07","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27010"},"modified":"2018-01-02T20:44:07","modified_gmt":"2018-01-02T15:14:07","slug":"check-balanced-parentheses-expression","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/check-balanced-parentheses-expression\/","title":{"rendered":"Check for balanced parentheses in an expression"},"content":{"rendered":"

Given an expression string exp , write a program to examine whether the pairs and the orders of \u201c{\u201c,\u201d}\u201d,\u201d(\u201c,\u201d)\u201d,\u201d[\u201c,\u201d]\u201d are correct in exp. <\/span>For example, the program should print true for exp = \u201c[()]{}{[()()]()}\u201d and false for exp = \u201c[(])\u201d<\/p>\n

Algorithm:<\/strong>
\n1) Declare a character stack S.
\n2) Now traverse the expression string exp.
\na) If the current character is a starting bracket (\u2018(\u2018 or \u2018{\u2018 or \u2018[\u2018) then push it to stack.
\nb) If the current character is a closing bracket (\u2018)\u2019 or \u2018}\u2019 or \u2018]\u2019) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.
\n3) After complete traversal, if there is some starting bracket left in stack then \u201cnot balanced\u201d<\/p>\n

Implementation:<\/p>\n

C Programming:<\/strong><\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%3Cstdio.h%3E%0A%23include%3Cstdlib.h%3E%0A%23define%20bool%20int%0A%20%0A%2F*%20structure%20of%20a%20stack%20node%20*%2F%0Astruct%20sNode%0A%7B%0A%20%20%20char%20data%3B%0A%20%20%20struct%20sNode%20*next%3B%0A%7D%3B%0A%20%0A%2F*%20Function%20to%20push%20an%20item%20to%20stack*%2F%0Avoid%20push(struct%20sNode**%20top_ref%2C%20int%20new_data)%3B%0A%20%0A%2F*%20Function%20to%20pop%20an%20item%20from%20stack*%2F%0Aint%20pop(struct%20sNode**%20top_ref)%3B%0A%20%0A%2F*%20Returns%201%20if%20character1%20and%20character2%20are%20matching%20left%0A%20%20%20and%20right%20Parenthesis%20*%2F%0Abool%20isMatchingPair(char%20character1%2C%20char%20character2)%0A%7B%0A%20%20%20if%20(character1%20%3D%3D%20\u2032(\u2018%20%26%26%20character2%20%3D%3D%20\u2032)\u2019)%0A%20%20%20%20%20return%201%3B%0A%20%20%20else%20if%20(character1%20%3D%3D%20\u2019%7B\u2019%20%26%26%20character2%20%3D%3D%20\u2019%7D\u2019)%0A%20%20%20%20%20return%201%3B%0A%20%20%20else%20if%20(character1%20%3D%3D%20\u2019%5B\u2019%20%26%26%20character2%20%3D%3D%20\u2019%5D\u2019)%0A%20%20%20%20%20return%201%3B%0A%20%20%20else%0A%20%20%20%20%20return%200%3B%0A%7D%0A%20%0A%2F*Return%201%20if%20expression%20has%20balanced%20Parenthesis%20*%2F%0Abool%20areParenthesisBalanced(char%20exp%5B%5D)%0A%7B%0A%20%20%20int%20i%20%3D%200%3B%0A%20%0A%20%20%20%2F*%20Declare%20an%20empty%20character%20stack%20*%2F%0A%20%20%20struct%20sNode%20*stack%20%3D%20NULL%3B%0A%20%0A%20%20%20%2F*%20Traverse%20the%20given%20expression%20to%20check%20matching%20parenthesis%20*%2F%0A%20%20%20while%20(exp%5Bi%5D)%0A%20%20%20%7B%0A%20%20%20%20%20%20%2F*If%20the%20exp%5Bi%5D%20is%20a%20starting%20parenthesis%20then%20push%20it*%2F%0A%20%20%20%20%20%20if%20(exp%5Bi%5D%20%3D%3D%20\u2019%7B\u2019%20%7C%7C%20exp%5Bi%5D%20%3D%3D%20\u2032(\u2018%20%7C%7C%20exp%5Bi%5D%20%3D%3D%20\u2019%5B\u2019)%0A%20%20%20%20%20%20%20%20push(%26stack%2C%20exp%5Bi%5D)%3B%0A%20%0A%20%20%20%20%20%20%2F*%20If%20exp%5Bi%5D%20is%20an%20ending%20parenthesis%20then%20pop%20from%20stack%20and%20%0A%20%20%20%20%20%20%20%20%20%20check%20if%20the%20popped%20parenthesis%20is%20a%20matching%20pair*%2F%0A%20%20%20%20%20%20if%20(exp%5Bi%5D%20%3D%3D%20\u2019%7D\u2019%20%7C%7C%20exp%5Bi%5D%20%3D%3D%20\u2032)\u2019%20%7C%7C%20exp%5Bi%5D%20%3D%3D%20\u2019%5D\u2019)%0A%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%2F*If%20we%20see%20an%20ending%20parenthesis%20without%20a%20pair%20then%20return%20false*%2F%0A%20%20%20%20%20%20%20%20%20if%20(stack%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20%20%20%20%20return%200%3B%20%0A%20%0A%20%20%20%20%20%20%20%20%20%2F*%20Pop%20the%20top%20element%20from%20stack%2C%20if%20it%20is%20not%20a%20pair%20%0A%20%20%20%20%20%20%20%20%20%20%20%20parenthesis%20of%20character%20then%20there%20is%20a%20mismatch.%0A%20%20%20%20%20%20%20%20%20%20%20%20This%20happens%20for%20expressions%20like%20%7B(%7D)%20*%2F%0A%20%20%20%20%20%20%20%20%20else%20if%20(%20!isMatchingPair(pop(%26stack)%2C%20exp%5Bi%5D)%20)%0A%20%20%20%20%20%20%20%20%20%20%20return%200%3B%0A%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20i%2B%2B%3B%0A%20%20%20%7D%0A%20%20%20%20%0A%20%20%20%2F*%20If%20there%20is%20something%20left%20in%20expression%20then%20there%20is%20a%20starting%0A%20%20%20%20%20%20parenthesis%20without%20a%20closing%20parenthesis%20*%2F%0A%20%20%20if%20(stack%20%3D%3D%20NULL)%0A%20%20%20%20%20return%201%3B%20%2F*balanced*%2F%0A%20%20%20else%0A%20%20%20%20%20return%200%3B%20%20%2F*not%20balanced*%2F%0A%7D%20%0A%20%0A%2F*%20UTILITY%20FUNCTIONS%20*%2F%0A%2F*driver%20program%20to%20test%20above%20functions*%2F%0Aint%20main()%0A%7B%0A%20%20char%20exp%5B100%5D%20%3D%20%22%7B()%7D%5B%5D%22%3B%0A%20%20if%20(areParenthesisBalanced(exp))%0A%20%20%20%20printf(%22%5Cn%20Balanced%20%22)%3B%0A%20%20else%0A%20%20%20%20printf(%22%5Cn%20Not%20Balanced%20%22)%3B%20%20%0A%20%20return%200%3B%0A%7D%20%20%20%20%0A%20%0A%2F*%20Function%20to%20push%20an%20item%20to%20stack*%2F%0Avoid%20push(struct%20sNode**%20top_ref%2C%20int%20new_data)%0A%7B%0A%20%20%2F*%20allocate%20node%20*%2F%0A%20%20struct%20sNode*%20new_node%20%3D%0A%20%20%20%20%20%20%20%20%20%20%20%20(struct%20sNode*)%20malloc(sizeof(struct%20sNode))%3B%0A%20%0A%20%20if%20(new_node%20%3D%3D%20NULL)%0A%20%20%7B%0A%20%20%20%20%20printf(%22Stack%20overflow%20%5Cn%22)%3B%0A%20%20%20%20%20getchar()%3B%0A%20%20%20%20%20exit(0)%3B%0A%20%20%7D%20%20%20%20%20%20%20%20%20%20%20%0A%20%0A%20%20%2F*%20put%20in%20the%20data%20%20*%2F%0A%20%20new_node-%3Edata%20%20%3D%20new_data%3B%0A%20%0A%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20new_node-%3Enext%20%3D%20(*top_ref)%3B%20%20%0A%20%0A%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20(*top_ref)%20%20%20%20%3D%20new_node%3B%0A%7D%0A%20%0A%2F*%20Function%20to%20pop%20an%20item%20from%20stack*%2F%0Aint%20pop(struct%20sNode**%20top_ref)%0A%7B%0A%20%20char%20res%3B%0A%20%20struct%20sNode%20*top%3B%0A%20%0A%20%20%2F*If%20stack%20is%20empty%20then%20error%20*%2F%0A%20%20if%20(*top_ref%20%3D%3D%20NULL)%0A%20%20%7B%0A%20%20%20%20%20printf(%22Stack%20overflow%20%5Cn%22)%3B%0A%20%20%20%20%20getchar()%3B%0A%20%20%20%20%20exit(0)%3B%0A%20%20%7D%0A%20%20else%0A%20%20%7B%0A%20%20%20%20%20top%20%3D%20*top_ref%3B%0A%20%20%20%20%20res%20%3D%20top-%3Edata%3B%0A%20%20%20%20%20*top_ref%20%3D%20top-%3Enext%3B%0A%20%20%20%20%20free(top)%3B%0A%20%20%20%20%20return%20res%3B%0A%20%20%7D%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

Time Complexity: O(n)
\nAuxiliary Space: O(n) for stack.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"

Check for balanced parentheses in an expression- Data Structure – Given an expression string exp , write a program to examine whether the pairs <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[73012,79607],"tags":[80614,80613,80615,80610,80616,80606,80608,80609,80611,80612,80607],"class_list":["post-27010","post","type-post","status-publish","format-standard","hentry","category-data-structures","category-stack","tag-balanced-parentheses-algorithm","tag-balanced-parentheses-geeksforgeeks","tag-balanced-parentheses-java","tag-balanced-parentheses-python","tag-balanced-parentheses-recursion","tag-balanced-parentheses-using-stack-in-java","tag-balanced-parentheses-without-stack","tag-check-for-balanced-parentheses-in-an-expression-in-python","tag-parenthesis-matching-algorithm","tag-parenthesis-matching-using-stack-in-c","tag-parenthesis-matching-using-stack-in-data-structure"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27010","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27010"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27010\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27010"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27010"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27010"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}