Valid Parenthesis String Check

Valid Parenthesis String Check

Given a string with '(', ')', and '*' (wildcard), determine if it can be a valid parentheses sequence.

Input format

The first line contains a string S (characters: (, ), *).

Output format

Print true if the string is valid (every ) has a matching (, * can be ), (, or empty), otherwise false.

Constraints

• Values fit in a 64-bit signed integer
• Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

()

true

(*)

true