Remove Minimum Parenthesis to Make it Balanced

题目：

Balance Parentheses就是remove最少的parenthesis使得剩下的parentheses是balanced。这道题只用返回一个结果。

解题思路：
这道题就是用stack来做，stack里面保留没有匹配左括号的index，如果有多出的右括号(stack为空的时候来了右括号)，那么就可以直接把该右括号的index加进结果里面。

代码：

public class RemoveMinimumParenthesistoMakeitBalanced {

    public List<Integer> remove(String s){
        List<Integer> rst = new ArrayList<>();
        if(s == null || s.length() == 0){
            return rst;
        }
        // stack will store the indexes of left parenthesis that have not been matched.        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i <= s.length() - 1; i++){
            if(s.charAt(i) == '('){
                stack.push(i);
            }
            else{
                if(stack.size() == 0){
                    rst.add(i);
                }
                else{
                    stack.pop();
                }
            }
        }
        while(stack.size() > 0){
            rst.add(stack.pop());
        }
        rst.sort((Integer i, Integer j) -> (i - j));
        return rst;
    }

}

JUnit Test:

public class RemoveMinimumParenthesistoMakeitBalancedTest {
    @Test    public void remove() throws Exception {
        RemoveMinimumParenthesistoMakeitBalanced removeMinimumParenthesistoMakeitBalanced = new RemoveMinimumParenthesistoMakeitBalanced();
        String s1 = "()(()(()";
        String s2 = "()())()";
        List<Integer> sample_rst1 = new ArrayList<>();
        List<Integer> sample_rst2 = new ArrayList<>();
        sample_rst1.add(2);
        sample_rst1.add(5);
        sample_rst2.add(4);
        List<Integer> rst1 = removeMinimumParenthesistoMakeitBalanced.remove(s1);
        List<Integer> rst2 = removeMinimumParenthesistoMakeitBalanced.remove(s2);
        assertEquals(rst1, sample_rst1);
        assertEquals(rst2, sample_rst2);
    }

}