MathExpressionParser

ExpressionParser.cs

/* * * * * * * * * * * * * *
 * A simple expression parser
 * --------------------------
 * 
 * The parser can parse a mathematical expression into a simple custom
 * expression tree. It can recognise methods and fields/contants which
 * are user extensible. It can also contain expression parameters which
 * are registrated automatically. An expression tree can be "converted"
 * into a delegate.
 * 
 * Written by Bunny83
 * 2014-11-02
 * 
 * Features:
 * - Elementary arithmetic [ + - * / ]
* - Power [ ^ ]
* - Brackets ( )
* - Most function from System.Math (abs, sin, round, floor, min, ...)
* - Constants ( e, PI )
* - MultiValue return (quite slow, produce extra garbage each call)
* 
* Original URL: http://wiki.unity3d.com/index.php/ExpressionParser
* * * * * * * * * * * * * */

using System.Linq;
using System.Collections.Generic;


namespace B83.ExpressionParser
{
    public interface IValue
    {
        double Value { get; }
    }

    public class Number : IValue
    {
        private double m_Value;

        public double Value {
            get { return m_Value; }
            set { m_Value = value; }
        }

        public Number (double aValue)
        {
            m_Value = aValue;
        }

        public override string ToString ()
        {
            return "" + m_Value + "";
        }
    }

    public class OperationSum : IValue
    {
        private IValue[] m_Values;

        public double Value {
            get { return m_Values.Select (v => v.Value).Sum (); }
        }

        public OperationSum (params IValue[] aValues)
        {
            // collapse unnecessary nested sum operations.
            List<IValue> v = new List<IValue> (aValues.Length);
            foreach (var I in aValues) {
                var sum = I as OperationSum;
                if (sum == null)
                    v.Add (I);
                else
                    v.AddRange (sum.m_Values);
            }
            m_Values = v.ToArray ();
        }

        public override string ToString ()
        {
            return "( " + string.Join (" + ", m_Values.Select (v => v.ToString ()).ToArray ()) + " )";
        }
    }

    public class OperationProduct : IValue
    {
        private IValue[] m_Values;

        public double Value {
            get { return m_Values.Select (v => v.Value).Aggregate ((v1, v2) => v1 * v2); }
        }

        public OperationProduct (params IValue[] aValues)
        {
            m_Values = aValues;
        }

        public override string ToString ()
        {
            return "( " + string.Join (" * ", m_Values.Select (v => v.ToString ()).ToArray ()) + " )";
        }

    }

    public class OperationPower : IValue
    {
        private IValue m_Value;
        private IValue m_Power;

        public double Value {
            get { return System.Math.Pow (m_Value.Value, m_Power.Value); }
        }

        public OperationPower (IValue aValue, IValue aPower)
        {
            m_Value = aValue;
            m_Power = aPower;
        }

        public override string ToString ()
        {
            return "( " + m_Value + "^" + m_Power + " )";
        }

    }

    public class OperationNegate : IValue
    {
        private IValue m_Value;

        public double Value {
            get { return -m_Value.Value; }
        }

        public OperationNegate (IValue aValue)
        {
            m_Value = aValue;
        }

        public override string ToString ()
        {
            return "( -" + m_Value + " )";
        }

    }

    public class OperationReciprocal : IValue
    {
        private IValue m_Value;

        public double Value {
            get { return 1.0 / m_Value.Value; }
        }

        public OperationReciprocal (IValue aValue)
        {
            m_Value = aValue;
        }

        public override string ToString ()
        {
            return "( 1/" + m_Value + " )";
        }

    }

    public class MultiParameterList : IValue
    {
        private IValue[] m_Values;

        public IValue[] Parameters { get { return m_Values; } }

        public double Value {
            get { return m_Values.Select (v => v.Value).FirstOrDefault (); }
        }

        public MultiParameterList (params IValue[] aValues)
        {
            m_Values = aValues;
        }

        public override string ToString ()
        {
            return string.Join (", ", m_Values.Select (v => v.ToString ()).ToArray ());
        }
    }

    public class CustomFunction : IValue
    {
        private IValue[] m_Params;
        private System.Func<double[], double> m_Delegate;
        private string m_Name;

        public double Value {
            get {
                if (m_Params == null)
                    return m_Delegate (null);
                return m_Delegate (m_Params.Select (p => p.Value).ToArray ());
            }
        }

