5. [10 points] Given a string S[1...2n] containing just the characters '(' and ')', de- sign an algorithm ISVALIDSTRING(S[1...2n]) to determine if the input string is valid. An input string is valid if the open brackets are closed in the proper order. Example: (()) is valid; (())() is valid; )()) is invalid; (())) is invalid; ()(( is invalid. (Hint: Use a stack to solve the problem.)

Fig: 1