8
\$\begingroup\$

This is my code for an assignment. The task is to take a user input in form of a sequence of parenthesis' followed by an E to mark its end and determine whether it is a correct sequence (as an example (()())E is correct, )(()((E is incorrect) and if incorrect determine how many parentheses at the start you need to remove and how many to add at the end for it to be correct.

The code works. But it's super long and I wondered if there were any improvements I could do on it.

public class Main {
  
  public static String enter(){     
    String enter = "";
    char nextValue ='A';
    while (nextValue!='E'){
      nextValue = In.readChar();
      enter += nextValue;
    }
    return enter;
  }
/*User Input. I know this could be done with ArrayList or scanner, but we haven't had these yet in classes. 
So I did it by converting the user inputs into a string, 
then storing that string into an array in main with "char []sequence = enter.toCharArray();"*/


  public static char[] removeParenthesisPairs(char[] a){
    for(int i=0; i<a.length; i++){
      if(a[i]=='('){
        a[i]='F';
        outerloop:
        for(int j=i+1; j<a.length;j++){
          if(a[j]==')'){
            a[j]='F';
            break outerloop;
          }
          if(j==a.length-1){
            a[i]='(';
          }
        }
      }
    }
    return a;
  }
/*I remove all the correct pairs from the sequence. I look for a ( and turn it into an F [to signal it's removed] 
and search the rest of the sequence for a ) and turn that into an F too. If there is no ) I turn the F back into (.
This part I really don't like, it looks super clunky. Also I have read that the "break outerloop"
thing I'm using here is bad practice, but I havent figured out any other way to accomplish the same result.*/
  

  
  public static boolean checkIfCorrect(char[] a){
    for(int i=0;i<a.length-1;i++){
      if(a[i]!='F'){
        return false;
      }
    }
    return true;
  }
/* I check if the sequence is correct. If there are only F left in the array, 
that means all entries were able to form pairs of () and the original sequence was correctly parenthesised.*/
  
  
   public static int subtract(char[] a){
    int count = 0;
    for(int i=0; i<a.length;i++){
      if(a[i]==')'){
        count += 1;
      }
    }
    return  count;
  }
// Check how many ) have to be subtracted at the beginning of the sequence.
  

  public static int add(char[] a){
    int count = 0;
    for(int i=0; i<a.length;i++){
      if(a[i]=='('){
        count += 1;
      }
    }
    return count;
  }
/*Check how many ( are still left in the sequence and need a ) added to form a pair.
I am kinda repeating myself here in the subtract() and add() methods, they are essentially doing
the same thing. The only way I have figured out for a method to return two values is by making
a class. But it seems even more convoluted to add new classes or is it preferable to this solution?*/
  
  public static void main(String[] args) {
    String enter= enter();
    char []sequence = enter.toCharArray();
    removeParenthesisPairs(sequence);
    boolean correct = checkIfCorrect(sequence);
    int additional = add(sequence);
    int removed = subtract(sequence);
    Out.println(correct);
    Out.println("removed = " + removed + " und additional = " + additional);
  }
/*I'm required by the assignment to have the boolean correct, int additional and int removed like this. 
So I can't just do "Out.println("removed = " + subtract(sequence)+ " und additional = " + add(sequence));"*/
}
\$\endgroup\$
1
  • 3
    \$\begingroup\$ What should happen for ())(E? Do you always remove things from the start up to the error, and add ) to balance it out (removed = 3, additional = 1)? Or do you scan through and say we're going to ignore 1 impossible ) then add one ) at the end to balance it (removed = 1, additional = 1)? \$\endgroup\$ – Jeremy Hunt Nov 19 '20 at 22:03
3
\$\begingroup\$

break is not a bad thing. Labels and goto are normally avoided. You are just breaking out of one loop, so you can just delete the outerloop: label and break; normally.


Comments at a method level are normally given with /** ... */ (JavaDoc syntax) above the method.


The trend is to avoid updating arrays in place (mutating), and instead just prefer returning new copies of the array (think of things as immutable), because when you mutate things it can sometimes be harder to keep track of state and easier to write incorrect code.

That's not to say it's wrong to do it with mutation. However, it might be better to keep mutation under control in the private parts of your code, so that if somebody re-uses your code, they don't have to worry about sequencing the method calls in the right order.


Presumably In is something provided by your course? Since I didn't have that, I just did the Scanner implementation to test with.


Here's your own code again, just with small changes as per the above comments, and formatted with 4 spaces (which seems to be more common these days).

import java.util.Scanner;

public class Main {

