Click here to Skip to main content
15,860,972 members
Articles / Programming Languages / C#
Article

Writing a fast formula interpreter

Rate me:
Please Sign up or sign in to vote.
4.27/5 (12 votes)
6 Apr 20063 min read 122.1K   2.7K   79   33
A tutorial on writing your own interpreter.

Screenshot

Introduction

Have you ever wondered how Microsoft Excel solves its formulas? This here is your way to get your own, personal and fast formula interpreter. It is used in products such as:

  • VariPlot - 2D Graph plotter
  • VariPlot3D - 3D Surface plotter
  • VariComplex - Fractals visualizer

Background

If you are writing a formula interpreter, you should decide which technology you want to use. As you might expect, there are lots and lots of possibilities to do this. I decided to do it recursively, because this offers a very easy way to use delegates, translate it into unmanaged C++, or add special functionality such as differential- and integral calculations.

Using the code

Using the interpreter is very easy:

  1. Initialize a new interpreter instance.
    C#
    private VariFormel fml=new VariFormel();
  2. If needed, add some variables. The chars a, b, c, d, e, f, g, h, x, y are allowed variable names. Variable names can only consist of one char.
    C#
    VariFormel.Variable var=
        new VariFormel.Variable("x",127.0);
    
    if (!fml.NeuV(var))
        MessageBox.Show("Variable name not allowed");
  3. Pass a string value to interpret.
    C#
    double res;
    
    if(!fml.Neu(tbFormel.Text,out res))
    {
        MessageBox.Show("Formula invalid");
    }
    else
        lblResult.Text=res.ToString();

How it works

The magic of the interpreter lies in a function called Zuteilung, which takes a string, analyzes it, and returns a number value, if the string is interpretable. If the string contains more than one command, the function calls itself recursively to get the rest of the string interpreted.

There are different types of commands which a string can contain:

  • the string is wrapped in brackets, e.g., (x*2) => you have to remove all outer opening brackets and their corresponding closing brackets.
  • the string is a constant, e.g., PI or EU => you have to return the value of the constant.
  • the string is a variable, e.g., a, b, c ... x, y => you have to return the value of the variable.
  • the string is a single-parameter function, e.g., sin(x*2) => you have to return the function of the recursively called value.
  • the string contains an operator, e.g., 2+3-4 => you have to return the last operation with the rest called recursively.
  • the string contains rubbish => return 0.0.
C#
/// <summary>
/// Rekursive Hauptprozedur, die die Formel ausrechnet
/// </summary>
/// <param name="Op">Der Text mit der Formel</param>
/// <returns>Das Ergebnis der
/// Formel oder 0 bei Fehlern</returns>
private double Zuteilung(string Op)
{
    if (Op.Length==0) goto fehl;
    if (Op.StartsWith("(") && 
              GetKlammer(Op,0) ==Op.Length-1)
        Op=Op.Substring(1,Op.Length-2);
    if (double.TryParse(Op,
            System.Globalization.NumberStyles.Float, 
            null,out res))
        return res;
    if (Op.Length==2 && Op=="PI") return Math.PI;
    if (Op.Length==1 && TryVariable(Op,out res)) return res;
    if (Op.Length>4 && Op.Substring(3,1)=="(")
    {
        pos=GetKlammer(Op,3);
        if (pos!=Op.Length-1) goto next;
        zc=Op.Substring(4,pos-4);
        switch (Op.Substring(0,3))
        {
            case "sqr":return Math.Sqrt(Zuteilung(zc));
            case "sin":return Math.Sin(Math.PI*Zuteilung(zc)/180);
            case "cos":return Math.Cos(Math.PI*Zuteilung(zc)/180);
            case "tan":return Math.Tan(Math.PI*Zuteilung(zc)/180);
            case "log":return Math.Log10(Zuteilung(zc));
            case "abs":return Math.Abs(Zuteilung(zc));
            case "fac":return Faculty(Zuteilung(zc));
        }
    }
    next: 
    pos=0;ebene=6;klammer=0;
    for (int i=Op.Length-1;i>-1;i--)
    {
        switch (Op.Substring(i,1))
        {
            case "(":klammer++;break;
            case ")":klammer--;break;
            case "+":if(klammer==0 && ebene>0){pos=i;ebene=0;}break;
            case "-":if(klammer==0 && ebene>1){pos=i;ebene=1;}break;
            case "*":if(klammer==0 && ebene>2){pos=i;ebene=2;}break;
            case "%":if(klammer==0 && ebene>3){pos=i;ebene=3;}break;
            case "/":if(klammer==0 && ebene>4){pos=i;ebene=4;}break;
            case "^":if(klammer==0 && ebene>5){pos=i;ebene=5;}break;
        }
    }
    if (pos==0 || pos==Op.Length-1) goto fehl;
    zc=Op.Substring(pos,1);
    string t1,t2;
    t1=Op.Substring(0,pos);
    t2=Op.Substring(pos+1,Op.Length-(pos+1));
    switch (zc)
    {
        case "+":return Zuteilung(t1)+Zuteilung(t2);
        case "-":return Zuteilung(t1)-Zuteilung(t2);
        case "*":return Zuteilung(t1)*Zuteilung(t2);
        case "/":return Zuteilung(t1)/Zuteilung(t2);
        case "%":return Math.IEEERemainder(Zuteilung(t1),Zuteilung(t2));
        case "^":return Math.Pow(Zuteilung(t1),Zuteilung(t2));
    }
    fehl:
    fehler=true;
    return 0.0;
}

