Hallo,
ich arbeite gerade an einem kleinen Vektrorrechner. Leider ists mal wieder etwas ausgeufert
Soweit funktioniert er auch ganz gut. Ausdrücke wie
Hier ist der Shunting Yard
Spoiler anzeigen
und der Tokeniser
Spoiler anzeigen
Den ^ habe ich mir mal hier geliehen.
Habt ihr da eine Idee?
Grüße
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
C#-Quellcode
- public class ShuntingYard
- {
- Tokeniser tokeniser = new Tokeniser();
- public Queue<TokenMatch> Perform(string term)
- {
- Queue<TokenMatch> result = new Queue<TokenMatch>();
- Stack<TokenMatch> operators = new Stack<TokenMatch>();
- Queue<TokenMatch> input = new Queue<TokenMatch>(tokeniser.Tokenise(term));
- foreach (TokenMatch t in input)
- t.Cast();
- while (input.Count != 0)
- {
- TokenMatch token = input.Dequeue();
- if (token.IsNumber)
- result.Enqueue(token);
- if (token.IsFunction)
- operators.Push(token);
- if (token.IsSeperator)
- {
- if (operators.Count == 0)
- throw new FormatException("Missing paranthesis or invalid seperator");
- while (operators.Peek().TokenType != Tokens.OpenParenthesis)
- {
- result.Enqueue(operators.Pop());
- if (operators.Count == 0)
- throw new FormatException("Missing paranthesis or invalid seperator");
- }
- }
- if (token.IsOperator)
- {
- while (operators.Count > 0 && operators.Peek().IsOperator && token.Operation.IsLeftAssociative
- && token.Operation.Precedence <= operators.Peek().Operation.Precedence)
- {
- result.Enqueue(operators.Pop());
- }
- operators.Push(token);
- }
- if (token.TokenType == Tokens.OpenParenthesis)
- operators.Push(token);
- if (token.TokenType == Tokens.CloseParenthesis)
- {
- if (operators.Count == 0)
- throw new FormatException("Missing opening paranthesis");
- while (operators.Peek().TokenType != Tokens.OpenParenthesis)
- {
- result.Enqueue(operators.Pop());
- if (operators.Count == 0)
- throw new FormatException("Missing opening paranthesis");
- }
- operators.Pop();
- if (operators.Count > 0 && operators.Peek().IsFunction)
- result.Enqueue(operators.Pop());
- }
- }
- while (operators.Count > 0)
- {
- TokenMatch token = operators.Pop();
- if (token.TokenType == Tokens.OpenParenthesis)
- throw new FormatException("Too many paranthesis");
- result.Enqueue(token);
- }
- return result;
- }
- public IMathElement Evaluate(Queue<TokenMatch> rpn)
- {
- Stack<TokenMatch> buffer = new Stack<TokenMatch>();
- while (rpn.Count > 0)
- {
- TokenMatch token = rpn.Dequeue();
- if (token.IsNumber)
- buffer.Push(token);
- if (token.IsOperator || token.IsFunction)
- {
- if (token.Operation.HasRightParam)
- {
- if (token.Operation.RightParam == null)
- token.Operation.RightParam = buffer.Pop().Element;
- var left = buffer.Pop();
- IMathElement elem = left.Element.ExecuteOp(token.Operation);
- buffer.Push(elem.CreateToken());
- }
- else
- {
- var left = buffer.Pop();
- IMathElement elem = left.Element.ExecuteOp(token.Operation);
- buffer.Push(elem.CreateToken());
- }
- }
- }
- return buffer.Pop().Element;
- }
- }
und der Tokeniser
C#-Quellcode
- public enum Tokens
- {
- Number, Seperator, StringValue, OpenParenthesis, CloseParenthesis, Add, Subtract, Multiply, Divide, Vector, Absolute, Root, Power,
- Cross, Dot, Magnitude, Sin, Cos, Tan, Asin, Acos, Atan, Normalise, Const, Log, Mod
- }
- public class TokenDefinition
- {
- private Regex regex;
- private int precedence;
- private Tokens type;
- public TokenDefinition(Tokens token, string regexPattern, int precedence)
- {
- regex = new Regex(regexPattern, RegexOptions.IgnoreCase | RegexOptions.Compiled);
- type = token;
- this.precedence = precedence;
- }
- public IEnumerable<TokenMatch> FindMatches(string inputString)
- {
- var matches = regex.Matches(inputString);
- for (int i = 0; i < matches.Count; i++)
- {
- yield return new TokenMatch()
- {
- StartIndex = matches[i].Index,
- EndIndex = matches[i].Index + matches[i].Length,
- TokenType = type,
- Value = matches[i].Value,
- Precedence = precedence
- };
- }
- }
- }
- public class TokenMatch
- {
- public Tokens TokenType { get; set; }
- public string Value { get; set; }
- public int StartIndex { get; set; }
- public int EndIndex { get; set; }
- public int Precedence { get; set; }
- public bool IsFunction => !IsNumber && !IsOperator && !IsSeperator && TokenType != Tokens.OpenParenthesis && TokenType != Tokens.CloseParenthesis;
- public bool IsSeperator => TokenType == Tokens.Seperator;
- public bool IsOperator => TokenType == Tokens.Add || TokenType == Tokens.Divide || TokenType == Tokens.Multiply || TokenType == Tokens.Power || TokenType == Tokens.Subtract
- || TokenType == Tokens.Dot || TokenType == Tokens.Cross || TokenType == Tokens.Mod;
- public bool IsNumber => TokenType == Tokens.Vector || TokenType == Tokens.Number || TokenType == Tokens.StringValue;
- public IMathElement Element { get; set; } = null;
- public IOperation Operation { get; set; } = null;
- }
- public class Tokeniser
- {
- public List<TokenDefinition> AvailableTokens { get; set; }
- public Tokeniser()
- {
- AvailableTokens = new List<TokenDefinition>();
- AvailableTokens.Add(new TokenDefinition(Tokens.Number, "\\d+\\.\\d+|\\d+", 2));
- AvailableTokens.Add(new TokenDefinition(Tokens.Number, "e|pi|inf", 2));
- AvailableTokens.Add(new TokenDefinition(Tokens.OpenParenthesis, "\\(", 1));
- AvailableTokens.Add(new TokenDefinition(Tokens.CloseParenthesis, "\\)", 1));
- AvailableTokens.Add(new TokenDefinition(Tokens.Vector, "\\[\\s*(\\d+\\.\\d+|\\d+|\"[^\"]*\"|pi|e|inf)(\\s*\\,\\s*(\\d+\\.\\d+|\\d+|\"[^\"]*\"|e|pi|inf)\\s*)*\\s*\\]", 1));
- AvailableTokens.Add(new TokenDefinition(Tokens.Add, "\\+", 1));
- AvailableTokens.Add(new TokenDefinition(Tokens.Subtract, "\\-", 1));
- AvailableTokens.Add(new TokenDefinition(Tokens.Multiply, "\\*", 1));
- AvailableTokens.Add(new TokenDefinition(Tokens.Divide, "\\/", 1));
- AvailableTokens.Add(new TokenDefinition(Tokens.Absolute, @"abs", 1));
- AvailableTokens.Add(new TokenDefinition(Tokens.Root, @"root|sqrt", 1));
- AvailableTokens.Add(new TokenDefinition(Tokens.Power, @"\^", 1));
- AvailableTokens.Add(new TokenDefinition(Tokens.Cross, "cross", 1));
- AvailableTokens.Add(new TokenDefinition(Tokens.Dot, "dot", 1));
- AvailableTokens.Add(new TokenDefinition(Tokens.Magnitude, "len", 1));
- AvailableTokens.Add(new TokenDefinition(Tokens.Sin, "sin", 1));
- AvailableTokens.Add(new TokenDefinition(Tokens.Cos, "cos", 1));
- AvailableTokens.Add(new TokenDefinition(Tokens.Tan, "tan", 1));
- AvailableTokens.Add(new TokenDefinition(Tokens.Asin, "asin", 1));
- AvailableTokens.Add(new TokenDefinition(Tokens.Acos, "acos", 1));
- AvailableTokens.Add(new TokenDefinition(Tokens.Atan, "atan", 1));
- AvailableTokens.Add(new TokenDefinition(Tokens.StringValue, "\"[^\"]*\"", 1));
- AvailableTokens.Add(new TokenDefinition(Tokens.Seperator, @"\,", 1));
- AvailableTokens.Add(new TokenDefinition(Tokens.Normalise, "norm", 1));
- AvailableTokens.Add(new TokenDefinition(Tokens.Log, "log", 1));
- AvailableTokens.Add(new TokenDefinition(Tokens.Mod, "\\%", 1));
- }
- public IEnumerable<TokenMatch> Tokenise(string term)
- {
- var tokenMatches = FindTokenMatches(term);
- var groupedByIndex = tokenMatches.GroupBy(x => x.StartIndex)
- .OrderBy(x => x.Key)
- .ToList();
- TokenMatch lastMatch = null;
- for (int i = 0; i < groupedByIndex.Count; i++)
- {
- var bestMatch = groupedByIndex[i].OrderBy(x => x.Precedence).First();
- if (lastMatch != null && bestMatch.StartIndex < lastMatch.EndIndex)
- continue;
- yield return bestMatch;
- lastMatch = bestMatch;
- }
- }
- private List<TokenMatch> FindTokenMatches(string term)
- {
- var tokenMatches = new List<TokenMatch>();
- foreach (var tokenDefinition in AvailableTokens)
- tokenMatches.AddRange(tokenDefinition.FindMatches(term).ToList());
- return tokenMatches;
- }
- }
Den ^ habe ich mir mal hier geliehen.
Habt ihr da eine Idee?
Grüße