LIKE CODING: MJ [39] Valid Parentheses

LIKE CODING: MJ [39] Valid Parentheses
Given a string with parentheses, return a string with balanced parentheses by removing the fewest characters possible. You cannot add anything to the string.
Examples:
balance("()") -> "()"
balance(")(") -> "".
balance("(((((") -> ""
balance("(()()(") -> "()()"
balance(")(())(") -> "(())"
Note：balance(")(())(") != "()()"
https://moonstonelin.wordpress.com/2015/03/23/given-a-string-with-parentheses-return-a-string-with-balanced-parentheses-by-removing-the-fewest-characters-possible/

public string Balance(string input)

{

    Stack<int> stack = new Stack<int>();

    HashSet<int> indexes = new HashSet<int>();

    int len = input.Length;

    for (int i = 0; i < len; i++)

    {

        char ch = input[i];

        if (ch == '(')

        {

            stack.Push(i);

        }

        else if (stack.Count > 0)

        {

            var top = stack.Pop();

            indexes.Add(top);

            indexes.Add(i);

        }

    }

    StringBuilder sb = new StringBuilder();

    for (int i = 0; i < len; i++)

    {

        if (indexes.Contains(i))

        {

            sb.Append(input[i]);

        }

    }

    return sb.ToString();

}

http://yuanhsh.iteye.com/blog/2194538

1. public String balance(String s) {  
2.     Stack<Integer> stack = new Stack<>();  
3.     StringBuilder sb = new StringBuilder(s);  
4.     for(int i=0; i<s.length(); i++) {  
5.         int c = s.charAt(i);  
6.         if(stack.isEmpty() || c == '(') {  
7.             stack.push(i);  
8.         } else {  
9.             int top = stack.peek();  
10.             if(s.charAt(top) == ')') {  
11.                 stack.push(i);  
12.             } else {  
13.                 stack.pop();  
14.             }  
15.         }  
16.     }  
17.     while(!stack.isEmpty()) {  
18.         sb.deleteCharAt(stack.pop());  
19.     }  
20.     return sb.toString();  
21. } 

string balance(string s){

    cout<<s<<":";

    int left = 0, n = s.size();

    for(int i=0; i<n; ++i){

        if(s[i]=='(') left++;

        else{

            if(left>0) left--;

            else s[i] = ' ';

        }

    }

    int right = 0;

    for(int i=n-1; i>=0; --i){

        if(s[i]==')') right++;

        else{

            if(right>0) right--;

            else s[i] = ' ';

        }

    }

    cout<<s<<endl;

    return s;

}

string balance1(string s){

    cout<<s<<":";

    stack<int> stk;

    string ret;

    int i = 0, n = s.size();

    while(i<n){

        if(stk.empty()||s[i]=='('){

            stk.push(s[i]);

            ++i;

        }else{

            string tmp;

            while(i<n && s[i]==')' && !stk.empty() && stk.top()=='('){

                tmp = "("+tmp+")";

                i++;

                stk.pop();

            }

            ret += tmp;

        }

    }

    cout<<ret<<endl;

    return ret;

}

X. http://blog.csdn.net/u010157717/article/details/44503017
思路：从左往右一遍，去掉多余的右括号。从右往左一遍，去掉多余的左括号。

 public String balance(String input) {
  if (input == null || input.isEmpty()) {
   return input;
  }
  String temp = removeRight(input);
  return removeLeft(temp);
 }

 private String removeLeft(String input) {
  StringBuffer result = new StringBuffer();
  int count = 0;
  for (int i = input.length() - 1; i >= 0; i--) {
   char ch = input.charAt(i);
   if (ch == ')') {
    result.append(')');
    count++;
   }
   else {
    if (count > 0) {
     result.append('(');
     count--;
    }
   }
  }
  return result.reverse().toString();
 }

 private String removeRight(String input) {
  StringBuffer result = new StringBuffer();
  int count = 0;
  for (int i = 0; i < input.length(); i++) {
   char ch = input.charAt(i);
   if (ch == '(') {
    result.append('(');
    count++;
   }
   else {
    if (count > 0) {
     result.append(')');
     count--;
    }
   }
  }
  return result.toString();
 }

Read full article from LIKE CODING: MJ [39] Valid Parentheses