Balanced Parentheses

StackString

Given a string containing only three types of characters: '(', ')' and '', write a function to check whether this string is valid. The string is valid if all open parentheses '(', are closed by a corresponding ')' before any excess closing bracket, and while accounting for asterisks '', which can be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.

Example 1

Input

[
  "(*)"
]

Output

true

Explanation. The asterisk can be treated as an empty string, making the parentheses effectively balanced.

Example 2

Input

[
  "((*)"
]

Output

true

Explanation. The asterisk acts as a right parenthesis, which balances all left parentheses.

Example 3

Input

[
  "((**)"
]

Output

true

Explanation. Both asterisks can act as right parentheses, balancing all left parentheses.

Example 4

Input

[
  "(()*"
]

Output

true

Explanation. The asterisk acts as a right parenthesis, balancing one of the left parentheses.

Example 5

Input

[
  ")*("
]

Output

false

Explanation. The first right parenthesis is unmatched making the string invalid.

Example 6

Input

[
  "(((*)"
]

Output

false

Explanation. There is one more left parenthesis than can be balanced by the available right parentheses and the asterisk.

Follow-up: Can this problem be solved using a different approach than the stack-based method? If so, what are these methods and how do they compare in performance?

Constraints:

The string size will be at least 1 and at most 100 characters. Each character is one of '(', ')', '*'.

Views: 3