Balance Parenthesis

Question

The function should return a string with balanced parenthesis. The code I wrote is working for all the inputs below. I am using stack data structure. I suppose this should work for all the edge cases. Can this solution be optimized further?

import java.util.ArrayList;
import java.util.Stack;

public class BalanceParenthesis {

    public static String balanceParenthesis(String input) {
        Stack<String> st = new Stack<>();
        ArrayList<Integer> indicesList = new ArrayList<Integer>();

        for (int i = 0; i < input.length(); i++) {
            if (st.isEmpty()) {
                if (input.charAt(i) == ')')
                    indicesList.add(i);
                if (input.charAt(i) == '(')
                    st.push("(" + i);
            } else {
                if ((input.charAt(i) == ')') && st.peek().charAt(0) == '(')
                    st.pop();
                if (input.charAt(i) == '(')
                    st.push("(" + i);
            }
        }

        while (!st.isEmpty())
            indicesList.add(Integer.parseInt(String.valueOf(st.pop().charAt(1))));

        StringBuffer buff = new StringBuffer();
        for (int i = 0; i < input.length(); i++) {
            if (!indicesList.contains(i))
                buff.append(input.charAt(i));

        }

        return buff.toString();

    }

    public static void main(String[] args) {

        System.out.println(balanceParenthesis("q(y)s)")); // q(y)s
        System.out.println(balanceParenthesis("(((((")); //""
        System.out.println(balanceParenthesis(")))"));  // ""
        System.out.println(balanceParenthesis("(()()(")); //()()
        System.out.println(balanceParenthesis(")())(()()(")); // ()()()     
        System.out.println(balanceParenthesis("((())))"));  //((()))

    }

}

Answer 1

1. You write information to the stack in two places, and both of them look like this:

   st.push("(" + i);
   

   That means st.peek().charAt(0) == '(' is always true, and you can remove it.

2. The only remaining place that reads the values in the stack reads

   st.pop().charAt(1)
   

   That means it isn’t necessary to add the parenthesis at all when pushing, and the stack can be a stack of Integers instead of Strings.

   Stack<Integer> st = new Stack<>();
   ArrayList<Integer> indicesList = new ArrayList<Integer>();
   
   for (int i = 0; i < input.length(); i++) {
       if (st.isEmpty()) {
           if (input.charAt(i) == ')')
               indicesList.add(i);
           if (input.charAt(i) == '(')
               st.push(i);
       } else {
           if (input.charAt(i) == ')')
               st.pop();
           if (input.charAt(i) == '(')
               st.push(i);
       }
   }
   
   while (!st.isEmpty())
       indicesList.add(st.pop());
   
   StringBuffer buff = new StringBuffer();
   for (int i = 0; i < input.length(); i++) {
       if (!indicesList.contains(i))
           buff.append(input.charAt(i));
   }
   
   return buff.toString();
   

   This is important for correctness, too, because integers could have been longer than one character. But now that’s fixed for free. Avoiding trips through data types that don’t really match up is good when possible.

3. input.charAt(i) is repeated, but it doesn’t have to be.

   for (int i = 0; i < input.length(); i++) {
       char c = input.charAt(i);
   
       if (st.isEmpty()) {
           if (c == ')')
               indicesList.add(i);
           if (c == '(')
               st.push(i);
       } else {
           if (c == ')')
               st.pop();
           if (c == '(')
               st.push(i);
       }
   }
   

4. st being empty only matters when the character is ')', and you do the same thing in either case when it’s '('. The conditions are more natural turned inside-out.

   if (c == '(') {
       st.push(i);
   } else if (c == ')') {
       if (st.isEmpty())
           indicesList.add(i);
       else
           st.pop();
   }
   

5. for (int i = 0; i < input.length(); i++) {
       if (!indicesList.contains(i))
           buff.append(input.charAt(i));
   }
   

   This loop has the potential to be very slow, because it searches indicesList for every character of the input. In total, that takes time proportional to the number of unbalanced parentheses multiplied by the length of the input. One way to avoid that is to replace indicesList with an array of booleans indicating whether the character at the same position should be excluded from the result:

   Stack<Integer> st = new Stack<>();
   boolean[] exclude = new boolean[input.length()];
   
   for (int i = 0; i < input.length(); i++) {
       char c = input.charAt(i);
   
       if (c == '(') {
           st.push(i);
       } else if (c == ')') {
           if (st.isEmpty())
               exclude[i] = true;
           else
               st.pop();
       }
   }
   
   while (!st.isEmpty())
       exclude[st.pop().intValue()] = true;
   
   StringBuffer buff = new StringBuffer();
   
   for (int i = 0; i < input.length(); i++) {
       if (!exclude[i])
           buff.append(input.charAt(i));
   }
   
   return buff.toString();
   

Answer 2

1) Use the java.util.Deque instead of the java.util.Stack

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example:

   Deque<Integer> stack = new ArrayDeque<Integer>();

Source: https://docs.oracle.com/javase/9/docs/api/java/util/Stack.html

2) Remove the "Integer" from the ArrayList section and use the List interface in the left section.

    List<Integer> indicesList = new ArrayList<>();

