11
\$\begingroup\$

I need to complete a sequence of braces and brackets like [ ], ( ), { }, or reject the input. I can add braces/brackets only at the beginning or at the end.

Example:

input: '))[[([{([])}' output: '(())[[([{([])}])]]'
input: '[)[((({}[]'   output: 'rejected'

My implementation is based on using a stack (self-implemented to improve from standard Stack class, based on Vector), but certainly it can be done much better.

public class BraceCompliter {
    private static final char L_PAREN    = '(';
    private static final char R_PAREN    = ')';
    private static final char L_BRACE    = '{';
    private static final char R_BRACE    = '}';
    private static final char L_BRACKET  = '[';
    private static final char R_BRACKET  = ']';
    private static StringBuilder currString;

public static void main(String[] args) {
    String test1 = "))[[([{([])}";
    String test2 = "[)[((({}[]";
    System.out.println(process(test1));
}


public static String process(String s) {
    currString = new StringBuilder(s);
    ArrayStack stack = new ArrayStack(s.length());
    int count = 0;
    for (int i = 0; i < s.length(); i++) {

        if      (s.charAt(i) == L_PAREN){
            stack.push(L_PAREN);
            count++;
        }
        else if (s.charAt(i) == L_BRACE)  {
            stack.push(L_BRACE);
            count++;
        }
        else if (s.charAt(i) == L_BRACKET) {
            stack.push(L_BRACKET);
            count ++;
        }
        else if (s.charAt(i) == R_PAREN) {
            if (stack.isEmpty())
                i = completeStart();
            else if (stack.pop() != L_PAREN)
                    return "rejected";
                else count--;
        }

        else if (s.charAt(i) == R_BRACE) {
            if (stack.isEmpty())
                i = completeStart();
            else if (stack.pop() != L_BRACE)
                return "rejected";
                else count--;
        }

        else if (s.charAt(i) == R_BRACKET) {
            if (stack.isEmpty())
                i = completeStart();
            else if (stack.pop() != L_BRACKET)
                return "rejected";
                else count--;
        }
    }
    if (!stack.isEmpty()) {
        completeEnd(stack, count);
    }
    return currString.toString();
}

private static void completeEnd(ArrayStack stack, int count) {
    for (int i = 0; i < count; i++) {
        Character ch = stack.pop();
        switch (ch) {
            case L_PAREN:
                currString.append(R_PAREN);
                break;
            case L_BRACE:
                currString.append(R_BRACE);
                break;
            case L_BRACKET:
                currString.append(R_BRACKET);
                break;
        }
    }
}

private static int completeStart() {
    int count = -1;
    for (int i = 0; i < currString.length(); i++) {
        char c = currString.charAt(i);
        if (c == L_BRACE || c == L_BRACKET || c == L_PAREN) {
            break;
        }
        switch (c) {
            case R_BRACE:
                currString.insert(0, L_BRACE);
                i++;
                count++;
                break;
            case R_BRACKET:
                currString.insert(0, L_BRACKET);
                i++;
                count++;
                break;
            case R_PAREN:
                currString.insert(0, L_PAREN);
                i++;
                count++;
                break;
        }
    }
    return count;
}

class ArrayStack {

    private int top;
    private char[] storage;

    ArrayStack(int capacity) {
        storage = new char[capacity];
        top = -1;
    }

    void push(char value) {
        top++;
        storage[top] = value;
    }

    char pop() {
        return storage[top--];
    }

    boolean isEmpty() {
        return (top == -1);
    }
}
}

All feedback welcome.

\$\endgroup\$
7
\$\begingroup\$

Don't Repeat Yourself

The repetitions in the switch statement calls for refactoring into a data-driven code. In essence, declare openers and closers as

    public static string openers = "([{";
    public static string closers = ")]}";

Now the loop in the process method shrinks to

        for (...) {
            char ch = s.charAt(i);
            int index;
            if ((index = openers.indexOf(ch)) != -1) {
                stack.push(ch);
                count++;
            } else {
                index = closers.indexOf(ch);
                assert(index != -1);
                if (stack.isEmpty()) {
                    i = completeStart()
                } else {
                    opener = stack.pop();
                    if (openers.indexOf(opener) != index)
                        return "rejected"
                    count--;
                }
            }
        }

and completeStart should follow the suit.

On a side note, I am not sure I like completeStart looping over the source string. I recommend refactor it to complete just one opener at a time.

\$\endgroup\$
1
  • \$\begingroup\$ My first impresion about your comment was "This give me NOTHING!", but after re-read couple times I star to undestent, and come with new version base on your comment, number of lines redused by half and speed improofed as vell. Thanks, you open my eyes) \$\endgroup\$ Dec 19 '15 at 14:50
7
\$\begingroup\$

Extract common code in each conditional branch

In the block:

    switch (c) {
        case R_BRACE:
            currString.insert(0, L_BRACE);
            i++;
            count++;
            break;
        case R_BRACKET:
            currString.insert(0, L_BRACKET);
            i++;
            count++;
            break;
        case R_PAREN:
            currString.insert(0, L_PAREN);
            i++;
            count++;
            break;
    }

You always execute:

        i++;
        count++;

So you can simplify and write just:

    switch (c) {
        case R_BRACE:
            currString.insert(0, L_BRACE);
            break;
        case R_BRACKET:
            currString.insert(0, L_BRACKET);
            break;
        case R_PAREN:
            currString.insert(0, L_PAREN);
            break;
    }
    i++;
    count++;
\$\endgroup\$
2
\$\begingroup\$

Your ArrayStack class:

class ArrayStack {

    private int top;
    private char[] storage;

    ArrayStack(int capacity) {
        storage = new char[capacity];
        top = -1;
    }

    void push(char value) {
        top++;
        storage[top] = value;
    }

    char pop() {
        return storage[top--];
    }

    boolean isEmpty() {
        return (top == -1);
    }
}

Is fairly well written. Some points:

  1. Make it generic so it can be used for later.
  2. Make is public so it can be used for later.
  3. Your pop() method will throw a ArrayIndexOutOfBoundsException if the Stack is empty. If you intended this, well, okay, but I would just return null.
  4. Since you are only getting the top of the stack (as that's what stacks are supposed to be), you should implement a stack that can change its size, while still having similar efficiency. How would you do this? Well:

    • Like a LinkedList, you can have Nodes pointing to the one below:

      class Node {
      
          private Node below;
          private T value;
      
          Node(Node below, T value) {
              this.below = below;
              this.value = value;
          }
      
      }
      
    • The class will hold the top Node:

      public class Stack<T> {
      
          private Node top;
      
          // ...
      
      }
      
    • Write the constructor:

      public Stack() {
          this.top = null;
      }
      
    • Then implement the methods:

      public void push(T value) {
          this.top = new Node(this.top, value);
      }
      
      public T pop() {
          if (top == null) {
              return null;
          }
          T result = top.value;
          top = top.below;
          return result;
      }
      
      public boolean isEmpty() {
          return top == null;
      }
      
    • Now put it together:

      public class Stack<T> {
      
          private Node top;
      
          public Stack() {
              this.top = null;
          }
      
          public void push(T value) {
              this.top = new Node(this.top, value);
          }
      
          public T pop() {
              if (top == null) {
                  return null;
              }
              T result = top.value;
              top = top.below;
              return result;
          }
      
          public boolean isEmpty() {
              return top == null;
          }
      
          class Node {
      
              private Node below;
              private T value;
      
              Node(Node below, T value) {
                  this.below = below;
                  this.value = value;
              }
      
          }
      
      }
      
\$\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.