HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Braces and Brackets Autocomplete

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
andbracesautocompletebrackets

Problem

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) {

Solution

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++;

Code Snippets

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;
    }
i++;
        count++;
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++;

Context

StackExchange Code Review Q#114405, answer score: 7

Revisions (0)

No revisions yet.