Created
June 26, 2014 19:50
-
-
Save bmchild/30f00a5fc67d97091073 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment