Balanced Parentheses

StackString

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid and all the brackets are properly closed in the correct order. The string is considered valid if any open brackets are closed by the same type of brackets and in the correct order without any open brackets being left unclosed.

Example 1

Input

[
  "()"
]

Output

true

Explanation. Single type of pair, matching and correctly ordered.

Example 2

Input

[
  "()[]{}"
]

Output

true

Explanation. Multiple types of pairs, all matching and correctly ordered.

Example 3

Input

[
  "(]"
]

Output

false

Explanation. Parentheses are closed incorrectly.

Example 4

Input

[
  "([)]"
]

Output

false

Explanation. Multiple types, but closed in the wrong order.

Example 5

Input

[
  "{[]}"
]

Output

true

Explanation. Complex nesting, correctly closed in the correct order.

Example 6

Input

[
  "{[a](b)}"
]

Output

true

Explanation. Ignoring non-bracket characters, still correctly nested and ordered.

Follow-up: How would you extend your solution to handle other types of brackets or different characters?

Constraints:

The input string may contain characters that are not among '()', '{}', '[]'. These should be ignored when evaluating the string.

Views: 4