Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

We filter and analyse seats for events. Apparently writing a domain query language for the floor people isn't an option. I'm using C# 4.0 & .NET 4.0, and have relatively free reign to use whatever open-source tools are available. </background-info>

If a request comes in for "FLOOR B", the sales people want it to show up if they've entered "FLOOR A-FLOOR F" in a filter. The only problem I have is that there's absolutely no structure to the parsed parameters. I get the string already concatenated (it actually uses a tilde instead of dash). Examples I've seen so far with matches after each:

  • 101WC-199WC (needs to match 150WC)
  • AAA-ZZZ (needs to match AAA, BBB, ABC but not BB)
  • LOGE15-LOGE20 (needs to match LOGE15 but not LOGE150)

At first I wanted to try just stripping off the numeric part of the lower and upper, and then incrementing through that. The problem I have is that only some entries have numbers, sometimes the numbers AND letters increment, sometimes its all letters that increment. Since I can't impose any kind of grammar to use (I really wanted [..] expansion syntax), I'm stuck using these entries.

Are there any suggestions for how to approach this parsing problem?

share|improve this question
1  
Can you at least make the assumption that the starting and ending portions of the filter have the same distribution of letters/numbers? For example, would you only ever get LOGE015-LOGE120, never LOGE15-LOGE120? –  sugaredlightning Dec 4 '12 at 22:43
    
@sugaredlightning: can't guarantee that. They might want 1-100 –  insta Dec 4 '12 at 23:03
    
Would one see 'A-9' or '0-F' as a valid range? Is the variable part staying within the same character class? –  MichaelT Dec 4 '12 at 23:16
    
@MichaelT: the variable part stays within the same character class, but both pieces might vary independently. It's not uncommon to see 100A-300L, or 100AA-200ZZ –  insta Dec 4 '12 at 23:19
add comment

2 Answers

up vote 1 down vote accepted

The only pattern I can see is that you have either letters followed by digits, or digits followed by letters, or letters only.

From this point, the first step would be to separate the string into the beginning and the end, then to separate each part into a group of one or two entities:

"AB12-ZZ789" → ["AB12", "ZZ789"] → [["AB", "12"], ["ZZ", "789"]]

The numeric entities can be then converted to numbers:

[["AB", "12"], ["ZZ", "789"]] → [["AB", 12], ["ZZ", 789]]

Then, letters can be converted to their respective numeric representation. For example, if "A" is mapped to 0, "B" - to 1, etc., "AB" is 0 × 26 + 1, while "ZZ" is 25 × 26 + 25.

[["AB", 12], ["ZZ", 789]] → [[26, 12], [675, 789]]

Once you do this conversion, it's pretty simple to know if the value is in a range. For example,

"HC52" → ["HC", "52"]
       → ["HC", 52]
       → [(7 × 26 + 2), 52]
       → [184, 52]

26 ≤ 184 ≤ 675 and 12 ≤ 52 ≤ 789, so the value is in the range.

"HC999" → ["HC", "999"]
        → ["HC", 999]
        → [(7 × 26 + 2), 999]
        → [184, 999]

26 ≤ 184 ≤ 675, but (12 ≤ 999 ≤ 789) is false, so the value is outside of the range.

share|improve this answer
    
How would this handle "AZ100-BZ200" where Z is meant to be a constant (BB should not be accepted)? –  MichaelT Dec 5 '12 at 18:50
    
@MichaelT: You can't, given that, as specified in the original question, "AAA-ZZZ [...] needs to match [...] ABC". How would the machine know if a character is a constant or a part of the range? –  MainMa Dec 5 '12 at 19:26
    
@insta Consider if the range in the second paragraph was instead "AFLOOR-FFLOOR"? Is that a possible valid range string? –  MichaelT Dec 5 '12 at 19:35
    
@MichaelT: yes thats a valid range. –  insta Dec 5 '12 at 20:18
add comment

Tighten the requirements.

In the specification as described, there is a significant amount of ambiguity in the grammar. The range A100-A200 has more than two valid strings. The question is does the 00 part of the range described in this example designate a character class (any digit) or a constant string?

No matter which way you chose, there is the possibility that you will be wrong for some intended range.

The options are you can guess, you can try a natural language library (and have it guess instead of you), or you can tighten the requirements to remove such ambiguities.

I would strongly advise trying to tighten the requirements. Alternatives to this will have perceived bugs and unclear documentation for the end user.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.