CareerCup

Store the position of '(' in another stack.The position should be the length of the output string at that point. If '(' needs to be printed in the output string, then we can get the entry position in the output string from the stackPos.

package careercup.questions.google;

import java.util.Scanner;
import java.util.Stack;

/**
 * Created by sibendu on 26/6/17.
 */
public class BalanceStringParanthesis {

    public static void main( String args[]) {

        Scanner sc = new Scanner(System.in);

        String str = sc.next();

        System.out.print(balanceParanthesis(str).toString());
    }

    private static StringBuilder balanceParanthesis(String str) {

        Stack<Character> stack = new Stack<>();
        Stack<Integer> stackPos = new Stack<>();

        StringBuilder output = new StringBuilder("");
        for ( int i = 0 ; i < str.length() ; i++)   {
            char curr = str.charAt(i);
            switch (curr)  {
                case '(' : stack.push('(');
                            stackPos.push(output.length());
                break;
                case ')' :
                    if ( stack.size() != 0) {
                        char ch = stack.pop();
                        int pos = stackPos.pop();
                        output.insert(pos , ch);
                        output.append(')');
                    }
                break;

                default:
                    output.append(curr);
                }
        }

        return output;
    }
}

void run(char[] a){
		int n = a.length;
		
		boolean[] valid = new boolean[n];
		Stack<Integer> sp = new Stack<Integer>();
		
		for(int i = 0; i < n; i++){
			if(a[i] == '(') sp.push(i);
			else if(a[i] == ')'){
				if(!sp.isEmpty() && a[sp.peek()] == '('){
					valid[i] = true;
					valid[sp.pop()] = true;
				}
			}
			else valid[i] = true;
		}
		
		for(int i = 0; i < n; i++)
			if(valid[i]) System.out.print(a[i]);
		System.out.println();
	}

void run(char[] a){
		int n = a.length;
			
		boolean[] valid = new boolean[n];
		Stack<Integer> sp = new Stack<Integer>();
		
		for(int i = 0; i < n; i++){
			if(a[i] == '(') sp.push(i);
			else if(a[i] == ')'){
				if(!sp.isEmpty() && a[sp.peek()] == '('){
					valid[i] = true;
					valid[sp.pop()] = true;
				}
			}
			else valid[i] = true;
		}
		
		for(int i = 0; i < n; i++)
			if(valid[i]) System.out.print(a[i]);
		System.out.println();
}

/* Balance Parentheris */
def is_balanced(string){
    !exists([0: size(string)/2 ] ) where {
        // when s[index] != s[-1-index] 
        string[$.o] != string[-1-$.o] 
    } 
}
def balance_paren(string){
    if ( is_balanced(string) ) { return string }
    // now, here... generates a multi set 
    m = mset(string.value)
    left_count = m[_'('] 
    right_count = m[_')'] 
    #(min,max) = minmax(left_count,right_count)
    // extract the bracket less string 
    s = fold(m.keys,'') as {  
         continue( $.o == _'(' || $.o == _')' )
         $.p += ( str($.o) ** m[$.o] ) 
        }
    // duplicate bracket-ness and... creare a balanced string
    ( '(' ** max ) + s + ( ')' ** max )     
}
println( balance_paren(@ARGS[0]) )

void run(char[] a){
int n = a.length;

boolean[] valid = new boolean[n];
Stack<Integer> sp = new Stack<Integer>();

for(int i = 0; i < n; i++){
if(a[i] == '(') sp.push(i);
else if(a[i] == ')'){
if(!sp.isEmpty() && a[sp.peek()] == '('){
valid[i] = true;
valid[sp.pop()] = true;
}
}
else valid[i] = true;
}

for(int i = 0; i < n; i++)
if(valid[i]) System.out.print(a[i]);
System.out.println();
}

Solution in python using a stack (promoted to a counter as we only have one type of parens). Regarding the input examples. For the input: '(((((' the output should be: '((((()))))' isn't?

def balanceParens(s):
    parens_stack = 0
    res = ''
    for c in s:
        if c == '(':
            parens_stack += 1
        elif c == ')':
            if parens_stack == 0: continue
            parens_stack -= 1
        res += c
    res += ')' * parens_stack
    return res

