有 Java 编程相关的问题?

你可以在下面搜索框中键入要查询的问题!

java如何检查字符串是否平衡?

我想测试输入字符串是否平衡。如果有一个匹配的开始和结束括号、括号或大括号,它将是平衡的

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;
}

我在选择做什么时遇到了问题。我是否应该将每个开始或结束的括号、括号或大括号放在一个堆栈中,然后将它们弹出?如果我把它们拿出来,那对我有什么帮助


共 (6) 个答案

  1. # 1 楼答案

    1)对于每个打开的括号:{ [ (将其推到堆栈中

    2)对于每个结束括号:} ] )从堆栈中弹出并检查括号的类型是否匹配。如果不返回false

    字符串中的当前符号是},如果从堆栈中弹出的是{中的任何其他符号,则立即返回false

    3)如果行尾和堆栈不是空的,则返回false,否则返回true

  2. # 2 楼答案

    下面是一个Java代码示例,用于检测字符串是否平衡

    http://introcs.cs.princeton.edu/java/43stack/Parentheses.java.html

    我们的想法是——

    • 对于每个打开的大括号( [ {,将其推到堆栈上
    • 对于右大括号) ] },请尝试从堆栈中弹出匹配的左大括号( [ }。若你们找不到匹配的大括号,那个么字符串是不平衡的
    • 如果处理完完整的字符串后,堆栈为空,则字符串处于平衡状态。否则字符串不平衡
  3. # 3 楼答案

    是的,堆栈是任务的合适选择,也可以使用递归函数。如果你使用一个堆栈,那么你的想法是推堆栈上的每个打开的括号,当你遇到一个关闭的括号时,你检查堆栈的顶部是否匹配它。如果匹配,则将其弹出,如果不匹配,则为错误。完成后,堆栈应为空

    import java.util.Stack;
    public class Balanced {
        public static boolean isBalanced(String in)
        {
            Stack<Character> st = new Stack<Character>();
    
            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");
            }
        }
    }
    
  4. # 4 楼答案

    粗略地说,如果它是平衡的,这意味着你的堆栈应该是空的

    为此,在解析}时需要弹出堆栈

    额外的要求是检查}前面是否有{或者弹出的字符是否是{

  5. # 5 楼答案

    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");
            }
        }
    }
    

    对此的任何反馈都是非常欢迎的。如果你发现有什么错误或无用的东西,请批评。我只是在努力学习

  6. # 6 楼答案

    我编写这段代码是为了解决这个问题,在每个括号类型中只使用一个整数(或者可能是一个字节)变量

    public boolean checkWithIntegers(String input) {
    
        int brackets = 0;
    
        for (char c: input.toCharArray()) {
    
            switch (c) {
    
                case '(':
    
                    brackets++;
    
                    break;
    
                case ')':
    
                    if (brackets == 0)
                        return false;
    
                    brackets--;
    
                    break;
    
                default:
    
                    break;
            }
        }
    
    
        return brackets == 0;
    }
    
    public static void main(String... args) {
    
        Borrar b = new Borrar();
        System.out.println( b.checkWithIntegers("") );
        System.out.println( b.checkWithIntegers("(") );
        System.out.println( b.checkWithIntegers(")") );
        System.out.println( b.checkWithIntegers(")(") );
        System.out.println( b.checkWithIntegers("()") );
    
    }
    

    OBS

    1. 我假设一个空字符串是平衡的。这可以通过之前的检查来改变
    2. 我只使用了一种类型的括号示例,但只需添加另一个case开关即可快速添加其他类型

    希望这有帮助。 干杯