How to determine the order of letters by regex? [closed]

Question

I want to write a regular expression to determine whether a given string is uppercase and sorted in non-descending order.

^A*B*C*D*E*F*G*H*I*J*K*L*M*N*O*P*Q*R*S*T*U*V*Q*X*Y*Z*$

I was just wondering if it is possible to improve the above regex.

Examples of correct strings:

AEHII
EFKLZ

Examples of wrong strings:

AbCDE
YABKL

Answer 1

There is no shorter solution. Because you are enforcing order, you must list every single entity in desired order. And because you are allowing zero to many instances of each entity, you must provide the * operator. And because you want to match the entire string, you must provide the anchors on both ends.

Could you write one that runs faster? Possibly. But shorter? I don't see how.

Answer 2

No.

There is no way to express

(xy)* | ∀(x, y) => x <= y ∧ (x, y) ∈ {A..Z}

with regular expressions in such an abstract way, at least not in popular regex usage I'm aware of. So you have to enumerate all characters explicitly.

Answer 3

As already pointed out by @userunknown, there is no way to simplify your regular expression from a purist point of view.

However, if you're using Perl, here's one way to do it that doesn't involve explicitly writing out all the letters A to Z.

my $uppersorted = "^" . join("", map {"$_*"} ('A'..'Z')) . "\$";

Making that into a compiled regex:

$uppersorted = qr/$uppersorted/;

Testing it with the given input cases:

my @tests = ("AEHII", "EFKLZ", "AbCDE", "YABKL");

foreach my $test (@tests) {
    printf "%s: %s\n",
        $test,
        $test =~ $uppersorted? "YES" : "NO";
}