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

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.

Answer 2

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 3

I wrote this code to solve this problem using only an integer (or maybe a byte) variable per bracket type.

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. I'm assuming that an empty string is balanced. That can be changed with just a previous check.
2. I'm using only one type of bracket example, but other types can be added quickly just adding another case switch.

Hope this help. Cheers!

Answer 4

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 5

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 {.