Brackets – Codility – Solution

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

[cc lang="java" escaped="true"]
package com.codility.lesson07.stacksqueues;

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;
	}
}
[/cc]

TestNG test cases for this problem which all passed:

[cc lang="java" escaped="true"]
package test.com.codility.lesson07.stacksqueues;

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);
	}	
}
[/cc]