Parsing a mathematical expression

Question

Given a string containing a mathematical expression, given a set of functions/commands and given a set of assigned variables, are there tools that .NET provides to quickly build a parser?

I would like to build a simple parser that analyzes an expression and breaks it into its simplest components, for example:

d*(abs(a-b)+sqrt(c))

becomes

1. f = abs(a-b) and g = sqrt(c)
2. e = f + g
3. d*e

Answer 1

Do you want to build a parser or just have the solution presented?

Either way, check out nCalc. If you just need to solve it, grab the binaries. If you need to see how they parse out the expression tree, grab the source.

Answer 2

I've heard good things about the Grammatica parser generator. ANTLR is also widely used (especially in Java).

I assume you know how to define a BNF grammar and have learned about or built parsers in the past.

Answer 3

Check out veparser as well. Here is a sample code that shows how you can build an expression evaluator( the code parses the expression and directly calculates the output ). This sample can be modified to store the evaluation tree instead of running it.

using System;
using VeParser;

public class MathEvaluator : CharParser
{
    protected override Parser GetRootParser()
    {
        Func<double, double, double> productFunc = (value1, value2) => value1 * value2;
        Func<double, double, double> divideFunc = (value1, value2) => value1 / value2;
        Func<double, double, double> sumFunc = (value1, value2) => value1 + value2;
        Func<double, double, double> subtractFunc = (value1, value2) => value1 - value2;
        Func<double, double> negativeFunc = value => -value;
        Func<double, double> posititveFunc = value => value;


        var dot = token('.');
        var op = token('(');
        var cp = token(')');
        var sumOp = create(sumFunc, token('+'));
        var subtractOp = create(subtractFunc, token('-'));
        var positiveOp = create(posititveFunc, token('+'));
        var negativeOp = create(negativeFunc, token('-'));
        var productOp = create(productFunc, token('*'));
        var divideOp = create(divideFunc, token('/'));

        // Numbers
        var deciamlPlaceValue = 1M;
        var decimalDot = run(() => { deciamlPlaceValue = 1; }, dot);
        var digit = consume((n, d) => n * 10 + char.GetNumericValue(d), keep(Digit));
        var decimalDigit = consume((n, d) => { deciamlPlaceValue = deciamlPlaceValue * 10; return (double)((decimal)n + ((decimal)char.GetNumericValue(d)) / deciamlPlaceValue); }, keep(Digit));
        var number = any(
            /* float */  create(0, seq(zeroOrMore(digit), decimalDot, oneOrMore(decimalDigit))),
            /* int   */  create(0, oneOrMore(digit))
        );

        var expression = createReference();
        var simpleExpression = createReference();
        // Unary
        var unaryOp = any(positiveOp, negativeOp);
        var unaryExpression = update(d => d.action(d.value),
                    createNew(seq(set("action", unaryOp), set("value", expression))));
        // Binary
        var binaryOp = any(sumOp, subtractOp, productOp, divideOp);

        var binaryExpressinoTree = update(x => x.value1, createNew(
            seq(
                set("value1", simpleExpression),
                zeroOrMore(
                    update(d => { var r = base.CreateDynamicObject(); r.value1 = d.action(d.value1, d.value2); return r; },
                        seq(
                            set("action", binaryOp),
                            set("value2", simpleExpression))))
            )));


        var privilegedExpressoin = seq(op, expression, cp);

        setReference(simpleExpression, any(privilegedExpressoin, unaryExpression, number));

        setReference(expression, any(binaryExpressinoTree, simpleExpression));

        return seq(expression, endOfFile());
    }

    public static object Eval(string expression)
    {
        MathEvaluator me = new MathEvaluator();
        var result = me.Parse(expression.ToCharArray());
        return result;
    }
}

Answer 4

Another Aproach

class Program
{
    static void Main(string[] args)
    {
        var a = 1;
        var b = 2;
        Console.WriteLine(FN_ParseSnippet($"{a} + {b} * 2"));
        Console.ReadKey();
    }

    public static object FN_ParseSnippet(string snippet)
    {
        object ret = null;

        var usingList = new List<string>();
        usingList.Add("System");
        usingList.Add("System.Collections.Generic");
        usingList.Add("System.Text");
        usingList.Add("Microsoft.CSharp");


        //Create method
        CodeMemberMethod pMethod = new CodeMemberMethod();
        pMethod.Name = "Execute";
        pMethod.Attributes = MemberAttributes.Public;
        pMethod.ReturnType = new CodeTypeReference(typeof(object));
        pMethod.Statements.Add(new CodeSnippetExpression(" return " + snippet));

        //Create Class
        CodeTypeDeclaration pClass = new System.CodeDom.CodeTypeDeclaration("Compilator");
        pClass.Attributes = MemberAttributes.Public;
        pClass.Members.Add(pMethod);
        //Create Namespace
        CodeNamespace pNamespace = new CodeNamespace("MyNamespace");
        pNamespace.Types.Add(pClass);
        foreach (string sUsing in usingList)
            pNamespace.Imports.Add(new CodeNamespaceImport(sUsing));

        //Create compile unit
        CodeCompileUnit pUnit = new CodeCompileUnit();
        pUnit.Namespaces.Add(pNamespace);


        CompilerParameters param = new CompilerParameters();
        param.GenerateInMemory = true;
        List<AssemblyName> pReferencedAssemblys = new List<AssemblyName>();
        pReferencedAssemblys = Assembly.GetExecutingAssembly().GetReferencedAssemblies().ToList();
        pReferencedAssemblys.Add(Assembly.GetExecutingAssembly().GetName());
        pReferencedAssemblys.Add(Assembly.GetCallingAssembly().GetName());
        foreach (AssemblyName asmName in pReferencedAssemblys)
        {
            Assembly asm = Assembly.Load(asmName);
            param.ReferencedAssemblies.Add(asm.Location);
        }

        //Compile
        CompilerResults pResults = (new CSharpCodeProvider()).CreateCompiler().CompileAssemblyFromDom(param, pUnit);

        if (pResults.Errors != null && pResults.Errors.Count > 0)
        {
            //foreach (CompilerError pError in pResults.Errors)
            //    MessageBox.Show(pError.ToString());

        }

        var instance = pResults.CompiledAssembly.CreateInstance("MyNamespace.Compilator");
        ret = instance.GetType().InvokeMember("Execute", BindingFlags.InvokeMethod, null, instance, null);

        return ret;
    }

}