import java.util.Scanner;
import java.util.Stack;
public class BalancedParanthesis{
	
	public static void main(String args[]){
	
		Stack<Integer> stack= new Stack<Integer>();
		Scanner in= new Scanner(System.in);
		StringBuilder str = new StringBuilder(in.next());
		in.close();
		int i,n=str.length();
		for(i=0;i<n;i++){	
			if(str.charAt(i)=='(')
				stack.push(i);
			else if(str.charAt(i)==')'){	
					if(stack.isEmpty()){
						str.deleteCharAt(i--);
						n--;
					}
					else
						stack.pop();	
				}
		}
		while(!stack.isEmpty())
		{	
			str.deleteCharAt(stack.peek());
			stack.pop();
		}
		System.out.println(str);
	}
}

Couple of assumptions before we begin:
1) Will the string always have equal number of ( and )? If not then should we add extra missing braces to balance them? Thats the approach code below takes and runs in O(N) memory and O(N) time

public class Solution {
  public String balance(String str) {
    if(str == null || str.isEmpty() || (str.indexOf('(') < 0 && str.indexOf(')') < 0)) {
      return str;
    }

    StringBuilder sb = new StringBuilder();
    int rightCount = leftCount = remRight = remLeft = 0;
    for(Character c : str.toCharArray()) {
      if(c != '(' && c != ')') {
        sb.append(c);
        continue;
      }

      if(c == '(') {
        leftCount++;
      }
      else {
        if(leftCount > rightCount) {
          rightCount++;
        }
        else {
          remRight++;
          continue;
        }
      }
      sb.append(c);
    }
    // In case our input had unequal number of ( and )
    while(leftCount > rightCount) {
      sb.append(')');
      rightCount++;
      remRight--;
    }
    if(remRight > 0) {
      for(int i = 1; i <= remRight; i++) {
        sb.append('()');
      }
    }

    return sb.toString();
  }
}

import java.util.Arrays;
import java.util.Stack;

public class BalanceStringParentheses {

public static void main(String[] args){

System.out.println(balanceStringParentheses("a(b)"));
System.out.println(balanceStringParentheses("(((("));
System.out.println(balanceStringParentheses("(()())"));
System.out.println(balanceStringParentheses(")ab(()"));
}

public static String balanceStringParentheses(String input){

char[] inputChar = input.toCharArray();
Stack<Integer> openingParentheses = new Stack<Integer>();
boolean[] charToBeRemoved = new boolean[inputChar.length];
Arrays.fill(charToBeRemoved, false);

for(int i = 0 ; i < inputChar.length; i++)
{
if(inputChar[i] == '('){
openingParentheses.push(i);
}
else if(inputChar[i] == ')'){
if(!openingParentheses.empty())
{
openingParentheses.pop();
}
else{
charToBeRemoved[i] = true;
}
}
}

// if there are un matched opening parentheses remove them
while(!openingParentheses.empty()){
charToBeRemoved[openingParentheses.pop()] = true;
}

// now collect only the balanced chars.
StringBuilder sb = new StringBuilder();
for(int i = 0 ; i < inputChar.length; i++){
if(!charToBeRemoved[i]){
sb.append(inputChar[i]);
}
}

return sb.toString();
}
}

str= "((((ab)))))"
arr = list(str)
parenlist=[]
removelist = []

for i,v in enumerate(arr):
    if v=='(':
        parenlist.append(i)
    elif v==')':
        if len(parenlist) > 0:
            del parenlist[-1]
        else:
            removelist.append(i)
removelist += parenlist
for i in removelist:
    del arr[i]

print ''.join(arr)

string Balance(string const &s)
{
	unordered_set<int> remove_idxes;
	stack<int> st;
	for (int i = 0; i < s.size(); ++i) {
		if (s[i] == ')') {
			if (st.empty()) {
				remove_idxes.insert(i);
			} else {
				st.pop();
			}
		} else if (s[i] == '(') {
			st.push(i);
		}
	}
	while (!st.empty()) {
		remove_idxes.insert(st.top());
		st.pop();
	}
	string out;
	for (int i = 0; i < s.size(); ++i) {
		if (remove_idxes.find(i) == remove_idxes.end()) {
			out += s[i];
		}
	}
	return out;
}