Cheap and Secure Web Hosting Provider : See Now

[Solved]: Why does a regular expression only accept all my required strings when the concatenation is the first of the OR operations?

, , No Comments
Problem Detail: 

I am having a bit of difficulty understanding the order of precedence in boolean logic for the OR operation. Take this example:

Assume the following regular expression:

((a(b+))+(a|c))|a|c 

Why is it that this accepts the strings:

a c abba abbabbba abbabbc 

etc

But when I flip it around and use the regular expression

a|c|((a(b+))+(a|c)) 

I can now only ever get the following strings when I check it with a RegExp tester:

a c 

I know it is to do with the order of precedence but I don't understand why, please could somebody enlighten me?

Asked By : Jake

Answered By : Untitled

Both the patterns match your given strings and are equivalent. The problem here is that your tester does not try to match the string against the pattern, but tries to find matching substrings, and it does that by trying each of the ORed patterns in order. Hence the second pattern stops when $a$ is matched, but the first one matches the whole string.

To see the difference Look at the below code, written in Java:

public static void main(String[] args) {     test("((a(b+))+(a|c))|a|c", "abbabbc");     test("a|c|((a(b+))+(a|c))", "abbabbc"); }  private static void test(String pattern, String str) {     System.out.println(str.matches(pattern));     Matcher matcher = Pattern.compile(pattern).matcher(str);     while(matcher.find())         System.out.println(str.substring(matcher.start(), matcher.end())); } 

The output is

true abbabbc true a a c 

which shows that both patterns do match $abbabbc$. They are only different in eyes of a matching-substrings-finder program.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18858

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback