Created
September 17, 2015 06:21
-
-
Save rampatra/4fe4f7e88db82fe9ad4d to your computer and use it in GitHub Desktop.
Well-formed Parenthesis
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
import java.io.BufferedReader; | |
import java.io.FileReader; | |
import java.io.IOException; | |
import java.util.EmptyStackException; | |
/** | |
* Created by IntelliJ IDEA. | |
* | |
* @author: ramswaroop | |
* @date: 9/15/15 | |
* @time: 11:15 PM | |
*/ | |
public class Parenthesis { | |
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 = ']'; | |
/** | |
* Checks if the parenthesis are well-formed in string {@param input}. | |
* <p/> | |
* For example, | |
* {[()]} : true | |
* {[]()[]} : true | |
* {[)} : false | |
* {(} : false | |
* | |
* @param input | |
* @return {@code true} if parenthesis are well-formed, {@code false} otherwise. | |
*/ | |
public static boolean isWellFormed(String input) { | |
int len = input.length(); | |
Stack<Character> stack = new Stack<>(); | |
// base case | |
if (len % 2 != 0) return false; | |
for (int i = 0; i < len; i++) { | |
char charAtI = input.charAt(i); | |
if (charAtI == L_PAREN || charAtI == L_BRACE || charAtI == L_BRACKET) { | |
stack.push(charAtI); | |
} else if (charAtI == R_PAREN) { | |
if (stack.isEmpty() || stack.pop() != L_PAREN) return false; | |
} else if (charAtI == R_BRACE) { | |
if (stack.isEmpty() || stack.pop() != L_BRACE) return false; | |
} else if (charAtI == R_BRACKET) { | |
if (stack.isEmpty() || stack.pop() != L_BRACKET) return false; | |
} | |
} | |
return stack.isEmpty(); | |
} | |
/** | |
* Reads the file specified in {@param filePath} line by line | |
* and checks if parenthesis are well-formed or not. | |
* | |
* @param filePath | |
*/ | |
public static void readFile(String filePath) { | |
try (BufferedReader br = new BufferedReader(new FileReader(filePath))) { | |
String line; | |
while ((line = br.readLine()) != null) { | |
System.out.println(isWellFormed(line) ? "True" : "False"); | |
} | |
} catch (IOException e) { | |
e.printStackTrace(); | |
} | |
} | |
/** | |
* Starting point of the program. | |
* | |
* @param a | |
*/ | |
public static void main(String a[]) { | |
readFile(a[0]); | |
System.exit(0); | |
} | |
} | |
/** | |
* Stack implementation using | |
* a singly linked list. | |
* | |
* @param <E> | |
*/ | |
class Stack<E> { | |
private Node<E> top; | |
public Stack() { | |
top = null; | |
} | |
/** | |
* Pushes an item onto the top of this stack. | |
* | |
* @param item | |
*/ | |
public E push(E item) { | |
top = new Node<>(item, top); | |
return item; | |
} | |
/** | |
* Removes the object at the top of this stack and | |
* returns it. | |
* | |
* @return | |
*/ | |
public E pop() { | |
E item = peek(); | |
top = top.next; | |
return item; | |
} | |
/** | |
* Looks at the object at the top of this stack without removing it from the stack. | |
* | |
* @return | |
*/ | |
public E peek() { | |
if (top == null) { | |
throw new EmptyStackException(); | |
} | |
return top.item; | |
} | |
/** | |
* Tests if this stack is empty. | |
* | |
* @return | |
*/ | |
public boolean isEmpty() { | |
return top == null; | |
} | |
/** | |
* Generic node for holding values of any object type. | |
* | |
* @param <E> | |
*/ | |
private class Node<E> { | |
E item; | |
Node<E> next; | |
Node(E item, Node<E> next) { | |
this.item = item; | |
this.next = next; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment