Check if a String is a Balanced String

Krrishnaaaa

A balanced String is a String with equal number of opening and closing matched brackets. In other words, an expression consisting of matching opening and closing brackets are called balanced strings. For instance, “adf(aew)23[34v3a*23]ade(we{wefave}qwef)ad[e[qew]]” is a balanced string, because after removing all the characters it is left with “()[]({})[[]]”.

How to check the expression

To check if an expression contains balanced brackets we can use Stack. A stack has push() for insertion and pop() for deletion. We can use this to check if a closing bracket is matched with the last element of the stack (top of the stack).


(adsbygoogle = window.adsbygoogle || []).push({});

Steps to check the expression:
1. Create a Character Stack and push the character if it matches ‘(‘ or ‘[‘ or ‘{‘.
2. If the character of the expression contains either of ‘)’ or ‘]’ or ‘}’ then pop the character of the stack
3. Compare the recent character from the expression with the popped character from stack. If both matches then continue iterating the expression, else return from iteration.

Implementation to check if a String is Balanced String

Following JAVA code is for checking if a String is Balanced String. This code sample could be found on GitHub.

import java.util.Stack;

public class BalancedString {

    public static void main(String[] args) {
        String testString = "adf(aew)23[34v3a*23]ade(we{wefave}qwef)ad[e[qew]][";
        if(args.length > 0) {
            testString = args[0];
        }

        Stack<Character> stringStack = new Stack<>();
        char[] chars = testString.toCharArray();

        for (int i = 0; i < chars.length; i++) {
            switch (chars[i]) {
                case '(':
                case '[':
                case '{':
                    stringStack.push(chars[i]);
                    break;
                case ')':
                    if (isMatchingClose(stringStack, '(')) {
                        System.out.println("Not balanced: no matching (");
                        return;
                    }
                    break;
                case ']':
                    if (isMatchingClose(stringStack, '[')) {
                        System.out.println("Not balanced: no matching [");
                        return;
                    }
                    break;
                case '}':
                    if (isMatchingClose(stringStack, '{')) {
                        System.out.println("Not balanced: no matching {");
                        return;
                    }
                    break;
            }
        }
        if (stringStack.isEmpty()) {
            System.out.println(testString + " is balanced String.");
        } else {
            System.out.println(testString + " is NOT balanced String.");
        }
    }

    private static boolean isMatchingClose(Stack<Character> stringStack, char openingBracket) {
        return stringStack.isEmpty() || !stringStack.pop().equals(openingBracket);
    }
}

Related