data-structures Checking Balanced Parentheses


Example

A bracket is considered to be any one of the following characters: (, ), {, }, [, or ].

Two brackets are considered to be a matched pair if the an opening bracket (i.e., (, [, or {) occurs to the left of a closing bracket (i.e., ), ], or }) of the exact same type. There are three types of matched pairs of brackets: [], {}, and ().

A matching pair of brackets is not balanced if the set of brackets it encloses are not matched. For example, {[(])} is not balanced because the contents in between { and } are not balanced. The pair of square brackets encloses a single, unbalanced opening bracket, (, and the pair of parentheses encloses a single, unbalanced closing square bracket, ].

By this logic, we say a sequence of brackets is considered to be balanced if the following conditions are met:

It contains no unmatched brackets.

The subset of brackets enclosed within the confines of a matched pair of brackets is also a matched pair of brackets.

Algorithm:

  1. Declare a stack (say stack).
  2. Now traverse the string input.
  • a) If the current character is a starting bracket ( i.e. ( or { or [ ) then push it to stack.
  • b) If the current character is a closing bracket ( i.e. ) or } or ]) then pop from stack. If the popped character is the matching starting bracket then fine else parenthesis are not balanced.
  • c) If the current character is a closing bracket ( i.e. ) or } or ]) and the stack is empty, then parenthesis are not balanced.
  1. After complete traversal, if there is some starting bracket left in stack then the string is not balanced else we have a balanced string.