CODEWITHSUNDEEP
javaregexstring
Manushi
Manushi

Reputation: 759

How to construct regular expression to balance characters in a string?

I have come across regular expressions for different problems but I could not find out regex s to balance characters in a string.

I came across a problem, to find if a string is balanced. ex: aabbccdd is a balanced one, as a characters are repeated in even numbers but aabbccddd is not a balanced one since ddd is repeated in odd number mode. This is applicable for all characters give an input not to specific a,b,c and d. If i give input as 12344321 or 123454321, it should return balanced and unbalanced result respectively.

How to find the balance using regex. What type of regular expression we should use to find if the string is balanced?

Edit:

I tried to find solution using regex only as the problem demands answer in regex pattern. I would implemented using any other solution if regex was not mentioned explicitly

Upvotes: 0

Views: 1167

Answers (2)

xenteros
xenteros

Reputation: 15842

Regular expression for this problem exists, but doesn't speed up anythings and will be totally messy. It's easier to prepare NFA, and then switch to REGEX. Still, it's not proper tool.

public static void main(String args[]) {
    String s = args[0];
    int[] counter = new int[256];
    for (int i = 0; i < s.length(); i++) {
        counter[s.charAt(i)]++;
    }
    if (validate(counter)) {
        System.out.println("valid");
    } else {
        System.out.println("invalid");
    }
}

public static boolean validate(int[] tab) {
    for (int i : tab) {
        if (i%2 == 1) {
            return false;
        }
    }
    return true;
}

Edit: for pointing the regex existance

Reference for a finite automate for just two characters. Start on the very left, win with double circle. Each state named by the set of characters that have odd count so far.

enter image description here

Upvotes: 1

RaffoSorr
RaffoSorr

Reputation: 404

I don't think you can do it with regex. Why do you need to use them? I tried this: it works and it's pretty simple

static boolean isBalanced(String str) {
    ArrayList<Character> odds = new ArrayList<>(); //Will contain the characters read until now an odd number of times
    for (char x : str.toCharArray()) { //Reads each char of the string
        if (odds.contains(x)) { //If x was in the arraylist we found x an even number of times so let's remove it
            odds.remove(odds.indexOf(x));
        }
        else {
            odds.add(x);
        }
    }
    return odds.isEmpty();
}

Upvotes: 1

Related Questions