import java.util.Stack;
public class SyntaxChecker {
/**
* This enum represents all types of open brackets. If we have a new type then
* just add it to this list with the corresponding closed bracket in the other
* ClosedBracketTypes enum
* @author AnishBivalkar
*
*/
private enum OpenBracketTypes {
LEFT_ROUND_BRACKET('('),
LEFT_SQUARE_BRACKET('['),
LEFT_CURLY_BRACKET('{');
char ch;
// Constructs the given bracket type
OpenBracketTypes(char ch) {
this.ch = ch;
}
// Getter for the type of bracket
public final char getBracket() {
return ch;
}
/**
* This method checks if the current character is of type OpenBrackets
* @param name
* @return True if the current character is of type OpenBrackets, false otherwise
*/
public static boolean contains(final char name) {
for (OpenBracketTypes type : OpenBracketTypes.values()) {
if (type.getBracket() == name) {
return true;
}
}
return false;
}
}
/**
* This enum represents all types of Closed brackets. If we have a new type then
* just add it to this list with the corresponding open bracket in the other
* OpenBracketTypes enum
* @author AnishBivalkar
*
*/
private enum CloseBracketTypes {
RIGHT_ROUND_BRACKET(')'),
RIGHT_SQUARE_BRACKET(']'),
RIGHT_CURLY_BRACKET('}');
char ch;
CloseBracketTypes(char ch) {
this.ch = ch;
}
private char getBracket() {
return ch;
}
/**
* This method checks if a given bracket type is a closing bracket and if it correctly
* completes the opening bracket
* @param bracket
* @param brackets
* @return
*/
public static boolean isBracketMatching(char bracket, Stack<Character> brackets) {
// If the current stack is empty and we encountered a closing bracket then this is
// an incorrect syntax
if (brackets.isEmpty()) {
return false;
} else {
if (bracket == CloseBracketTypes.RIGHT_ROUND_BRACKET.getBracket()) {
if (brackets.peek() == OpenBracketTypes.LEFT_ROUND_BRACKET.getBracket()) {
return true;
}
} else if (bracket == CloseBracketTypes.RIGHT_SQUARE_BRACKET.ch) {
if (brackets.peek() == OpenBracketTypes.LEFT_SQUARE_BRACKET.getBracket()) {
return true;
}
} else if (bracket == CloseBracketTypes.RIGHT_CURLY_BRACKET.ch) {
if (brackets.peek() == OpenBracketTypes.LEFT_CURLY_BRACKET.getBracket()) {
return true;
}
}
return false;
}
}
/**
* This method checks if the current character is of type ClosedBrackets
* @param name
* @return true if the current character is of type ClosedBrackets, false otherwise
*/
public static boolean contains(final char name) {
for (CloseBracketTypes type : CloseBracketTypes.values()) {
if (type.getBracket() == name) {
return true;
}
}
return false;
}
}
/**
* This method check the syntax for brackets. There should always exist a
* corresponding closing bracket for a open bracket of same type.
*
* It runs in O(N) time with O(N) worst case space complexity for the stack
* @param sentence The string whose syntax is to be checked
* @return True if the syntax of the given string is correct, false otherwise
*/
public static boolean matchBrackets(String sentence) {
boolean bracketsMatched = true;
// Check if sentence is null
if (sentence == null) {
throw new IllegalArgumentException("Input cannot be null");
}
// Empty string has correct syntax
if (sentence.isEmpty()) {
return bracketsMatched;
} else {
Stack<Character> brackets = new Stack<Character>();
char[] letters = sentence.toCharArray();
for (char letter : letters) {
// If the letter is a type of open bracket then push it
// in stack else if the letter is a type of closing bracket
// then pop it from the stack
if (OpenBracketTypes.contains(letter)) {
brackets.push(letter);
} else if (CloseBracketTypes.contains(letter)) {
if (!CloseBracketTypes.isBracketMatching(letter, brackets)) {
return false;
} else {
brackets.pop();
}
}
}
// If the stack is not empty then the syntax is incorrect
if (!brackets.isEmpty()) {
bracketsMatched = false;
}
}
return bracketsMatched;
}
/**
* @param args
*/
public static void main(String[] args) {
String words = "[[][][]Anfield[[]([])[]]becons()]";
boolean isSyntaxCorrect = SyntaxChecker.matchBrackets(words);
if (isSyntaxCorrect) {
System.out.println("The syntax is correct");
} else {
System.out.println("Incorrect syntax");
}
}
}
これに関するフィードバックは大歓迎です。あなたが何かが間違っているか役に立たないことを見つけたら批判してください。私はただ勉強しようとしています。
これは宿題の問題ですか？ –