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

Question

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

I never liked java, but after reading all the answers and comments - I know - I'm never switching to Java. In python this problem is about 2-5 lines of code without regex and specific libraries ... still cannot believe you can't count characters in string in java ... actually here is SO answer for that: https://stackoverflow.com/questions/275944/java-how-do-i-count-the-number-of-occurrences-of-a-char-in-a-string , now only compare those counts for each char in string ... it's actually 1-liner as expected — Drako, Jun 12 '17 at 09:29
@Drako Keep in mind the OP asked for a solution based on RegExps (I actually suspect that to be an exam trick question). Regarding Java, it has undergone a few developments recently, and then there are Groovy and Kotlin, which definitely steal Java the show by adding all the syntactic sugar which Python is offering since ages. — class stacker, Jun 12 '17 at 09:33
@classstacker You might be right about this being assignment, because I get here for regex tag and find out that no regex is needed even if it would be possible to write it, in python not using lambdas that would shorten it even more, working example have 3-4 lines :) I believe with just few lines more can do the same in Java :) so really must be school question for regex torturing :) — Drako, Jun 12 '17 at 09:41
@classstacker it's perfect task for checking if the student knows how to convert from DFA or NFA to regex. For me DFA would be enough if convertion algorithm provided. — xenteros, Jun 12 '17 at 09:49
Sorry, as you can see from my other comments, I thought "balanced" were defined by either repeating the same character seceral times in a row or having a symmetrical character string. This would involve counting. — class stacker, Jun 12 '17 at 09:50
@xenteros Yes, once you provide a precise definition of "balanced" -- for me, there's really nothing "balanced" about "13253152", and why would good examples suggest a regularity which is not supposed to be chacked for... anyhow. Nice discussion. ;) — class stacker, Jun 12 '17 at 09:53

score 1 · Answer 1 · answered Jun 12 '17 at 09:17

1

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

answered Jun 12 '17 at 09:17

RaffoSorr

405
1
5
14

I tried my code with all four OP examples and it returns the right value. 12344321 returns true and 123454321 returns false. – RaffoSorr Jun 12 '17 at 09:42
Sorry, as you can see from my other comments, I thought "balanced" were defined by either repeating the same character seceral times in a row or having a symmetrical character string. – class stacker Jun 12 '17 at 09:48
I tried to find solution using regex only as the problem demands answer in regex pattern. I would used any other solution if regex was not mentioned explicitly – Manushi Jun 12 '17 at 10:22

xenteros · Answer 2 · 2017-06-12T09:46:02.697

1

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.

edited Jun 12 '17 at 09:46

answered Jun 12 '17 at 09:18

xenteros

15,586
12
56
91

@classstacker it is easier to understand for `L={0,1}`. It's well explained https://stackoverflow.com/a/19615508/4723795 – xenteros Jun 12 '17 at 09:37
@classstacker regular expressions are izomorfic to NFA, and the nfa would just read char by char and for each char it would have 2 states - even and odd. It would just switch. – xenteros Jun 12 '17 at 09:38
@classstacker please check the DFA attached to the answer. https://cs.stackexchange.com/questions/2016/how-to-convert-finite-automata-to-regular-expressions describes the convertion – xenteros Jun 12 '17 at 09:46
Sorry, as you can see from my other comments, I thought "balanced" were defined by either repeating the same character seceral times in a row or having a symmetrical character string. That would require counting. – class stacker Jun 12 '17 at 09:49
@classstacker obviously this would require inf number of states which conflicts with finite automate – xenteros Jun 12 '17 at 09:50
Yes, and it wouldn't be the fiist trick question in a textbook / exam. ;) – class stacker Jun 12 '17 at 09:54
@classstacker I remember my exam on formal languages. Being best on the year wasn't enough to solve more than 2 out of 3 tasks :D It's wonderful science. – xenteros Jun 12 '17 at 10:04
Agreed. Opening up a universe of insights, undervalued, and my major field of studies at that time. Still have the Aho / Sethi / Ullman on the shelf. – class stacker Jun 12 '17 at 10:09

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

2 Answers2