When analyzing operator strings, you have pay special attention:

2+3-4-2 => you have to interpret it as ((2+3)-4)-2

To do this, you have to go through the formula from the back, and give the operators signs:

  • + 0
  • - 1
  • * 2
  • / 3
  • % 4
  • ^ 5

Then calculate the lowest sign operator, and you get a kind of a tree. But you have to take care about the brackets => you can only interpret the outer level of the formula:

2+3-(4-2) => you can't interpret the subtraction in brackets by now

Also, there is the problem of picking the right one of the wrapping brackets:

(3+2+4)+sin(x) => if you take the last bracket, it's wrong, 
                  you have to take the one after +4.

Therefore, you have to write a function to find the matching bracket always:

C#
/// <summary>
/// Sucht zu einer geöffneten Klammer die
/// Position der entsprechend schließenden Klammer
/// </summary>
/// <param name="Op">Der zu überprüfende Text</param>
/// <param name="start">Position der
/// eröffnenden Klammer</param>
/// <returns>Position der schließenden Klammer,
/// oder START, wenn keine vorhanden</returns>
private int GetKlammer(string Op,int start)
{
    int res=start;
    for (int i=start;i<Op.Length;i++)
    {
    switch (Op.Substring(i,1))
    {
    case "(":klammer++;break;
    case ")":klammer--;break;
    }
    if (klammer==0){res=i;break;}
    }
    return res;
}

The function increments a variable called klammer on every opening bracket, and decrements it on every closing bracket, and if its value reaches 0, it has found the corresponding position.

Furthermore, you have to decide if the string is a variable and then return its value. VariFormel uses two arrays for doing this, one double[] array for the values, and a string value for containing the names.

The allowed array is used for determining if the value name is suitable.

C#
private string vars="";
private const string allowed="abcdefgxyz";
private double[] values=new double[10];
C#
/// <summary>
/// Prüft, ob der Text eine Variable bezeichnet
/// und schreibt den Wert in eine Variable
/// </summary>
/// <param name="Op">Der zu überprüfende Text</param>
/// <param name="wert">Adresse der Variable,
/// die den Wert erhalten soll</param>
/// <returns>TRUE, wenn eine Variable
/// gefunden wurde</returns>
private bool TryVariable(string Op,out double wert)
{
    int i=vars.IndexOf(Op);
    if (i!=-1)
    {
    wert=values[i];
    return true;
    }
    else
    {
    wert=0.0;
    return false;
    }
}

The function is called by the main function.

The rest of the VariFormel class is used to provide a nice, easy to use code-structure, here only the main parts are explained.

For more information, see the source code itself.

Points of Interest

Unless I think it's very useful, this is just the beginning point of a formula interpreter. Just go forward and modify it to fit your personal needs. For example, the recursive procedure can easily be updated to use delegates, which is up to 4000 times faster and very good for iterational calculations (function plotters etc.). There is already a delegate-version working in VariPlot Reload.

