Formula and math expression parser algorithm

Question

I must write a program that able to parsing formula. It should work like this example below :

Input : 5x + 7 ^ sin(z) / 2T + 44
Output : Enter value for x , z , t
Input : 2 , 1 ,2
Output : the answer is : something

It should support (+ , * , - , ^ , % , SIN , COS)
I did read this page about Shunting-yard algorithm

And also I know how to convert Infix expression to postfix or prefix.
It is my algorithm :

1 - Give the expression.
2 - If parentheses are balance go to step 3 else show error go to step 1
3 - Find all variables apart from (SIN , COS)
4 - Give variables from input
5 - Replace variables
6 - Prefix the expression and calculate it
7 - Display result in output and close program

Is that right ? I want to implement it in C#
Please suggest me any note might be useful for me.

You could use ANTLR, see this [Q&A](http://stackoverflow.com/questions/4396080/antlr-3-3-c-tutorials). — Bart Kiers, Apr 22 '11 at 09:07
possible duplicate of [Best algorithm for evaluating a mathematical expression?](http://stackoverflow.com/questions/572796/best-algorithm-for-evaluating-a-mathematical-expression) — H H, Apr 22 '11 at 10:05

score 2 · Answer 1 · answered Apr 22 '11 at 13:44

If you decide to write this from scratch, your algorithm looks good. I'll provide a few of my thoughts.

You may want to move step 5 (replace variables) into step 6 (prefix the expression and calculate it). In other words, instead of just doing a textual find-and-replace for the variables, do it during the calculation whenever need to evaluate a variable. This could open up more possibilities later, possibly making it easier to graph your functions or have variables with values that depend on other variables. Your way should work for the simple case, though.

A possible implementation for the sin and cos functions, making it easier to define additional functions in the future, could be having a Dictionary<string, Func<double,double>>, something like:

private var functions = 
    new Dictionary<string, Func<double,double>>(StringComparer.OrdinalIgnoreCase)
    {
        { "sin", Math.Sin },
        { "cos", Math.Cos },
        { "sec", Secant }
    };

. . . 

// checking whether a token is a defined function or a variable
if (functions.ContainsKey(token))
{
    // determine the value of the argument to the function
    double inputValue = getArgument();
    double result = functions[token](inputValue);
    . . .
}

. . .

private static double Secant(double x)
{
    return 1.0 / Math.Cos(x);
}

Emmanuel · Answer 2 · 2011-04-22T12:19:13.950

I don't know how to do this in C#, but python has a very powerful syntax tree analyzer (the ast module) that could help you here, if you give your expressions as python expressions (this is not so hard, you just have to add the '*' multiplication signs :-) ).

First, define the good class that only redefines the visit_Name method (called for identifiers, for instance another one visit_Expr is called for expressions, visit_Num is called when a number is met, etc, here we only want identifiers).

>>> import ast
>>> class MyVisitor(ast.NodeVisitor):
    def __init__(self, *args, **kwargs):
        super(MyVisitor, self).__init__(*args, **kwargs)
        self.identifiers = []

    def generic_visit(self, node):
        ast.NodeVisitor.generic_visit(self, node)

    def visit_Name(self, node):
        # You can specify othe exceptions here than cos or sin
        if node.id not in ['cos', 'sin']:
            self.identifiers.append(node.id)

Then define a quick function that takes an expression to give you its identifiers:

>>> def visit(expression):
    node = ast.parse(expression)
    v = MyVisitor()
    v.visit(node)
    print v.identifiers

It looks ok:

>>> visit('x + 4 * sin(t)')
['x', 't']
>>> visit('5*x + 7 ^ sin(z) / 2*T + 44')
['x', 'z', 'T']

Use python 2.6 or 2.7 for the ast module.

Formula and math expression parser algorithm

2 Answers2