如何检查String是否平衡？
我想测试输入字符串是否平衡。 如果有匹配的开括号，括号或括号，它将是平衡的。
example: {} balanced () balanced [] balanced If S is balanced so is (S) If S and T are balanced so is ST public static boolean isBalanced(String in) { Stack st = new Stack(); for(char chr : in.toCharArray()) { if(chr == '{') st.push(chr); } return false; } 我在选择做什么时遇到了问题。 我应该将每个开口或右括号，括号或括号放入堆叠中然后将它们弹出？ 如果我把它们弹出来，这对我有什么帮助？
1）对于每个开口括号： { [ (将其推入堆栈。
2）对于每个结束括号： } ] )从堆栈弹出并检查括号的类型是否匹配。 如果没有返回false ;
即 String中的当前符号是}并且如果从堆栈中取出来的是其他任何来自{则立即返回false 。
3）如果行尾和堆栈不为空，则返回false ，否则为true 。
是的，堆栈是任务的合适选择，或者您可以使用递归函数。 如果您使用堆栈，那么您的想法是将每个开口括号推到堆栈上，当您遇到一个右括号时，您会检查堆栈的顶部是否与它匹配。 如果匹配，则将其弹出，如果不匹配则为错误。 完成后，堆栈应为空。
import java.util.Stack; public class Balanced { public static boolean isBalanced(String in) { Stack st = new Stack (); for(char chr : in.toCharArray()) { switch(chr) { case '{': case '(': case '[': st.push(chr); break; case ']': if(st.isEmpty() || st.pop() != '[') return false; break; case ')': if(st.isEmpty() || st.pop() != '(') return false; break; case '}': if(st.isEmpty() || st.pop() != '{') return false; break; } } return st.isEmpty(); } public static void main(String args[]) { if(args.length != 0) { if(isBalanced(args[0])) System.out.println(args[0] + " is balanced"); else System.out.println(args[0] + " is not balanced"); } } }
好吧，粗略地说，如果它是平衡的，那意味着你的堆栈应该是空的。
为此，你需要在解析时弹出堆栈}
附加要求是检查}前面是{或弹出的字符是{ 。
以下是检测字符串是否平衡的Java代码示例。
http://introcs.cs.princeton.edu/java/43stack/Parentheses.java.html
这个想法是 –
- 对于每个左大括号
( [ {，将其推入堆栈。 - 对于关闭大括号
) ] }，尝试从堆栈中弹出匹配的左大括号( [ }。如果找不到匹配的左大括号，则字符串不平衡。 - 如果在处理完整的字符串后，堆栈为空，则字符串是平衡的。 否则字符串不平衡。
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 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 brackets = new Stack (); 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"); } } }
对此的任何反馈都是最受欢迎的。 如果你发现错误或无用，请批评。 我只是想学习。
import java.util.*; public class Parenthesis { public static void main (String ...argd) { Scanner sc=new Scanner(System.in); System.out.println("enetr string"); String s=sc.nextLine(); Stack st=new Stack (); for (int i=0;i