VariPlot - 2D function plotter

VariPlot3D - 3D surface visualizer

VariComplex - complex fractals visualizer

If you translate VariFormel into C++ or make any other modifications, I would be glad if you would drop me a mail so I can see how VariFormel evolves.

Have fun with the code :-)

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
Other VariSoft Industries
Germany Germany
my name is ramon van blech

Comments and Discussions

 
GeneralGotos Pin
delly474731-Jul-14 7:40
delly474731-Jul-14 7:40 
GeneralMy vote of 5 Pin
Menon Santosh18-Sep-12 22:17
professionalMenon Santosh18-Sep-12 22:17 
Generaldoesn't work when the first simbol is negative Pin
onegreath25-Apr-11 3:49
onegreath25-Apr-11 3:49 
GeneralRe: doesn't work when the first simbol is negative Pin
Julian Ott25-Apr-11 3:52
Julian Ott25-Apr-11 3:52 
GeneralThe best thing is...It works! Pin
brclancy11115-Oct-09 1:18
brclancy11115-Oct-09 1:18 
GeneralRe: The best thing is...It works! Pin
Julian Ott15-Oct-09 10:16
Julian Ott15-Oct-09 10:16 
hi,
that will also work:

(-1)*(x^2)


there is a new version upcoming,
which features automatic
differentation, advanced
parsing, simplification and
drawing...

i will update the article as soon
as it's available
QuestionC#? Pin
schiefiix4-Sep-07 8:30
schiefiix4-Sep-07 8:30 
AnswerRe: C#? Pin
Julian Ott5-Sep-07 0:50
Julian Ott5-Sep-07 0:50 
GeneralDoes not cope with negative numbers Pin
Bryan Avery16-Aug-07 21:35
Bryan Avery16-Aug-07 21:35 
GeneralRe: Does not cope with negative numbers Pin
Julian Ott18-Aug-07 20:43
Julian Ott18-Aug-07 20:43 
GeneralCool. The primary task is *parsing*, for which tools already exist... Pin
sherifffruitfly8-Apr-07 7:40
sherifffruitfly8-Apr-07 7:40 
GeneralRe: Cool. The primary task is *parsing*, for which tools already exist... Pin
Julian Ott18-Aug-07 20:44
Julian Ott18-Aug-07 20:44 
GeneralError corrections Pin
Michael Goncharenko10-Jan-07 11:16
Michael Goncharenko10-Jan-07 11:16 
GeneralRe: Error corrections Pin
OrangeSwrd2-Jun-07 12:36
OrangeSwrd2-Jun-07 12:36 
GeneralRe: Error corrections Pin
Jonathan M Smith22-Aug-07 19:57
Jonathan M Smith22-Aug-07 19:57 
GeneralSuggestion Pin
The Monz6-Apr-06 21:48
The Monz6-Apr-06 21:48 
GeneralRe: Suggestion Pin
Julian Ott7-Apr-06 8:34
Julian Ott7-Apr-06 8:34 
GeneralRe: Suggestion Pin
Blubbo11-Apr-06 2:09
Blubbo11-Apr-06 2:09 
GeneralRe: Suggestion Pin
Julian Ott12-Apr-06 23:57
Julian Ott12-Apr-06 23:57 
GeneralRe: Suggestion Pin
icestatue13-Apr-06 1:59
icestatue13-Apr-06 1:59 
GeneralRe: Suggestion Pin
Roger Alsing21-Jun-06 23:55
Roger Alsing21-Jun-06 23:55 
GeneralNo German, please :-) Pin
Uwe Keim6-Apr-06 19:06
sitebuilderUwe Keim6-Apr-06 19:06 
GeneralRe: No German, please :-) Pin
User 66581-May-06 10:22
User 66581-May-06 10:22 
GeneralRe: No German, please :-) Pin
Julian Ott4-May-06 12:13
Julian Ott4-May-06 12:13 
GeneralRe: No German, please :-) Pin
.:floyd:.9-Jan-07 2:46
.:floyd:.9-Jan-07 2:46 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.