        public CustomFunction (string aName, System.Func<double[], double> aDelegate, params IValue[] aValues)
        {
            m_Delegate = aDelegate;
            m_Params = aValues;
            m_Name = aName;
        }

        public override string ToString ()
        {
            if (m_Params == null)
                return m_Name;
            return m_Name + "( " + string.Join (", ", m_Params.Select (v => v.ToString ()).ToArray ()) + " )";
        }
    }

    public class Parameter : Number
    {
        public string Name { get; private set; }

        public override string ToString ()
        {
            return Name + "[" + base.ToString () + "]";
        }

        public Parameter (string aName) : base (0)
        {
            Name = aName;
        }
    }

    public class Expression : IValue
    {
        public Dictionary<string, Parameter> Parameters = new Dictionary<string, Parameter> ();

        public IValue ExpressionTree { get; set; }

        public double Value {
            get { return ExpressionTree.Value; }
        }

        public double[] MultiValue {
            get {
                var t = ExpressionTree as MultiParameterList;
                if (t != null) {
                    double[] res = new double[t.Parameters.Length];
                    for (int i = 0; i < res.Length; i++)
                        res [i] = t.Parameters [i].Value;
                    return res;
                }
                return null;
            }
        }

        public override string ToString ()
        {
            return ExpressionTree.ToString ();
        }

        public ExpressionDelegate ToDelegate (params string[] aParamOrder)
        {
            var parameters = new List<Parameter> (aParamOrder.Length);
            for (int i = 0; i < aParamOrder.Length; i++) {
                if (Parameters.ContainsKey (aParamOrder [i]))
                    parameters.Add (Parameters [aParamOrder [i]]);
                else
                    parameters.Add (null);
            }
            var parameters2 = parameters.ToArray ();

            return (p) => Invoke (p, parameters2);
        }

        public MultiResultDelegate ToMultiResultDelegate (params string[] aParamOrder)
        {
            var parameters = new List<Parameter> (aParamOrder.Length);
            for (int i = 0; i < aParamOrder.Length; i++) {
                if (Parameters.ContainsKey (aParamOrder [i]))
                    parameters.Add (Parameters [aParamOrder [i]]);
                else
                    parameters.Add (null);
            }
            var parameters2 = parameters.ToArray ();


            return (p) => InvokeMultiResult (p, parameters2);
        }

        double Invoke (double[] aParams, Parameter[] aParamList)
        {
            int count = System.Math.Min (aParamList.Length, aParams.Length);
            for (int i = 0; i < count; i++) {
                if (aParamList [i] != null)
                    aParamList [i].Value = aParams [i];
            }
            return Value;
        }

        double[] InvokeMultiResult (double[] aParams, Parameter[] aParamList)
        {
            int count = System.Math.Min (aParamList.Length, aParams.Length);
            for (int i = 0; i < count; i++) {
                if (aParamList [i] != null)
                    aParamList [i].Value = aParams [i];
            }
            return MultiValue;
        }

        public static Expression Parse (string aExpression)
        {
            return new ExpressionParser ().EvaluateExpression (aExpression);
        }

        public class ParameterException : System.Exception
        {
            public ParameterException (string aMessage) : base (aMessage)
            {
            }

        }
    }
    public delegate double ExpressionDelegate (params double[] aParams);
    public delegate double[] MultiResultDelegate (params double[] aParams);



    public class ExpressionParser
    {
        private List<string> m_BracketHeap = new List<string> ();
        private Dictionary<string, System.Func<double>> m_Consts = new Dictionary<string, System.Func<double>> ();
        private Dictionary<string, System.Func<double[], double>> m_Funcs = new Dictionary<string, System.Func<double[], double>> ();
        private Expression m_Context;

