Как проверить, сбалансирована ли строка?

1) Для каждой открывающей скобки: { [ ( поместите ее в стек.

2) Для каждой закрывающей скобки: } ] ) извлеките из стека и проверьте, совпадает ли тип скобки. Если не вернуть false;

т. е. текущий символ в строке — }, и если из стека выталкивается что-либо еще из {, то немедленно возвращайте false.

3) Если конец строки и стек не пуст, вернуть false, иначе true.

Да, стек подходит для этой задачи, или вы можете использовать рекурсивную функцию. Если вы используете стек, то идея состоит в том, что вы помещаете каждую открывающую скобку в стек, когда вы встречаете закрывающую скобку, вы проверяете, соответствует ли ей вершина стека. Если он совпадает, вытащите его, если нет, это ошибка. По завершении стек должен быть пуст.

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

Ниже приведен пример кода Java для определения сбалансированности строки.

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

Идея в том, что -

• Для каждой открывающей скобки ( [ { поместите ее в стек.
• Для закрывающей скобки ) ] } попробуйте извлечь из стека соответствующую открывающую скобку ( [ }. Если вы не можете найти подходящую открывающую скобку, строка не сбалансирована.
• Если после обработки всей строки стек пуст, то строка сбалансирована. В противном случае строка не сбалансирована.

Ну, грубо говоря, если он сбалансирован, значит, ваш стек должен быть пуст.

Для этого вам нужно вытолкнуть свой стек при разборе }

Дополнительным требованием является проверка того, что } предшествует { или выталкиваемый символ является {.

Я написал этот код, чтобы решить эту проблему, используя только целочисленную (или, возможно, байтовую) переменную для каждого типа скобки.

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

}

ОБС

1. Я предполагаю, что пустая строка сбалансирована. Это можно изменить с помощью только предыдущей проверки.
2. Я использую в качестве примера только один тип скобок, но другие типы можно быстро добавить, просто добавив еще один переключатель регистра.

Надеюсь, это поможет. Ваше здоровье!

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

Любые отзывы по этому поводу приветствуются. Пожалуйста, критикуйте, если вы считаете что-то неправильным или бесполезным. Я просто пытаюсь учиться.

соответствующая ссылка Hackrrank: https://www.hackerrank.com/challenges/balanced-brackets/problem

import java.util.Stack;

class BalancedParenthesis {
    static String isBalanced(String s) {
        return isBalanced(s.toCharArray());
    }

    private static String isBalanced(final char[] chars) {
        final Stack<Character> stack = new Stack<>();
        for (char eachChar : chars) {
            if (eachChar == '{' || eachChar == '[' || eachChar == '(') {
                stack.push(eachChar);
            } else {
                if (stack.isEmpty()) {
                    return "NO";
                }
                if (correspondingCloseBracket(stack.peek()) != eachChar) {
                    return "NO";
                }
                stack.pop();
            }
        }
        return stack.isEmpty() ? "YES" : "NO";
    }

    private static char correspondingCloseBracket(final char eachChar) {
        if (eachChar == '{') {
            return '}';
        }
        if (eachChar == '[') {
            return ']';
        }
        return ')';
    }
}