Requirements
A function is needed, that is able to parse a list of symbols with the following rules:
- Symbols may be associated with numbers or not.
- Numbers are defined by a comma separed list behind the symbol.
- Numbers may be defined as range (e.g. 3-7 or also 7-3).
- Whitespaces and invalid tokens should be ignored after token recognition finished.
- Whitespaces are not needed as seperators.
- The size / number of items to parse is not time critical.
Examples:
Available Symbols: ABC, CDE, A, B, C - A, B and C may be associated with numbers.
- "ABC CDE A 1, 2 B" => [ABC], [CDE], [A{1,2}], [B].
- "A1-4,6 CDE B C9-7,4,3" => [A{1,2,3,4,6}], [CDE], [B], [C{3,4,7,8,9}]
- "ABCBCA5,4" => [ABC], [B], [C], [A{4,5}]
Approach
Yes, a parser is a little oversized for that kind of string analysis. However, it is very likely that the complexity of the syntax will grow in the course of time, so I decide to write a parse that scales better that regex or string operations.
The parsing process works in 2 steps.
- Split string in tokens (Symbols, Numbers, Separator ',', Range operator '-')
- Parse tokens to list of objects
Tokenizer
I created a general purpose regex based Tokenizer
that produces a list of Token
objects from an input string. Each token has a type (can be defined when creating the Tokenizer
), an index (position of the token within the input string) and the actual value.
public class Token
{
public Token(string type, string token, int index)
{
Value = token;
Type = type;
Index = index;
}
public string Value { get; private set; }
public string Type { get; private set; }
public int Index { get; private set; }
}
Usage of the tokenizer:
Tokenizer tokenizer = Tokenizer.Empty
.WithToken(SYMBOL, "(ABC|CDE)")
.WithToken(SYMBOL_AND_NUMBERS, "(A|B|C|D|E|F)")
.WithToken(RANGE, "-")
.WithToken(SEPARATOR, ",")
.WithToken(NUMBER, "[0-9]+");
Token[] rokens = tokenizer.Parse("ABC B1,4-5");
// results in:
// Token (Value="ABC", Index=0, TYPE="SYMBOL")
// Token (Value="B", Index=4, TYPE="SYMBOL_AND_NUMBERS")
// Token (Value="1", Index=5, TYPE="NUMBER")
// Token (Value=",", Index=6, TYPE="SEPARATOR")
// Token (Value="4", Index=7, TYPE="NUMBER")
// Token (Value="-", Index=8, TYPE="RANGE")
// Token (Value="5", Index=9, TYPE="NUMBER")
Implementation of the Tokenizer
:
public class Tokenizer
{
private class TokenDefinition
{
private readonly Regex myRegex;
public TokenDefinition(string type, string regex)
{
myRegex = new Regex(regex, RegexOptions.IgnoreCase | RegexOptions.Compiled);
Type = type;
}
public string Type { get; set; }
public MatchCollection Matches(string input)
{
return myRegex.Matches(input);
}
}
private readonly List<TokenDefinition> myTokenDefinitions = new List<TokenDefinition>();
public Tokenizer WithToken(string type, params string[] regexes)
{
foreach (var regex in regexes)
myTokenDefinitions.Add(new TokenDefinition(type, regex));
return this;
}
public Token[] Tokenize(string input)
{
if (input == null)
input = string.Empty;
var occupied = new bool[input.Length];
return CollectTokens(input, occupied);
}
private Token[] CollectTokens(string input, bool[] occupied)
{
var tokens = new List<Token>();
foreach (var tokenDefinition in myTokenDefinitions)
foreach (var token in TokenizeInternal(input, occupied, tokenDefinition))
tokens.Add(token);
return tokens.OrderBy(t => t.Index).ToArray();
}
private static IEnumerable<Token> TokenizeInternal(string input, bool[] occupied, TokenDefinition tokenDefinition)
{
foreach (Match match in tokenDefinition.Matches(input))
{
if (!match.Success)
continue;
var indexRange = Enumerable.Range(match.Index, match.Length).ToList();
if (indexRange.Any(idx => occupied[idx]))
continue;
indexRange.ForEach(idx => occupied[idx] = true);
yield return new Token(tokenDefinition.Type, match.Value, match.Index);
}
}
public static Tokenizer Empty
{
get { return new Tokenizer(); }
}
}
Parser
The parser uses the Tokanizer
internally and produces a list of ParserResult objects:
public class ParserResult
{
public string Symbol { get; private set; }
public int[] Numbers { get; private set; }
public ParserResult(string symbol, params int[] numbers)
{
Symbol = symbol;
Numbers = numbers.OrderBy(n => n).ToArray();
}
}
The implementation of the Parser
:
public class Parser
{
public const string SYMBOL_WITH_NUMBERS = "SYMBOL_WITH_NUMBERS";
public const string SYMBOL = "SYMBOL";
public const string SEPARATOR = "SEPARATOR";
public const string RANGE = "RANGE";
public const string NUMBER = "NUMBER";
private readonly Tokenizer myTokenizer;
public Parser()
{
// note: first added token definitions have a higher prio (will be processed first).
myTokenizer = Tokenizer.Empty
.WithToken(SYMBOL, "(ABC|CDE)")
.WithToken(SYMBOL_WITH_NUMBERS, "(A|B|C|D|E|F)")
.WithToken(RANGE, "-")
.WithToken(SEPARATOR, ",")
.WithToken(NUMBER, "[0-9]+");
}
public IEnumerable<ParserResult> Parse(string input)
{
var tokens = myTokenizer.Tokenize(input);
foreach (var result in ParseInternal(tokens).Where(r => r != null))
yield return result;
}
private IEnumerable<ParserResult> ParseInternal(Token[] tokens)
{
var stack = new Stack<Token>();
for (int i = 0; i < tokens.Length; i++)
{
Token current = tokens[i];
switch (current.Type)
{
case NUMBER:
stack.Push(current);
break;
case SYMBOL_WITH_NUMBERS:
if (stack.Count > 0)
yield return FromStack(stack);
stack.Push(current);
break;
case RANGE:
stack.Push(current);
break;
case SEPARATOR:
// nothing to do
break;
case SYMBOL:
if (stack.Count > 0)
yield return FromStack(stack);
yield return new ParserResult(current.Value);
break;
default:
throw new InvalidOperationException("Invalid type: '" + current.Type + "'");
}
}
if (stack.Count > 0)
yield return FromStack(stack);
}
private ParserResult FromStack(Stack<Token> stack)
{
var numbers = new List<int>();
bool addRange = false;
while (stack.Count > 0)
{
var token = stack.Pop();
switch (token.Type)
{
case NUMBER:
AddNumber(numbers, int.Parse(token.Value), ref addRange);
break;
case SYMBOL_WITH_NUMBERS:
return new ParserResult(token.Value, numbers.ToArray());
case RANGE:
addRange = true;
break;
}
}
return null;
}
private void AddNumber(List<int> numbers, int numberToAdd, ref bool addRange)
{
var last = addRange && numbers.Any() ? numbers.Last() : numberToAdd;
var from = Math.Min(last, numberToAdd);
var count = Math.Max(Math.Abs(last - numberToAdd), 1);
foreach (var rangedNumberToAdd in Enumerable.Range(from, count))
if (!numbers.Contains(rangedNumberToAdd))
numbers.Add(rangedNumberToAdd);
addRange = false;
}
}
My first idea was to create a generic parser that can be configured (similar to the tokenizer), but that seems more difficult than thought. Therefore, I just created a specialized one for my problem. However I am not really happy with the implemention... so, all comments / suggestions for improvments are welcome.
"(ABC|DEF)"
be rather"(ABC|CDE)"
...? \$\endgroup\$AB C
andAB$C
should both evaluate to[ABC]
, not[AB], [C]
, right? Does that currently work correctly? \$\endgroup\$AB C
andAB$C
should both evaluate to[AB], [C]
. Strictly speaking 'ignored' is not correct... "Whitespaces should be ignored after token recognition finished" describes it better. \$\endgroup\$