        public ExpressionParser ()
        {
            var rnd = new System.Random ();
            m_Consts.Add ("PI", () => System.Math.PI);
            m_Consts.Add ("e", () => System.Math.E);
            m_Funcs.Add ("sqrt", (p) => System.Math.Sqrt (p.FirstOrDefault ()));
            m_Funcs.Add ("abs", (p) => System.Math.Abs (p.FirstOrDefault ()));
            m_Funcs.Add ("ln", (p) => System.Math.Log (p.FirstOrDefault ()));
            m_Funcs.Add ("floor", (p) => System.Math.Floor (p.FirstOrDefault ()));
            m_Funcs.Add ("ceiling", (p) => System.Math.Ceiling (p.FirstOrDefault ()));
            m_Funcs.Add ("round", (p) => System.Math.Round (p.FirstOrDefault ()));

            m_Funcs.Add ("sin", (p) => System.Math.Sin (p.FirstOrDefault ()));
            m_Funcs.Add ("cos", (p) => System.Math.Cos (p.FirstOrDefault ()));
            m_Funcs.Add ("tan", (p) => System.Math.Tan (p.FirstOrDefault ()));

            m_Funcs.Add ("asin", (p) => System.Math.Asin (p.FirstOrDefault ()));
            m_Funcs.Add ("acos", (p) => System.Math.Acos (p.FirstOrDefault ()));
            m_Funcs.Add ("atan", (p) => System.Math.Atan (p.FirstOrDefault ()));
            m_Funcs.Add ("atan2", (p) => System.Math.Atan2 (p.FirstOrDefault (), p.ElementAtOrDefault (1)));
            //System.Math.Floor
            m_Funcs.Add ("min", (p) => System.Math.Min (p.FirstOrDefault (), p.ElementAtOrDefault (1)));
            m_Funcs.Add ("max", (p) => System.Math.Max (p.FirstOrDefault (), p.ElementAtOrDefault (1)));
            m_Funcs.Add ("rnd", (p) => {
                if (p.Length == 2)
                    return p [0] + rnd.NextDouble () * (p [1] - p [0]);
                if (p.Length == 1)
                    return rnd.NextDouble () * p [0];
                return rnd.NextDouble ();
            });
        }

        public void AddFunc (string aName, System.Func<double[],double> aMethod)
        {
            if (m_Funcs.ContainsKey (aName))
                m_Funcs [aName] = aMethod;
            else
                m_Funcs.Add (aName, aMethod);
        }

        public void AddConst (string aName, System.Func<double> aMethod)
        {
            if (m_Consts.ContainsKey (aName))
                m_Consts [aName] = aMethod;
            else
                m_Consts.Add (aName, aMethod);
        }

        public void RemoveFunc (string aName)
        {
            if (m_Funcs.ContainsKey (aName))
                m_Funcs.Remove (aName);
        }

        public void RemoveConst (string aName)
        {
            if (m_Consts.ContainsKey (aName))
                m_Consts.Remove (aName);
        }

        int FindClosingBracket (ref string aText, int aStart, char aOpen, char aClose)
        {
            int counter = 0;
            for (int i = aStart; i < aText.Length; i++) {
                if (aText [i] == aOpen)
                    counter++;
                if (aText [i] == aClose)
                    counter--;
                if (counter == 0)
                    return i;
            }
            return -1;
        }

        void SubstitudeBracket (ref string aExpression, int aIndex)
        {
            int closing = FindClosingBracket (ref aExpression, aIndex, '(', ')');
            if (closing > aIndex + 1) {
                string inner = aExpression.Substring (aIndex + 1, closing - aIndex - 1);
                m_BracketHeap.Add (inner);
                string sub = "&" + (m_BracketHeap.Count - 1) + ";";
                aExpression = aExpression.Substring (0, aIndex) + sub + aExpression.Substring (closing + 1);
            } else
                throw new ParseException ("Bracket not closed!");
        }

