How to check if a String is balanced?

Question

I want to test if an input String is balanced. It would be balanced if there is a matching opening and closing parenthesis, bracket or brace.

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

I'm having problems choosing what to do. Should I put every opening or closing parenthesis, bracket, or brace in a stack then pop them out? If I pop them out, how does that really help me?

Answer 1

Following is a Java code sample to detect if a string is balanced.

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

The idea is that -

• For each opening brace ( [ {, push it on the stack.
• For closing brace ) ] }, try to pop a matching opening brace ( [ } from stack. If you can't find a matching opening brace, then string is not balanced.
• If after processing the complete string, stack is empty then string is balanced. Otherwise string is not balanced.

Answer 2

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<Character> st=new Stack<Character>();  
        for (int i=0;i<s.length();++i)
        {
            if((s.charAt(i)=='(')||(s.charAt(i)=='{')||(s.charAt(i)=='['))
            {
                st.push(s.charAt(i));
            }
            else if(st.isEmpty()==false)
            {   
            switch(s.charAt(i))
            {
            case']':
                if(st.pop()!='[')
                {
                    System.out.println("unbalanced");
                    System.exit(0);
                }
                break;
            case'}':
                if(st.pop()!='{')
                {
                    System.out.println("unbalanced");
                    System.exit(0);
                }
                break;
            case')':
                if(st.pop()!='(')
                {
                    System.out.println("unbalanced");
                    System.exit(0);
                }
                break;
            }
            }
        }           
        if(st.isEmpty())
        {
            System.out.println("balanced paranthesis");
        }
        else 
            System.out.println("not balance");
    }   
}

Answer 3

Yes, a stack is a suitable choice for the task, or you could use a recursive function. If you use a stack, then the idea is you push each opening bracket on the stack, when you encounter a closing bracket you check that the top of the stack matches it. If it matches, pop it off, if not that is an error. When complete, the stack should be empty.

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

Answer 4

Well, roughly speaking, if it is balanced, that means your stack should be empty.

For that, you need to pop your stack when you parse a }

Additional requirement is to check that } is preceded by { or the character popped is a {.

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

Any feedback on this is most welcome. Please criticize if you find something is wrong or useless. I am just trying to learn.

Answer 6

1) For every opening bracket: { [ ( push it to the stack.

2) For every closing bracket: } ] ) pop from the stack and check whether the type of bracket matches. If not return false;

i.e. current symbol in String is } and if poped from stack is anything else from { then return false immediately.

3) If end of line and stack is not empty, return false, otherwise true.