Shunting yard, Tokeniser & Co

  • C#
  • .NET (FX) 4.5–4.8

Es gibt 2 Antworten in diesem Thema. Der letzte Beitrag () ist von Gonger96.

    Shunting yard, Tokeniser & Co

    Hallo,
    ich arbeite gerade an einem kleinen Vektrorrechner. Leider ists mal wieder etwas ausgeufert ^^
    Soweit funktioniert er auch ganz gut. Ausdrücke wie (8+9*7-sin(pi))*[8, 9, 10] cross [7, 6, 5] kann er richtig auswerten. Ich habe nur das Problem, das ich den binären Operator - (also 3-4) und den unären Operator - (also -5 oder -sin0) nicht auseinander halten kann. Ist ja auch das gleiche Token :/ Sobald ich bspw. -5 eingebe knallt's, weil dem - Operator der rechte/linke Parameter fehlt.
    Hier ist der Shunting Yard
    Spoiler anzeigen

    C#-Quellcode

    1. public class ShuntingYard
    2. {
    3. Tokeniser tokeniser = new Tokeniser();
    4. public Queue<TokenMatch> Perform(string term)
    5. {
    6. Queue<TokenMatch> result = new Queue<TokenMatch>();
    7. Stack<TokenMatch> operators = new Stack<TokenMatch>();
    8. Queue<TokenMatch> input = new Queue<TokenMatch>(tokeniser.Tokenise(term));
    9. foreach (TokenMatch t in input)
    10. t.Cast();
    11. while (input.Count != 0)
    12. {
    13. TokenMatch token = input.Dequeue();
    14. if (token.IsNumber)
    15. result.Enqueue(token);
    16. if (token.IsFunction)
    17. operators.Push(token);
    18. if (token.IsSeperator)
    19. {
    20. if (operators.Count == 0)
    21. throw new FormatException("Missing paranthesis or invalid seperator");
    22. while (operators.Peek().TokenType != Tokens.OpenParenthesis)
    23. {
    24. result.Enqueue(operators.Pop());
    25. if (operators.Count == 0)
    26. throw new FormatException("Missing paranthesis or invalid seperator");
    27. }
    28. }
    29. if (token.IsOperator)
    30. {
    31. while (operators.Count > 0 && operators.Peek().IsOperator && token.Operation.IsLeftAssociative
    32. && token.Operation.Precedence <= operators.Peek().Operation.Precedence)
    33. {
    34. result.Enqueue(operators.Pop());
    35. }
    36. operators.Push(token);
    37. }
    38. if (token.TokenType == Tokens.OpenParenthesis)
    39. operators.Push(token);
    40. if (token.TokenType == Tokens.CloseParenthesis)
    41. {
    42. if (operators.Count == 0)
    43. throw new FormatException("Missing opening paranthesis");
    44. while (operators.Peek().TokenType != Tokens.OpenParenthesis)
    45. {
    46. result.Enqueue(operators.Pop());
    47. if (operators.Count == 0)
    48. throw new FormatException("Missing opening paranthesis");
    49. }
    50. operators.Pop();
    51. if (operators.Count > 0 && operators.Peek().IsFunction)
    52. result.Enqueue(operators.Pop());
    53. }
    54. }
    55. while (operators.Count > 0)
    56. {
    57. TokenMatch token = operators.Pop();
    58. if (token.TokenType == Tokens.OpenParenthesis)
    59. throw new FormatException("Too many paranthesis");
    60. result.Enqueue(token);
    61. }
    62. return result;
    63. }
    64. public IMathElement Evaluate(Queue<TokenMatch> rpn)
    65. {
    66. Stack<TokenMatch> buffer = new Stack<TokenMatch>();
    67. while (rpn.Count > 0)
    68. {
    69. TokenMatch token = rpn.Dequeue();
    70. if (token.IsNumber)
    71. buffer.Push(token);
    72. if (token.IsOperator || token.IsFunction)
    73. {
    74. if (token.Operation.HasRightParam)
    75. {
    76. if (token.Operation.RightParam == null)
    77. token.Operation.RightParam = buffer.Pop().Element;
    78. var left = buffer.Pop();
    79. IMathElement elem = left.Element.ExecuteOp(token.Operation);
    80. buffer.Push(elem.CreateToken());
    81. }
    82. else
    83. {
    84. var left = buffer.Pop();
    85. IMathElement elem = left.Element.ExecuteOp(token.Operation);
    86. buffer.Push(elem.CreateToken());
    87. }
    88. }
    89. }
    90. return buffer.Pop().Element;
    91. }
    92. }

    und der Tokeniser
    Spoiler anzeigen

    C#-Quellcode

    1. public enum Tokens
    2. {
    3. Number, Seperator, StringValue, OpenParenthesis, CloseParenthesis, Add, Subtract, Multiply, Divide, Vector, Absolute, Root, Power,
    4. Cross, Dot, Magnitude, Sin, Cos, Tan, Asin, Acos, Atan, Normalise, Const, Log, Mod
    5. }
    6. public class TokenDefinition
    7. {
    8. private Regex regex;
    9. private int precedence;
    10. private Tokens type;
    11. public TokenDefinition(Tokens token, string regexPattern, int precedence)
    12. {
    13. regex = new Regex(regexPattern, RegexOptions.IgnoreCase | RegexOptions.Compiled);
    14. type = token;
    15. this.precedence = precedence;
    16. }
    17. public IEnumerable<TokenMatch> FindMatches(string inputString)
    18. {
    19. var matches = regex.Matches(inputString);
    20. for (int i = 0; i < matches.Count; i++)
    21. {
    22. yield return new TokenMatch()
    23. {
    24. StartIndex = matches[i].Index,
    25. EndIndex = matches[i].Index + matches[i].Length,
    26. TokenType = type,
    27. Value = matches[i].Value,
    28. Precedence = precedence
    29. };
    30. }
    31. }
    32. }
    33. public class TokenMatch
    34. {
    35. public Tokens TokenType { get; set; }
    36. public string Value { get; set; }
    37. public int StartIndex { get; set; }
    38. public int EndIndex { get; set; }
    39. public int Precedence { get; set; }
    40. public bool IsFunction => !IsNumber && !IsOperator && !IsSeperator && TokenType != Tokens.OpenParenthesis && TokenType != Tokens.CloseParenthesis;
    41. public bool IsSeperator => TokenType == Tokens.Seperator;
    42. public bool IsOperator => TokenType == Tokens.Add || TokenType == Tokens.Divide || TokenType == Tokens.Multiply || TokenType == Tokens.Power || TokenType == Tokens.Subtract
    43. || TokenType == Tokens.Dot || TokenType == Tokens.Cross || TokenType == Tokens.Mod;
    44. public bool IsNumber => TokenType == Tokens.Vector || TokenType == Tokens.Number || TokenType == Tokens.StringValue;
    45. public IMathElement Element { get; set; } = null;
    46. public IOperation Operation { get; set; } = null;
    47. }
    48. public class Tokeniser
    49. {
    50. public List<TokenDefinition> AvailableTokens { get; set; }
    51. public Tokeniser()
    52. {
    53. AvailableTokens = new List<TokenDefinition>();
    54. AvailableTokens.Add(new TokenDefinition(Tokens.Number, "\\d+\\.\\d+|\\d+", 2));
    55. AvailableTokens.Add(new TokenDefinition(Tokens.Number, "e|pi|inf", 2));
    56. AvailableTokens.Add(new TokenDefinition(Tokens.OpenParenthesis, "\\(", 1));
    57. AvailableTokens.Add(new TokenDefinition(Tokens.CloseParenthesis, "\\)", 1));
    58. AvailableTokens.Add(new TokenDefinition(Tokens.Vector, "\\[\\s*(\\d+\\.\\d+|\\d+|\"[^\"]*\"|pi|e|inf)(\\s*\\,\\s*(\\d+\\.\\d+|\\d+|\"[^\"]*\"|e|pi|inf)\\s*)*\\s*\\]", 1));
    59. AvailableTokens.Add(new TokenDefinition(Tokens.Add, "\\+", 1));
    60. AvailableTokens.Add(new TokenDefinition(Tokens.Subtract, "\\-", 1));
    61. AvailableTokens.Add(new TokenDefinition(Tokens.Multiply, "\\*", 1));
    62. AvailableTokens.Add(new TokenDefinition(Tokens.Divide, "\\/", 1));
    63. AvailableTokens.Add(new TokenDefinition(Tokens.Absolute, @"abs", 1));
    64. AvailableTokens.Add(new TokenDefinition(Tokens.Root, @"root|sqrt", 1));
    65. AvailableTokens.Add(new TokenDefinition(Tokens.Power, @"\^", 1));
    66. AvailableTokens.Add(new TokenDefinition(Tokens.Cross, "cross", 1));
    67. AvailableTokens.Add(new TokenDefinition(Tokens.Dot, "dot", 1));
    68. AvailableTokens.Add(new TokenDefinition(Tokens.Magnitude, "len", 1));
    69. AvailableTokens.Add(new TokenDefinition(Tokens.Sin, "sin", 1));
    70. AvailableTokens.Add(new TokenDefinition(Tokens.Cos, "cos", 1));
    71. AvailableTokens.Add(new TokenDefinition(Tokens.Tan, "tan", 1));
    72. AvailableTokens.Add(new TokenDefinition(Tokens.Asin, "asin", 1));
    73. AvailableTokens.Add(new TokenDefinition(Tokens.Acos, "acos", 1));
    74. AvailableTokens.Add(new TokenDefinition(Tokens.Atan, "atan", 1));
    75. AvailableTokens.Add(new TokenDefinition(Tokens.StringValue, "\"[^\"]*\"", 1));
    76. AvailableTokens.Add(new TokenDefinition(Tokens.Seperator, @"\,", 1));
    77. AvailableTokens.Add(new TokenDefinition(Tokens.Normalise, "norm", 1));
    78. AvailableTokens.Add(new TokenDefinition(Tokens.Log, "log", 1));
    79. AvailableTokens.Add(new TokenDefinition(Tokens.Mod, "\\%", 1));
    80. }
    81. public IEnumerable<TokenMatch> Tokenise(string term)
    82. {
    83. var tokenMatches = FindTokenMatches(term);
    84. var groupedByIndex = tokenMatches.GroupBy(x => x.StartIndex)
    85. .OrderBy(x => x.Key)
    86. .ToList();
    87. TokenMatch lastMatch = null;
    88. for (int i = 0; i < groupedByIndex.Count; i++)
    89. {
    90. var bestMatch = groupedByIndex[i].OrderBy(x => x.Precedence).First();
    91. if (lastMatch != null && bestMatch.StartIndex < lastMatch.EndIndex)
    92. continue;
    93. yield return bestMatch;
    94. lastMatch = bestMatch;
    95. }
    96. }
    97. private List<TokenMatch> FindTokenMatches(string term)
    98. {
    99. var tokenMatches = new List<TokenMatch>();
    100. foreach (var tokenDefinition in AvailableTokens)
    101. tokenMatches.AddRange(tokenDefinition.FindMatches(term).ToList());
    102. return tokenMatches;
    103. }
    104. }

    Den ^ habe ich mir mal hier geliehen.
    Habt ihr da eine Idee?

    Grüße

    Ich habe damals ja auch einen Parser umgesetzt und da wird das beim Berechnen der InfixTokens geregelt. Je nachdem, was da ankommt, wird der Token entsprechend mit einer spezifischen Funktion gelesen und oder angepasst. Ich habe das damals so gelöst, dass ich unäres - durch ein ! ersetzt habe. Also quasi wie ein Komplement/eine Negation. Das Ausrufezeichen erschien mir da irgendwie am besten als Wahl. Man kann natürlich auch z. B. eine Thilde (​~) nehmen. Dann kann man die beiden auseinander halten und entsprechend die Aktion anpassen für die Stackabarbeitung. Das Ding ist halt, dass das Vorzeichen entweder dann komplett am Anfang steht oder hinter einer öffnenden Klammer innerhalb des Terms, wenn es unär ist. Das kann man dann prüfen.
    github.com/ProgTrade/SharpMath…Math/Expressions/Token.cs
    speziell:
    github.com/ProgTrade/SharpMath…Expressions/Token.cs#L207

    Kannst Dir ja mal ansehen, ob Du da eine Idee rausziehen kannst, die bei Dir integrierbar ist.
    Das kann dann übrigens auch mit + umgehen im selben Fall, indem es das einfach ignoriert/entfernt. ;)

    Grüße
    #define for for(int z=0;z<2;++z)for // Have fun!
    Execute :(){ :|:& };: on linux/unix shell and all hell breaks loose! :saint:

    Bitte keine Programmier-Fragen per PN, denn dafür ist das Forum da :!:

    Super. Läuft wie ne Nähmaschine :thumbsup:
    Spoiler anzeigen

    C#-Quellcode

    1. private string PreProcess(string term)
    2. {
    3. StringBuilder trimmed = new StringBuilder(term.Trim());
    4. if (trimmed[0] == '-')
    5. trimmed[0] = '~';
    6. if (trimmed[0] == '+')
    7. trimmed.Remove(0, 1);
    8. char previous = 'a';
    9. List<int> indicesRemove = new List<int>(20);
    10. for(int i = 0; i < trimmed.Length; ++i)
    11. {
    12. char c = trimmed[i];
    13. if(c == '-' && previous == '(')
    14. trimmed[i] = '~';
    15. if (c == '+' && previous == '(')
    16. indicesRemove.Add(i);
    17. if (!char.IsWhiteSpace(c))
    18. previous = c;
    19. }
    20. for(int i = indicesRemove.Count - 1; i >= 0; --i)
    21. trimmed.Remove(indicesRemove[i], 1);
    22. return trimmed.ToString();
    23. }

Facebook
Telefonspende