A string w of parenthesis ( and ) is balanced if it satisfies one of the following conditions:

w is the empty string; w = (x) for some balanced string x; w = xy for some balanced strings x and y.

For example, the string w = ((())())(()((()))) is balanced, because x = ((())()) and y = (()((()))) are balanced.

(a) Describe (English description + pseudocode) and analyze (correctness + runtime) an algorithm to determine whether a given string of parenthesis is balanced.

(b) Describe (English description + pseudocode) and analyze (correctness + runtime) a greedy algorithm to compute the length of a longest balanced subsequence of a given string of parenthesis.

The input to each of the above problems is an array W[1..n] such that for each i we have W[i] =( or W [i] =). Both of the algorithms should run in O(n) time.

Progress: I know it is possible to use a stack to solve it, but I am not clear what's the difference between (a) and (b), seems like both of them can be solved by using one algorithm, and I don't know how to make the algorithm greedy(always choosing the optimal one).