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:**

- Declare a stack (say
`stack`

). - 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`

.

- After complete traversal, if there is some starting bracket left in stack then the string is
`not balanced`

else we have a`balanced`

string.

This modified text is an extract of the original Stack Overflow Documentation created by following contributors and released under CC BY-SA 3.0

This website is not affiliated with Stack Overflow