patternjavaMinor
Braces and Brackets Autocomplete
Viewed 0 times
andbracesautocompletebrackets
Problem
I need to complete a sequence of braces and brackets like
Example:
My implementation is based on using a stack (self-implemented to improve from standard
```
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) {
[ ], ( ), { }, 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:
You always execute:
So you can simplify and write just:
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.