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?
4
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.
4
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.