        IValue Parse (string aExpression)
        {
            aExpression = aExpression.Trim ();
            int index = aExpression.IndexOf ('(');
            while (index >= 0) {
                SubstitudeBracket (ref aExpression, index);
                index = aExpression.IndexOf ('(');
            }
            if (aExpression.Contains (',')) {
                string[] parts = aExpression.Split (',');
                List<IValue> exp = new List<IValue> (parts.Length);
                for (int i = 0; i < parts.Length; i++) {
                    string s = parts [i].Trim ();
                    if (!string.IsNullOrEmpty (s))
                        exp.Add (Parse (s));
                }
                return new MultiParameterList (exp.ToArray ());
            } else if (aExpression.Contains ('+')) {
                string[] parts = aExpression.Split ('+');
                List<IValue> exp = new List<IValue> (parts.Length);
                for (int i = 0; i < parts.Length; i++) {
                    string s = parts [i].Trim ();
                    if (!string.IsNullOrEmpty (s))
                        exp.Add (Parse (s));
                }
                if (exp.Count == 1)
                    return exp [0];
                return new OperationSum (exp.ToArray ());
            } else if (aExpression.Contains ('-')) {
                string[] parts = aExpression.Split ('-');
                List<IValue> exp = new List<IValue> (parts.Length);
                if (!string.IsNullOrEmpty (parts [0].Trim ()))
                    exp.Add (Parse (parts [0]));
                for (int i = 1; i < parts.Length; i++) {
                    string s = parts [i].Trim ();
                    if (!string.IsNullOrEmpty (s))
                        exp.Add (new OperationNegate (Parse (s)));
                }
                if (exp.Count == 1)
                    return exp [0];
                return new OperationSum (exp.ToArray ());
            } else if (aExpression.Contains ('*')) {
                string[] parts = aExpression.Split ('*');
                List<IValue> exp = new List<IValue> (parts.Length);
                for (int i = 0; i < parts.Length; i++) {
                    exp.Add (Parse (parts [i]));
                }
                if (exp.Count == 1)
                    return exp [0];
                return new OperationProduct (exp.ToArray ());
            } else if (aExpression.Contains ('/')) {
                string[] parts = aExpression.Split ('/');
                List<IValue> exp = new List<IValue> (parts.Length);
                if (!string.IsNullOrEmpty (parts [0].Trim ()))
                    exp.Add (Parse (parts [0]));
                for (int i = 1; i < parts.Length; i++) {
                    string s = parts [i].Trim ();
                    if (!string.IsNullOrEmpty (s))
                        exp.Add (new OperationReciprocal (Parse (s)));
                }
                return new OperationProduct (exp.ToArray ());
            } else if (aExpression.Contains ('^')) {
                int pos = aExpression.IndexOf ('^');
                var val = Parse (aExpression.Substring (0, pos));
                var pow = Parse (aExpression.Substring (pos + 1));
                return new OperationPower (val, pow);
            }
            foreach (var M in m_Funcs) {
                if (aExpression.StartsWith (M.Key)) {
                    var inner = aExpression.Substring (M.Key.Length);
                    var param = Parse (inner);
                    var multiParams = param as MultiParameterList;
                    IValue[] parameters;
                    if (multiParams != null)
                        parameters = multiParams.Parameters;
                    else
                        parameters = new IValue[] { param };
                    return new CustomFunction (M.Key, M.Value, parameters);
                }
            }
            foreach (var C in m_Consts) {
                if (aExpression.StartsWith (C.Key)) {
                    return new CustomFunction (C.Key, (p) => C.Value (), null);
                }
            }
            int index2a = aExpression.IndexOf ('&');
            int index2b = aExpression.IndexOf (';');
            if (index2a >= 0 && index2b >= 2) {
                var inner = aExpression.Substring (index2a + 1, index2b - index2a - 1);
                int bracketIndex;
                if (int.TryParse (inner, out bracketIndex) && bracketIndex >= 0 && bracketIndex < m_BracketHeap.Count) {
                    return Parse (m_BracketHeap [bracketIndex]);
                } else
                    throw new ParseException ("Can't parse substitude token");
            }
            double doubleValue;
            if (double.TryParse (aExpression, out doubleValue)) {
                return new Number (doubleValue);
            }
            if (ValidIdentifier (aExpression)) {
                if (m_Context.Parameters.ContainsKey (aExpression))
                    return m_Context.Parameters [aExpression];
                var val = new Parameter (aExpression);
                m_Context.Parameters.Add (aExpression, val);
                return val;
            }

            throw new ParseException ("Reached unexpected end within the parsing tree");
        }

        private bool ValidIdentifier (string aExpression)
        {
            aExpression = aExpression.Trim ();
            if (string.IsNullOrEmpty (aExpression))
                return false;
            if (aExpression.Length < 1)
                return false;
            if (aExpression.Contains (" "))
                return false;
            if (!"abcdefghijklmnopqrstuvwxyz§$".Contains (char.ToLower (aExpression [0])))
                return false;
            if (m_Consts.ContainsKey (aExpression))
                return false;
            if (m_Funcs.ContainsKey (aExpression))
                return false;
            return true;
        }

        public Expression EvaluateExpression (string aExpression)
        {
            var val = new Expression ();
            m_Context = val;
            val.ExpressionTree = Parse (aExpression);
            m_Context = null;
            m_BracketHeap.Clear ();
            return val;
        }

        public double Evaluate (string aExpression)
        {
            return EvaluateExpression (aExpression).Value;
        }

        public static double Eval (string aExpression)
        {
            return new ExpressionParser ().Evaluate (aExpression);
        }

        public class ParseException : System.Exception
        {
            public ParseException (string aMessage) : base (aMessage)
            {
            }

        }
    }
}