Wildcard Parentheses Validation

Problem Statement:

You are given a string (s) consisting of three types of characters: '(', ')' and ''. The character '' can be replaced with either '(', ')' or an empty string. Determine whether the string can be transformed into a valid parentheses string by replacing every '' with one of these possibilities.

A string is considered valid if it can be transformed into a well-formed sequence of parentheses. Formally, a string is valid if it satisfies the grammar:
[ S \rightarrow \epsilon \quad | \quad (S)S ]

For example, if (s = "()"), it can be transformed into "()" (by replacing '*' with an empty string) which is valid. Conversely, the string ")(" cannot be valid under any replacement.

Note: The solution involves a greedy two-pass scan, one from left-to-right and the other from right-to-left.

inputFormat

Input Format:
A single line containing a string (s) composed of characters '(', ')' and '*'.

outputFormat

Output Format:
Output a single line with either "True" if the string can be made valid, or "False" otherwise.## sample

()

True