3
\$\begingroup\$

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("((())))"));  //((()))

    }

}
\$\endgroup\$
4
\$\begingroup\$
  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();
    
\$\endgroup\$
2
  • \$\begingroup\$ Did you get the words in wrong order here? "integers could have been longer than one character" \$\endgroup\$ – TorbenPutkonen Dec 10 '19 at 6:49
  • \$\begingroup\$ @TorbenPutkonen: "(" + 12 gets read back as 1 by .charAt(1). \$\endgroup\$ – Ry- Dec 10 '19 at 6:59
0
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ What exactly do you gain by extracting ch == '(' into a separate method? The function that contains this code is short enough to be understandable on its own. At some point you do have to write the character literals when doing string processing. \$\endgroup\$ – Roland Illig Dec 10 '19 at 16:04
  • \$\begingroup\$ In your suggestions (1) and (2), you don't provide any rationale why your suggestion is better than the original code. Therefore it's difficult to see whether your suggestions make sense or in which other cases they apply. And by the way, to quote text that is not code, you should prefix it with > instead of backticks, which avoids the horizontal scrollbars. \$\endgroup\$ – Roland Illig Dec 10 '19 at 16:06
  • \$\begingroup\$ Hello Rolland, In my opinion, when you extract the comparison to a method, it adds visibility and remove the potential error, when reading the expression when there are lots of similar characters near each other. That's why i try to extract characters and string comparison to methods; it adds nothing more than the previous code, in terms of optimization. For the second comment, I didn't feel, at that time, the need to add more explanation than the provided link to the JavaDoc. I will try to explain more next time. Thanks for your remarks! \$\endgroup\$ – Doi9t Dec 10 '19 at 16:45
0
\$\begingroup\$

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("((())))", "((()))");
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.