Implement a function string balanceParanthesis(string s); which given a string s consisting of some parenthesis returns a string s1 in which parenthesis are balanced and differences between s and s1 are minimum.
Eg - "(ab(xy)u)2)" - "(ab(xy)u)2"
")))(((" - ""

Question

Implement a function string balanceParanthesis(string s); which given a string s consisting of some parenthesis returns a string s1 in which parenthesis are balanced and differences between s and s1 are minimum.
Eg - "(ab(xy)u)2)" -> "(ab(xy)u)2"
")))(((" -> ""

Chris · Accepted Answer

All we need to do is to delete unnecessary parenthesis.
every time we encounter a ')' which has no previous '(' to match with, delete.
delete every '(' left when we finished reading the string s.

xemoaya · Answer

def balanceParanthesis(str) :
    (bef, aft, left, right) = (0, 0, 0, 0)
    for i in str :
        if i == '(' :
            if right > 0 :
                bef += right
                right = 0
            left += 1
        elif i == ')' :
            if left > 0 :
                left -= 1
            else : 
                right += 1
    if right > 0 :
        bef += right
    if left > 0 :
        aft = left
    return '(' * bef + str + ')' * aft

Hussein · Answer

string justify(string str) {
	string s1 = "";
	int l = 0, i;
	
	for(i = 0; i  0) {
			l --;
			s1 += ')';
		}
		else if(str[i] == '(') {
			s1 += '(';
			l++;
		}
	}
	
	for(i = 0; i < l; i++) s1 += ')';
	
	return s1;
}

light · Answer

@xemoaya
try print balanceParanthesis(")))((("): you solution is wrong!! --> ((()))((()))

@hussein
try cout  ((()))

light · Answer

well according to the given examples, this code would do good

void balance(char *u)
{
  int n=strlen(u);
  int i=n-1;
  //modified string length
  for(;i>=0;--i)
  {
    if(u[i]=='(') --n;
    else break;
  }

  //remove extra right braces
  int l=0;
  for(int i=0;i

light · Answer

one small change needed 

  for(;l>0;--l,pos++)
  {
    output[pos]=')';
  }
  output[pos]='\0';
need to add extra ) at end

anon · Answer

how about simple balancing with an open count? close any that are unclosed. but before that run a round to delete leading ')' and trailing '(' which are be deemed unnecessary.

light · Answer

well in the above code
for(;i>=0;--i)
  {
    if(u[i]=='(') --n;
    else break;
  } 
part removes trailing '('
then ofcourse we are removing and extra ')' [ones not balanced by a '(']
finally if there were more {remember that by our approach we can never have more ')'}
'(' then we need to balance them with ')' that is what this part of the code does
for(;l>0;--l,pos++)
  {
    output[pos]=')';
  }
  output[pos]='\0';

this part compacts the  string, so we can do convert it inplace, if a standard technique to delete certain parts of a string is to fill those parts with '\0' and then compact the string
that is what this does
  int pos=0;
  for(int i=0;i

Anonymous · Answer

Use O(n) time and O(1) space.

Kandarp · Answer

import java.util.*;


class BalanceParanthesis
{
    static String getBalancedHelper(String input)
    {
        int count=0;
        for(int i=0;i0)     //'(' is extra
        {
            while(input.charAt(0)=='('&& count!=0)
            {
                input=input.substring(1,input.length());
                count--;
                if(input.length()==0)
                    break;
            }
            while(count!=0)
            {
                input+=")";
                count--;
            }
        }
        else if(count0)
        if(input.charAt(0)=='('&&input.charAt(input.length()-1)==')')
            input=input.substring(1,input.length()-1);
            return input;
    }
    static String getBalanced(String input)
    {
        Stack chars=new Stack();
        Stack index=new Stack();
        for(int i=0;i0)
                {
                    System.out.println("in partition");
                    return getBalancedHelper(input.substring(0,ind+1))+getBalancedHelper(input.substring(ind+1,input.length()));
                }
        }
        return getBalancedHelper(input);
    }
    public static void main(String[] st)
    {
        String input=")))(((";
            System.out.print(input+" result: "+getBalanced(input));
    }
}

anchan77 · Answer

def removeExtra(s,op,cl):
	count = 0
	out = ''
	for c in s:
		if c == op:
			count += 1
			out += c
		elif c == cl:
			if count > 0:
				count -= 1
				out += c
		else:
			out += c
	return out

def parenBalance(s):

	return removeExtra(removeExtra(s,'(',')')[::-1], ')', '(')[::-1]

may · Answer

No I think the correct form of ")))((("  is not "((()))" since you are not allowed to change the ordering of elements.  You change the ordering of original parenthesis. Even though you can change the ordering the difference between ((())) and )))((( is still 6.

iverson1407 · Answer

Actually I think there is some mistake in the question itself.
If the solution persue minimum difference, ")))(((" should lead to "((()))" since the difference between the input and output is 0. However, in the question ")))((("'s output is "", then the difference is 6.

Meta

Meta interview question

Interview Answers

Followed companies

Job searches

Bowls

Want the inside scoop on your own company?