DIY: Valid Parenthesis String

Problem statement

You are given a string named check. Your task is to find out if this string is valid. This string will only contain three type of characters i.e., (, ), and *.

A string is valid if it follows the following rules:

• Every left ( parenthesis must have a corresponding right ) parenthesis.

• Every right ) parenthesis must have a corresponding left ) parenthesis.

• Every Left parenthesis ( should appear before the corresponding right ) parenthesis.

• We can treat * as a single right or left parenthesis i.e., ( or ) or as an empty string " ".

Constraints

• The length of the string check will be in the range [1,100].
• Every check[i] will be either left (, or right ) parenthesis or an asterisk *.

Input

The input will be a string called check. The following are example inputs:

# Example 1
check = "()"

# Example 2
check = "(*)"

# Example 3
check = "((*)"

# Example 4
check = "(()"

Output

The output will be a boolean i.e, either True or False. The followings are sample outputs to the above inputs:

# Example 1
True

# Example 2
True

# Example 3
True

# Example 4
False

Coding exercise

You need to implement the function CheckValidString(check) in the skeleton code below.