Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
expression evaluator wich is easy to extend
////////////////////////////////////////////////////////////////////////////// // This source code and all associated files and resources are copyrighted by // the author(s). This source code and all associated files and resources may // be used as long as they are used according to the terms and conditions set // forth in The Code Project Open License (CPOL), which may be viewed at // http://www.blackbeltcoder.com/Legal/Licenses/CPOL. // // Copyright (c) 2010 Jonathan Wood // using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Rextester { /// <summary> /// Custom exception for evaluation errors /// </summary> public class EvalException : Exception { /// <summary> /// Zero-base position in expression where exception occurred /// </summary> public int Column { get; set; } /// <summary> /// Constructor /// </summary> /// <param name="message">Message that describes this exception</param> /// <param name="position">Position within expression where exception occurred</param> public EvalException(string message, int position) : base(message) { Column = position; } /// <summary> /// Gets the message associated with this exception /// </summary> public override string Message { get { return String.Format("{0} (column {1})", base.Message, Column + 1); } } } public enum SymbolStatus { OK, UndefinedSymbol, } // ProcessSymbol arguments public class SymbolEventArgs : EventArgs { public string Name { get; set; } public double Result { get; set; } public SymbolStatus Status { get; set; } } public enum FunctionStatus { OK, UndefinedFunction, WrongParameterCount, } // ProcessFunction arguments public class FunctionEventArgs : EventArgs { public string Name { get; set; } public List<double> Parameters { get; set; } public double Result { get; set; } public FunctionStatus Status { get; set; } } /// <summary> /// Expression evaluator class /// </summary> public class Eval { // Event handers public delegate void ProcessSymbolHandler(object sender, SymbolEventArgs e); public delegate void ProcessFunctionHandler(object sender, FunctionEventArgs e); public event ProcessSymbolHandler ProcessSymbol; public event ProcessFunctionHandler ProcessFunction; // Token state enums protected enum State { None = 0, Operand = 1, Operator = 2, UnaryOperator = 3 } // Error messages protected string ErrInvalidOperand = "Invalid operand"; protected string ErrOperandExpected = "Operand expected"; protected string ErrOperatorExpected = "Operator expected"; protected string ErrUnmatchedClosingParen = "Closing parenthesis without matching open parenthesis"; protected string ErrMultipleDecimalPoints = "Operand contains multiple decimal points"; protected string ErrUnexpectedCharacter = "Unexpected character encountered \"{0}\""; protected string ErrUndefinedSymbol = "Undefined symbol \"{0}\""; protected string ErrUndefinedFunction = "Undefined function \"{0}\""; protected string ErrClosingParenExpected = "Closing parenthesis expected"; protected string ErrWrongParamCount = "Wrong number of function parameters"; // To distinguish it from a minus operator, // we'll use a character unlikely to appear // in expressions to signify a unary negative protected const string UnaryMinus = "\x80"; // public Eval() { } /// <summary> /// Evaluates the given expression and returns the result /// </summary> /// <param name="expression">The expression to evaluate</param> /// <returns></returns> public double Execute(string expression) { return ExecuteTokens(TokenizeExpression(expression)); } /// <summary> /// Converts a standard infix expression to list of tokens in /// postfix order. /// </summary> /// <param name="expression">Expression to evaluate</param> /// <returns></returns> protected List<string> TokenizeExpression(string expression) { List<string> tokens = new List<string>(); Stack<string> stack = new Stack<string>(); State state = State.None; int parenCount = 0; string temp; TextParser parser = new TextParser(expression); while (!parser.EndOfText) { int charsCount = 1; string twoChars = parser.Peek().ToString() + parser.Peek(1).ToString(); if(new List<string>() {"!=", ">=", "<=", "&&", "||"}.Count(f => f==twoChars) > 0) charsCount = 2; if (Char.IsWhiteSpace(parser.Peek())) { // Ignore spaces, tabs, etc. } else if (parser.Peek() == '(') { // Cannot follow operand if (state == State.Operand) throw new EvalException(ErrOperatorExpected, parser.Position); // Allow additional unary operators after "(" if (state == State.UnaryOperator) state = State.Operator; // Push opening parenthesis onto stack stack.Push(parser.Peek().ToString()); // Track number of parentheses parenCount++; } else if (parser.Peek() == ')') { // Must follow operand if (state != State.Operand) throw new EvalException(ErrOperandExpected, parser.Position); // Must have matching open parenthesis if (parenCount == 0) throw new EvalException(ErrUnmatchedClosingParen, parser.Position); // Pop all operators until matching "(" found temp = stack.Pop(); while (temp != "(") { tokens.Add(temp); temp = stack.Pop(); } // Track number of parentheses parenCount--; } else if ("+-*/=!><".Contains(parser.Peek()) || charsCount == 2) { string peekedString = charsCount == 1 ? parser.Peek().ToString() : twoChars; // Need a bit of extra code to support unary operators if (state == State.Operand) { // Pop operators with precedence >= current operator int currPrecedence = GetPrecedence(peekedString); while (stack.Count > 0 && GetPrecedence(stack.Peek()) >= currPrecedence) tokens.Add(stack.Pop()); stack.Push(peekedString); state = State.Operator; } else if (state == State.UnaryOperator) { // Don't allow two unary operators together throw new EvalException(ErrOperandExpected, parser.Position); } else { // Test for unary operator if (peekedString == "-") { // Push unary minus stack.Push(UnaryMinus); state = State.UnaryOperator; } else if (peekedString == "+") { // Just ignore unary plus state = State.UnaryOperator; } else if (peekedString == "!") { stack.Push("!"); state = State.UnaryOperator; } else { throw new EvalException(ErrOperandExpected, parser.Position); } } } else if (Char.IsDigit(parser.Peek()) || parser.Peek() == '.' || parser.Peek() == ',') { if (state == State.Operand) { // Cannot follow other operand throw new EvalException(ErrOperatorExpected, parser.Position); } // Parse number temp = ParseNumberToken(parser); tokens.Add(temp); state = State.Operand; continue; } else { double result; // Parse symbols and functions if (state == State.Operand) { // Symbol or function cannot follow other operand throw new EvalException(ErrOperatorExpected, parser.Position); } if (!(Char.IsLetter(parser.Peek()) || parser.Peek() == '_')) { // Invalid character temp = String.Format(ErrUnexpectedCharacter, parser.Peek()); throw new EvalException(temp, parser.Position); } // Save start of symbol for error reporting int symbolPos = parser.Position; // Parse this symbol temp = ParseSymbolToken(parser); // Skip whitespace parser.MovePastWhitespace(); // Check for parameter list if (parser.Peek() == '(') { // Found parameter list, evaluate function result = EvaluateFunction(parser, temp, symbolPos); } else { // No parameter list, evaluate symbol (variable) result = EvaluateSymbol(temp, symbolPos); } // Handle negative result if (result < 0) { stack.Push(UnaryMinus); result = Math.Abs(result); } tokens.Add(result.ToString()); state = State.Operand; continue; } parser.MoveAhead(charsCount); } // Expression cannot end with operator if (state == State.Operator || state == State.UnaryOperator) throw new EvalException(ErrOperandExpected, parser.Position); // Check for balanced parentheses if (parenCount > 0) throw new EvalException(ErrClosingParenExpected, parser.Position); // Retrieve remaining operators from stack while (stack.Count > 0) tokens.Add(stack.Pop()); return tokens; } /// <summary> /// Parses and extracts a numeric value at the current position /// </summary> /// <param name="parser">TextParser object</param> /// <returns></returns> protected string ParseNumberToken(TextParser parser) { bool hasDecimal = false; int start = parser.Position; while (Char.IsDigit(parser.Peek()) || parser.Peek() == '.' || parser.Peek() == ',') { if (parser.Peek() == '.' || parser.Peek() == ',') { if (hasDecimal) throw new EvalException(ErrMultipleDecimalPoints, parser.Position); hasDecimal = true; } parser.MoveAhead(); } // Extract token string token = parser.Extract(start, parser.Position); if (token == "." || token == ",") throw new EvalException(ErrInvalidOperand, parser.Position - 1); return token; } /// <summary> /// Parses and extracts a symbol at the current position /// </summary> /// <param name="parser">TextParser object</param> /// <returns></returns> protected string ParseSymbolToken(TextParser parser) { int start = parser.Position; while (Char.IsLetterOrDigit(parser.Peek()) || parser.Peek() == '_') parser.MoveAhead(); return parser.Extract(start, parser.Position); } /// <summary> /// Evaluates a function and returns its value. It is assumed the current /// position is at the opening parenthesis of the argument list. /// </summary> /// <param name="parser">TextParser object</param> /// <param name="name">Name of function</param> /// <param name="pos">Position at start of function</param> /// <returns></returns> protected double EvaluateFunction(TextParser parser, string name, int pos) { double result = default(double); // Parse function parameters List<double> parameters = ParseParameters(parser); // We found a function reference FunctionStatus status = FunctionStatus.UndefinedFunction; if (ProcessFunction != null) { FunctionEventArgs args = new FunctionEventArgs(); args.Name = name; args.Parameters = parameters; args.Result = result; args.Status = FunctionStatus.OK; ProcessFunction(this, args); result = args.Result; status = args.Status; } if (status == FunctionStatus.UndefinedFunction) throw new EvalException(String.Format(ErrUndefinedFunction, name), pos); if (status == FunctionStatus.WrongParameterCount) throw new EvalException(ErrWrongParamCount, pos); return result; } /// <summary> /// Evaluates each parameter of a function's parameter list and returns /// a list of those values. An empty list is returned if no parameters /// were found. It is assumed the current position is at the opening /// parenthesis of the argument list. /// </summary> /// <param name="parser">TextParser object</param> /// <returns></returns> protected List<double> ParseParameters(TextParser parser) { // Move past open parenthesis parser.MoveAhead(); // Look for function parameters List<double> parameters = new List<double>(); parser.MovePastWhitespace(); if (parser.Peek() != ')') { // Parse function parameter list int paramStart = parser.Position; int parenCount = 1; while (!parser.EndOfText) { if (parser.Peek() == ',') { // Note: Ignore commas inside parentheses. They could be // from a parameter list for a function inside the parameters if (parenCount == 1) { parameters.Add(EvaluateParameter(parser, paramStart)); paramStart = parser.Position + 1; } } if (parser.Peek() == ')') { parenCount--; if (parenCount == 0) { parameters.Add(EvaluateParameter(parser, paramStart)); break; } } else if (parser.Peek() == '(') { parenCount++; } parser.MoveAhead(); } } // Make sure we found a closing parenthesis if (parser.Peek() != ')') throw new EvalException(ErrClosingParenExpected, parser.Position); // Move past closing parenthesis parser.MoveAhead(); // Return parameter list return parameters; } /// <summary> /// Extracts and evaluates a function parameter and returns its value. If an /// exception occurs, it is caught and the column is adjusted to reflect the /// position in original string, and the exception is rethrown. /// </summary> /// <param name="parser">TextParser object</param> /// <param name="paramStart">Column where this parameter started</param> /// <returns></returns> protected double EvaluateParameter(TextParser parser, int paramStart) { try { // Extract expression and evaluate it string expression = parser.Extract(paramStart, parser.Position); return Execute(expression); } catch (EvalException ex) { // Adjust column and rethrow exception ex.Column += paramStart; throw ex; } } /// <summary> /// This method evaluates a symbol name and returns its value. /// </summary> /// <param name="name">Name of symbol</param> /// <param name="pos">Position at start of symbol</param> /// <returns></returns> protected double EvaluateSymbol(string name, int pos) { double result = default(double); // We found a symbol reference SymbolStatus status = SymbolStatus.UndefinedSymbol; if (ProcessSymbol != null) { SymbolEventArgs args = new SymbolEventArgs(); args.Name = name; args.Result = result; args.Status = SymbolStatus.OK; ProcessSymbol(this, args); result = args.Result; status = args.Status; } if (status == SymbolStatus.UndefinedSymbol) throw new EvalException(String.Format(ErrUndefinedSymbol, name), pos); return result; } public double Precision { get { return 0.00000000001; //when doubles differ by less than this they are considered equal } } /// <summary> /// Evaluates the given list of tokens and returns the result. /// Tokens must appear in postfix order. /// </summary> /// <param name="tokens">List of tokens to evaluate.</param> /// <returns></returns> /// protected double ExecuteTokens(List<string> tokens) { Stack<double> stack = new Stack<double>(); double tmp, tmp2; foreach (string token in tokens) { // Is this a value token? int count = token.Count(c => Char.IsDigit(c) || c == '.' || c == ','); if (count == token.Length) { stack.Push(double.Parse(token)); } else if (token == "+") { stack.Push(stack.Pop() + stack.Pop()); } else if (token == "-") { tmp = stack.Pop(); tmp2 = stack.Pop(); stack.Push(tmp2 - tmp); } else if (token == "*") { stack.Push(stack.Pop() * stack.Pop()); } else if (token == "/") { tmp = stack.Pop(); tmp2 = stack.Pop(); stack.Push(tmp2 / tmp); } else if (token == "=") { tmp = stack.Pop(); tmp2 = stack.Pop(); stack.Push((Math.Abs(tmp - tmp2) < Precision) ? (double)1 : (double)0); } else if (token == ">") { tmp = stack.Pop(); tmp2 = stack.Pop(); if ((tmp2 - tmp) > Precision) stack.Push((double)1); else stack.Push((double)0); } else if (token == ">=") { tmp = stack.Pop(); tmp2 = stack.Pop(); if ((tmp2 - tmp) > Precision || Math.Abs(tmp - tmp2) < Precision) stack.Push((double)1); else stack.Push((double)0); } else if (token == "<") { tmp = stack.Pop(); tmp2 = stack.Pop(); if ((tmp - tmp2) > Precision) stack.Push((double)1); else stack.Push((double)0); } else if (token == "<=") { tmp = stack.Pop(); tmp2 = stack.Pop(); if ((tmp - tmp2) > Precision || Math.Abs(tmp - tmp2) < Precision) stack.Push((double)1); else stack.Push((double)0); } else if (token == "!=") { tmp = stack.Pop(); tmp2 = stack.Pop(); if (Math.Abs(tmp - tmp2) > Precision) stack.Push((double)1); else stack.Push((double)0); } else if (token == "&&") { tmp = stack.Pop(); tmp2 = stack.Pop(); if (Math.Abs(tmp) > Precision && Math.Abs(tmp2) > Precision) stack.Push((double)1); else stack.Push((double)0); } else if (token == "||") { tmp = stack.Pop(); tmp2 = stack.Pop(); if (Math.Abs(tmp) > Precision || Math.Abs(tmp2) > Precision) stack.Push((double)1); else stack.Push((double)0); } else if (token == "!") { tmp = stack.Pop(); if (Math.Abs(tmp) > Precision) stack.Push((double)0); else stack.Push((double)1); } else if (token == UnaryMinus) { stack.Push(-stack.Pop()); } } // Remaining item on stack contains result return (stack.Count > 0) ? stack.Pop() : 0.0; } /// <summary> /// Returns a value that indicates the relative precedence of /// the specified operator /// </summary> /// <param name="s">Operator to be tested</param> /// <returns></returns> protected int GetPrecedence(string s) { switch (s) { case "||": return 1; case "&&": return 2; case "=": case ">": case ">=": case "<": case "<=": case "!=": return 3; case "+": case "-": return 4; case "*": case "/": return 5; case "^": return 6; case "!": case UnaryMinus: return 10; } return 0; } } ////////////////////////////////////////////////////////////////////////////// // This source code and all associated files and resources are copyrighted by // the author(s). This source code and all associated files and resources may // be used as long as they are used according to the terms and conditions set // forth in The Code Project Open License (CPOL), which may be viewed at // http://www.blackbeltcoder.com/Legal/Licenses/CPOL. // // Copyright (c) 2010 Jonathan Wood // public class TextParser { private string _text; private int _pos; public string Text { get { return _text; } } public int Position { get { return _pos; } } public int Remaining { get { return _text.Length - _pos; } } public static char NullChar = (char)0; public TextParser() { Reset(null); } public TextParser(string text) { Reset(text); } /// <summary> /// Resets the current position to the start of the current document /// </summary> public void Reset() { _pos = 0; } /// <summary> /// Sets the current document and resets the current position to the start of it /// </summary> /// <param name="html"></param> public void Reset(string text) { _text = (text != null) ? text : String.Empty; _pos = 0; } /// <summary> /// Indicates if the current position is at the end of the current document /// </summary> public bool EndOfText { get { return (_pos >= _text.Length); } } /// <summary> /// Returns the character at the current position, or a null character if we're /// at the end of the document /// </summary> /// <returns>The character at the current position</returns> public char Peek() { return Peek(0); } /// <summary> /// Returns the character at the specified number of characters beyond the current /// position, or a null character if the specified position is at the end of the /// document /// </summary> /// <param name="ahead">The number of characters beyond the current position</param> /// <returns>The character at the specified position</returns> public char Peek(int ahead) { int pos = (_pos + ahead); if (pos < _text.Length) return _text[pos]; return NullChar; } /// <summary> /// Extracts a substring from the specified position to the end of the text /// </summary> /// <param name="start"></param> /// <returns></returns> public string Extract(int start) { return Extract(start, _text.Length); } /// <summary> /// Extracts a substring from the specified range of the current text /// </summary> /// <param name="start"></param> /// <param name="end"></param> /// <returns></returns> public string Extract(int start, int end) { return _text.Substring(start, end - start); } /// <summary> /// Moves the current position ahead one character /// </summary> public void MoveAhead() { MoveAhead(1); } /// <summary> /// Moves the current position ahead the specified number of characters /// </summary> /// <param name="ahead">The number of characters to move ahead</param> public void MoveAhead(int ahead) { _pos = Math.Min(_pos + ahead, _text.Length); } /// <summary> /// Moves to the next occurrence of the specified string /// </summary> /// <param name="s">String to find</param> /// <param name="ignoreCase">Indicates if case-insensitive comparisons are used</param> public void MoveTo(string s, bool ignoreCase = false) { _pos = _text.IndexOf(s, _pos, ignoreCase ? StringComparison.OrdinalIgnoreCase : StringComparison.Ordinal); if (_pos < 0) _pos = _text.Length; } /// <summary> /// Moves to the next occurrence of the specified character /// </summary> /// <param name="c">Character to find</param> public void MoveTo(char c) { _pos = _text.IndexOf(c, _pos); if (_pos < 0) _pos = _text.Length; } /// <summary> /// Moves to the next occurrence of any one of the specified /// characters /// </summary> /// <param name="chars">Array of characters to find</param> public void MoveTo(char[] chars) { _pos = _text.IndexOfAny(chars, _pos); if (_pos < 0) _pos = _text.Length; } /// <summary> /// Moves to the next occurrence of any character that is not one /// of the specified characters /// </summary> /// <param name="chars">Array of characters to move past</param> public void MovePast(char[] chars) { while (IsInArray(Peek(), chars)) MoveAhead(); } /// <summary> /// Determines if the specified character exists in the specified /// character array. /// </summary> /// <param name="c">Character to find</param> /// <param name="chars">Character array to search</param> /// <returns></returns> protected bool IsInArray(char c, char[] chars) { foreach (char ch in chars) { if (c == ch) return true; } return false; } /// <summary> /// Moves the current position to the first character that is part of a newline /// </summary> public void MoveToEndOfLine() { char c = Peek(); while (c != '\r' && c != '\n' && !EndOfText) { MoveAhead(); c = Peek(); } } /// <summary> /// Moves the current position to the next character that is not whitespace /// </summary> public void MovePastWhitespace() { while (Char.IsWhiteSpace(Peek())) MoveAhead(); } } public class Program { public static void Main(string[] args) { try { /* Origin: http://www.blackbeltcoder.com/Articles/algorithms/a-c-expression-evaluator * * New: * Not just '.', but also ',' is considered as floating part delimiter. This needs work, though. * * boolean: 1 is true, 0 is false * boolean operators: =, !=, >, >=, <, <=, &&, ||, ! (unary not) * if(expression_to_evaluate, expression_if_true, expression_if_false) */ string expression = @"if(!(5+2*3 >= 11 && 10<10), if(1=0, 9*9, round(pi*abs(pow(-3,2)) + sqrt(47*(27+14)))), 8*8)"; // Evaluate the current expression Eval eval = new Eval(); eval.ProcessSymbol += ProcessSymbol; eval.ProcessFunction += ProcessFunction; Console.WriteLine(eval.Execute(expression)); } catch (EvalException ex) { // Report expression error and move caret to error position Console.WriteLine("Badly formed expression (column {0}): {1}", ex.Column, ex.Message); } catch (Exception ex) { // Unknown error Console.WriteLine("Unexpected error : " + ex.Message); } } // Implement expression symbols static void ProcessSymbol(object sender, SymbolEventArgs e) { if (String.Compare(e.Name, "pi", true) == 0) { e.Result = Math.PI; } // Unknown symbol name else e.Status = SymbolStatus.UndefinedSymbol; } // Implement expression functions static void ProcessFunction(object sender, FunctionEventArgs e) { if (String.Compare(e.Name, "if", true) == 0) { if (e.Parameters.Count == 3) { if(Math.Abs(e.Parameters[0]) < (sender as Eval).Precision) e.Result = e.Parameters[2]; else e.Result = e.Parameters[1]; } else e.Status = FunctionStatus.WrongParameterCount; } else if (String.Compare(e.Name, "abs", true) == 0) { if (e.Parameters.Count == 1) e.Result = Math.Abs(e.Parameters[0]); else e.Status = FunctionStatus.WrongParameterCount; } else if (String.Compare(e.Name, "pow", true) == 0) { if (e.Parameters.Count == 2) e.Result = Math.Pow(e.Parameters[0], e.Parameters[1]); else e.Status = FunctionStatus.WrongParameterCount; } else if (String.Compare(e.Name, "round", true) == 0) { if (e.Parameters.Count == 1) e.Result = Math.Round(e.Parameters[0]); else e.Status = FunctionStatus.WrongParameterCount; } else if (String.Compare(e.Name, "sqrt", true) == 0) { if (e.Parameters.Count == 1) e.Result = Math.Sqrt(e.Parameters[0]); else e.Status = FunctionStatus.WrongParameterCount; } // Unknown function name else e.Status = FunctionStatus.UndefinedFunction; } } }
run
|
edit
|
history
|
help
0
a5
regimeketopdf
Daily Coding Problem: Problem #1
Schrikkeljaar
Main4-1
Test
Fórum ➡ Building a List<> with questions and answers, from data in TXT file, using LINQ ♦
Listas JL
project euler 11, C#
XmlException in XmlSerializer.Deserialize when XML has \0