Valid Parenthesis String

Given a string s that consists only of the characters (, ), and *, decide whether every * can independently stand for: an opening parenthesis, a closing parenthesis, or no character at all, so that the transformed string becomes a valid parentheses sequence. A parentheses sequence is valid when it has an equal number of ( and ), and while reading from left to right the balance of unmatched ( never becomes negative. Example 1: Explanation: Both * characters can be treated as…