ChallengeFive.java

package com.bmchild;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

/**
 * @author bchild
 *
 */
public class ChallengeFive {
	
	private static final String VALID = "((x+y (3x-2)) * (z^2 - 1) * (x + z))";
	private static final String VALID_2 = "(a + b + (c+d) + (f+h))";
	private static final String NOT_VALID = "((x+y (3x-2)) * (z^2 - 1) * (x + z)))))))";
	private static final String COUNT_BREAKER = ")(";
	
	private static final String LEFT_PAREN = "(";
	private static final String RIGHT_PAREN = ")";
	

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(VALID + "  -> " + isBalance(VALID));
		System.out.println(VALID_2 + "  -> " + isBalance(VALID_2));
		System.out.println(NOT_VALID + " -> " + isBalance(NOT_VALID));
		System.out.println(COUNT_BREAKER + " -> " + isBalance(COUNT_BREAKER));
		
		System.out.println(VALID + "  -> " + getParenMap(VALID));
		System.out.println(VALID_2 + "  -> " + getParenMap(VALID_2));
		System.out.println(NOT_VALID + " -> " + getParenMap(NOT_VALID));
		
		/*
		 * Code results in:	
		   	((x+y (3x-2)) * (z^2 - 1) * (x + z))  -> true
			(a + b + (c+d) + (f+h))  -> true
			((x+y (3x-2)) * (z^2 - 1) * (x + z))))))) -> false
			)( -> false
			((x+y (3x-2)) * (z^2 - 1) * (x + z))  -> {16=24, 0=35, 1=12, 6=11, 28=34}
			(a + b + (c+d) + (f+h))  -> {0=22, 17=21, 9=13}
			Exception in thread "main" java.util.NoSuchElementException
		 * 
		 */

	}
	
	/**
	 * Uses an int to track balance.  Positive means too many left parens.  Negative means too many right parens.
	 * If the balance ever goes negative the method will stop and return that balance since it means it's already off balance. 
	 * @param expression
	 * @return
	 */
	private static Boolean isBalance(String expression) {
		Integer balance = 0;
		for(Character character : expression.toCharArray()) {
			if(LEFT_PAREN.equals(character.toString())) {
				balance++;
			} else if (RIGHT_PAREN.equals(character.toString())) {
				balance--;
				if(balance < 0) {
					return Boolean.FALSE;
				}
			}
		}
		return Boolean.TRUE;
	}
	
	/**
	 * Creates a map keyed of the indexes of the opening paren and the value of the closing paren. 
	 * @param expression
	 * @return
	 */
	private static Map<Integer, Integer> getParenMap(String expression) {
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		
		Deque<Integer> stack = new ArrayDeque<Integer>();
		int i = 0;
		for(Character character : expression.toCharArray()) {
			if(LEFT_PAREN.equals(character.toString())) {
				stack.push(i);
			} else if (RIGHT_PAREN.equals(character.toString())) {
				Integer leftIndex = stack.pop(); // throws NoSuchElementException if the deque is empty
				map.put(leftIndex, i);
			}
			i++;
		}
		
		return map;
	}

}