Java solution to Codility Brackets problem (Lesson 7 – Stacks and Queues) which scored 100%. The problem is to determine whether a given string of multiple types of parentheses is properly nested.
The strategy is to store opening brackets on a stack and pop elements off stack when encounter closing bracket and check that it’s a proper open bracket-close bracket match.
Special Cases
- odd number of characters – can’t be nested
- encountering closing bracket when stack is empty – can’t be nested
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import java.util.Stack;
public class Brackets {
public int solution(String S) {
if(S.length() % 2 != 0) return 0; //all odd numbered strings can't be properly nested
Stack charStack = new Stack();
for(int i=0; i<S.length(); i++) {
char currentChar = S.charAt(i);
if(isOpeningBracket(currentChar)) {
charStack.push(currentChar);
}
else {
//adding closing bracket to empty stack will never become properly nested
if(charStack.size() == 0) {
return 0;
}
char poppedChar = charStack.pop();
if(isBracketMatch(poppedChar, currentChar)) {
continue;
}
else return 0;
}
}
if(charStack.isEmpty()) return 1;
return 0;
}
boolean isOpeningBracket(char pC) {
if(pC == '[' || pC == '(' || pC == '{') {
return true;
}
return false;
}
boolean isBracketMatch(char pC1, char pC2) {
if(pC1 == '[' && pC2 == ']') return true;
if(pC1 == '(' && pC2 == ')') return true;
if(pC1 == '{' && pC2 == '}') return true;
return false;
}
}
TestNG test cases for this problem which all passed:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import org.testng.Assert;
import org.testng.annotations.BeforeTest;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;
import com.codility.lesson07.stacksqueues.Brackets;
public class BracketsTests {
private Brackets solution;
@BeforeTest
public void setUp() {
solution = new Brackets();
}
@DataProvider(name = "test1")
public Object [][] createData1() {
return new Object [][] {
new Object [] { "{[()()]}", 1 },
new Object [] { "{[(){([])}()]}", 1 },
new Object [] { "{}", 1 },
new Object [] { "()", 1 },
new Object [] { "[]", 1 },
new Object [] { "[([][])()]", 1 },
new Object [] { "([)()]", 0 },
new Object [] { "(]", 0 },
new Object [] { "", 1 },
new Object [] { "{{{{", 0 },
new Object [] { "))", 0 },
};
}
@Test(dataProvider = "test1")
public void verifySolution(String pS, int pExpected) {
Assert.assertEquals(solution.solution(pS), pExpected);
}
}