    public static void process(String s) {
        char[] sequence = s.toCharArray();
        removeParenthesisPairs(sequence);
        
        /*
         * I'm required by the assignment to have the boolean correct, int additional
         * and int removed like this. So I can't just do "Out.println("removed = " +
         * subtract(sequence)+ " und additional = " + add(sequence));"
         */
        boolean correct = checkIfCorrect(sequence);
        int additional = add(sequence);
        int removed = subtract(sequence);
        System.out.println(correct);
        System.out.println("removed = " + removed + " und additional = " + additional);
    }
    
    /**
     * I remove all the correct pairs from the sequence. I look for a ( and turn it
     * into an F [to signal it's removed] and search the rest of the sequence for a
     * ) and turn that into an F too. If there is no ) I turn the F back into (.
     * This part I really don't like, it looks super clunky.
     */
    private static char[] removeParenthesisPairs(char[] a) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] == '(') {
                a[i] = 'F';
                for (int j = i + 1; j < a.length; j++) {
                    if (a[j] == ')') {
                        a[j] = 'F';
                        break;
                    }
                    if (j == a.length - 1) {
                        a[i] = '(';
                    }
                }
            }
        }
        return a;
    }

    /**
     * I check if the sequence is correct. If there are only F left in the array,
     * that means all entries were able to form pairs of () and the original
     * sequence was correctly parenthesised.
     */
    private static boolean checkIfCorrect(char[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            if (a[i] != 'F') {
                return false;
            }
        }
        return true;
    }

    /**
     * Check how many ) have to be subtracted at the beginning of the sequence.
     */
    private static int subtract(char[] a) {
        int count = 0;
        for (int i = 0; i < a.length; i++) {
            if (a[i] == ')') {
                count += 1;
            }
        }
        return count;
    }

    /**
     * Check how many ( are still left in the sequence and need a ) added to form a
     * pair. I am kinda repeating myself here in the subtract() and add() methods,
     * they are essentially doing the same thing. The only way I have figured out
     * for a method to return two values is by making a class. But it seems even
     * more convoluted to add new classes or is it preferable to this solution?
     */
    private static int add(char[] a) {
        int count = 0;
        for (int i = 0; i < a.length; i++) {
            if (a[i] == '(') {
                count += 1;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            process(scanner.next());
        }
    }

}

Before I looked at your code, I attempted the problem myself. Here's what I came up with - take from it what you will or leave it. I think our two versions produce different outputs for some inputs - that could be different interpretations of the problem, or one of us has got bugs! (Edit: Actually, they do seem to be the same after all).

import java.util.Scanner;

public class Parens {

    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            System.out.print("Input: ");
            Parens.displayBalancing(scanner.next());
            System.out.println();
        }

        System.out.println("Extra tests cases");
        for (String test : new String[] { "(()())E", ")(()((E", "())(E" }) {
            Parens.displayBalancing(test);
        }
    }

    public static void displayBalancing(String s) {
        Parens.Changes changes = balance(s);
        System.out.format("removed: %-2d  additional:  %-2d correct: %-5b  input: %s\n",
                changes.removed, changes.additional, changes.isNoChanges(), s);
    }

    public static class Changes {
        int removed;
        int additional;

        Changes(int remove, int add) {
            this.removed = remove;
            this.additional = add;
        }

        public boolean isNoChanges() {
            return removed == 0 && additional == 0;
        }
    }

    public static Changes balance(String s) throws IllegalArgumentException {
        return balance(s.toCharArray(), 0, 0);
    }

    private static Changes balance(char[] characters, final int remove, final int add)
            throws IllegalArgumentException {
        int open = 0;
        for (char c : characters) {
            switch (c) {
            case '(':
                open++;
                break;
            case ')':
                if (open == -remove) {
                    // got close paren but none are open
                    return balance(characters, remove + 1, add);
                }
                open--;
                break;
            case 'E':
                if (open != add - remove) {
                    // got E but some parens are still open
                    return balance(characters, remove, add + 1);
                }
                // balanced
                return new Changes(remove, add);
            default:
                throw (new IllegalArgumentException(
                        String.format("Unexpected character '%c'", c)));
            }
        }
        throw (new IllegalArgumentException("String didn't contain an E"));
    }

}

Then I realised your approach was actually pretty good. This should work too:

    public static Changes balance2(String s) {
        while (s.contains("()")) {
            s = s.replace("()", "");
        }
        int remove = 0;
        int add = 0;
        for (char c: s.toCharArray()) {
            if (c == 'E') {
                break;
            } else if (c == '(') {
                add++;
            } else if (c == ')') {
                remove++;
            }
        }
        return new Changes(remove, add);
    }
\$\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.