3) Instead of using the java.lang.String#charAt method, I suggest that you use an array and iterate on each instead.

        char[] charArray = input.toCharArray();
        for (int i = 0; i < charArray.length; i++) {
            char currentChar = charArray[i];

            if (st.isEmpty()) {
                if (currentChar == ')') {
                    indicesList.add(i);
                }
                if (currentChar == '(') {
                    st.push("(" + i);
                }
            } else {
                if ((currentChar == ')') && st.peek().charAt(0) == '(') {
                    st.pop();
                }
                if (currentChar == '(') {
                    st.push("(" + i);
                }
            }
        }

4) Create methods to check the type of parentheses

   //[...]
   public static String balanceParenthesis(String input) {
            if (st.isEmpty()) {
                if (isClosingParentheses(input.charAt(i))) {
                    indicesList.add(i);
                }
                if (isOpeningParentheses(input.charAt(i))) {
                    st.push("(" + i);
                }
            } else {
                if (isClosingParentheses(input.charAt(i)) && isOpeningParentheses(st.peek().charAt(0))) {
                    st.pop();
                }
                if (isOpeningParentheses(input.charAt(i))) {
                    st.push("(" + i);
                }
            }
   //[...]
   }


    private static boolean isOpeningParentheses(char currentChar) {
        return currentChar == '(';
    }

    private static boolean isClosingParentheses(char currentChar) {
        return currentChar == ')';
    }

5) Instead of using "if and else", you can use if-else-if and extract similar logic in methods.

            final boolean isDequeEmpty = st.isEmpty();
            final boolean isClosingParentheses = isClosingParentheses(currentChar);

            if (isDequeEmpty && isClosingParentheses) {
                indicesList.add(i);
            } else if (isDequeEmpty && isOpeningParentheses(currentChar)) {
                st.push("(" + i);
            } else if (!isDequeEmpty && isClosingParentheses) {
                st.pop();
            } else if (!isDequeEmpty && isOpeningParentheses(currentChar)) {
                st.push("(" + i);
            }

6) Use the java.lang.StringBuilder instead of the java.lang.StringBuffer

As of release JDK 5, this class has been supplemented with an equivalent class designed for use by a single thread, StringBuilder. The StringBuilder class should generally be used in preference to this one, as it supports all of the same operations but it is faster, as it performs no synchronization.

Source: https://docs.oracle.com/javase/9/docs/api/java/lang/StringBuffer.html

Answer 3

In addition to the other answers, I'm focusing on the main method.

It's great that you have provided example test cases with your code since the words "balance parentheses" leave much room for interpretation. By providing examples, you close this gap. Ideally you would add a few comments to the examples, for example why you expect exactly this output and what other outputs would be possible but not desired.

When you want to validate your tests, you currently have to inspect the output from System.out manually. That's error prone, especially for counting lots of parentheses. You can easily automate this by writing the following code:

private static void testBalanceParentheses(String input, String expectedOutput) {
    String actualOutput = balanceParenthesis(input);
    if (!Objects.equals(actualOutput, expectedOutput)) {
        throw new AssertionError(
            String.format(
                "Expected \"%s\" for \"%s\", but got \"%s\".",
                expectedOutput, input, actualOutput));
    }
}

private static void testBalanceParentheses() {
    testBalanceParentheses("q(y)s)", "q(y)s");
    testBalanceParentheses("(((((", "");
    testBalanceParentheses(")))", "");
    testBalanceParentheses("(()()(", "()()");
    testBalanceParentheses(")())(()()(", "()()()");
    testBalanceParentheses("((())))", "((()))");
}

public static void main(String[] args) {
    testBalanceParentheses();
}

This way, you just have to run the program, and if it outputs nothing, everything is fine.

This idea of having automated test cases is so popular that the JUnit project has developed a framework to make testing easier. When you use it, you don't have to write the low-level throw new AssertionError yourself, but can use the higher-level Assert.assertEquals method:

private static void testBalanceParentheses(String input, String expectedOutput) {
    String actualOutput = balanceParenthesis(input);
    Assert.assertEquals(expectedOutput, actualOutput);
}

@Test
void testBalanceParentheses() {
    testBalanceParentheses("q(y)s)", "q(y)s");
    testBalanceParentheses("(((((", "");
    testBalanceParentheses(")))", "");
    testBalanceParentheses("(()()(", "()()");
    testBalanceParentheses(")())(()()(", "()()()");
    testBalanceParentheses("((())))", "((()))");
}

See how the code gets shorter and simpler? That's what JUnit is for.

Finally, here is the test code with the additional comments I would add:

@Test
void testBalanceParentheses() {

    // Trailing closing parentheses are omitted.
    testBalanceParentheses("q(y)s)", "q(y)s");

    // Opening parentheses that don't get closed again are omitted as well.
    testBalanceParentheses("(((((", "");

    // Unmatched closing parentheses are omitted.
    testBalanceParentheses(")))", "");

    // TODO: Add another test case to demonstrate which of
    // the opening parentheses is omitted.
    // "a(b(c(d)e(f)g(h"
    // Do you expect "ab(c" or "a(bc"?
    testBalanceParentheses("(()()(", "()()");

    // TODO: Add another test case to demonstrate which of the
    // closing parentheses is omitted, like above.
    testBalanceParentheses(")())(()()(", "()()()");

    // Perfectly balanced nested parentheses are kept.
    testBalanceParentheses("((())))", "((()))");
}