3
\$\begingroup\$

I successfully created an expression evaluator in C#, and I would like to know if it works well, and what I can do to improve it.

    class ExpressionEvaluator2
{
    public enum Token
    {
        None,
        Literal,
        Variable,
        Operator,
        Function,
        FunctionArgumentSeparator,
        LeftParanthesis,
        RightParanthesis
    };

    private List<KeyValuePair<Token, string>> tokens = new List<KeyValuePair<Token, string>> ();
    private List<KeyValuePair<Token, string>> output = new List<KeyValuePair<Token, string>> ();
    private Dictionary<string, double> variables = new Dictionary<string, double>();

    public List<KeyValuePair<Token, string>> Tokens { get { return tokens; } }
    public List<KeyValuePair<Token, string>> Output { get { return output; } }
    public Dictionary<string, double> Variables { get { return variables; } }

    public ExpressionEvaluator2()
    {
        Variables.Add("pi", Math.PI);
        Variables.Add("e", Math.E);
    }

    public string Expression { get; set; }

    public void Tokenize()
    {
        tokens.Clear();

        for (int i = 0; i < Expression.Length; i++)
        {
            if (char.IsWhiteSpace(Expression[i])) continue;

            if (IsOperator(Expression[i]))
            {
                // Unary minus
                if (Expression[i] == '-' && (tokens.Count == 0 || tokens.Last().Key == Token.LeftParanthesis || tokens.Last().Key == Token.Operator))
                    tokens.Add(new KeyValuePair<Token, string>(Token.Operator, "!-"));

                // Any other operator
                else tokens.Add(new KeyValuePair<Token, string>(Token.Operator, Expression[i].ToString()));

            }

            else if (Expression[i] == '(')
                tokens.Add(new KeyValuePair<Token, string>(Token.LeftParanthesis, Expression[i].ToString()));

            else if (Expression[i] == ')')
                tokens.Add(new KeyValuePair<Token, string>(Token.RightParanthesis, Expression[i].ToString()));

            else if (Expression[i] == ',')
                tokens.Add(new KeyValuePair<Token, string>(Token.FunctionArgumentSeparator, Expression[i].ToString()));

            else if (Char.IsDigit(Expression[i]))
                tokens.Add(new KeyValuePair<Token, string>(Token.Literal, GetLiteral(Expression, ref i)));

            else if (Char.IsLetter(Expression[i]))
            {
                if (IsFunction(Expression, i)) tokens.Add(new KeyValuePair<Token, string>(Token.Function, GetVariable(Expression, ref i)));
                else tokens.Add(new KeyValuePair<Token, string>(Token.Variable, GetVariable(Expression, ref i)));
            }

            else throw new Exception("Unrecognized character found!");
        }
    }

    public void ShuntingYard()
    {
        Stack<KeyValuePair<Token, string>> stack = new Stack<KeyValuePair<Token, string>>();

        foreach (var i in Tokens) switch (i.Key)
            {
                case Token.Variable:
                case Token.Literal: output.Add(i); break;

                case Token.Function: stack.Push(i); break;

                case Token.FunctionArgumentSeparator:

                    while (stack.Peek().Key != Token.LeftParanthesis) {
                        output.Add(stack.Pop());
                        if (stack.Count == 0) throw new Exception("Syntax error!");
                    }

                    break;

                case Token.Operator:

                    if (IsLeftAssociative(i.Value)) {
                        while (stack.Count != 0 && Precedence(i.Value) <= Precedence(stack.Peek().Value))
                            output.Add(stack.Pop());
                    }

                    else {
                        while (stack.Count != 0 && Precedence(i.Value) < Precedence(stack.Peek().Value))
                            output.Add(stack.Pop());
                    }

                    stack.Push(i);
                    break;

                case Token.LeftParanthesis: stack.Push(i); break;

                case Token.RightParanthesis:

                    while (stack.Peek().Key != Token.LeftParanthesis) {
                        output.Add(stack.Pop());
                        if (stack.Count == 0) throw new Exception("Mismatched parantheses!");
                    }

                    stack.Pop(); // Pop paranthesis
                    if (stack.Peek().Key == Token.Function) output.Add(stack.Pop());   // Pop function

                    break;
            }

        while (stack.Count > 0)
        {
            if (stack.Peek().Key == Token.LeftParanthesis) throw new Exception("Mismatched parantheses!");
            output.Add(stack.Pop());
        }
    }

    public double Evaluate()
    {
        Stack<double> stack = new Stack<double>();

        foreach (var i in Output)
            switch (i.Key)
            {
                case Token.Variable:
                    if (!Variables.ContainsKey(i.Value)) throw new Exception("Variable missing: " + i.Value);
                    stack.Push(Variables[i.Value]);
                    break;

                case Token.Literal: stack.Push(double.Parse(i.Value)); break;

                case Token.Operator:
                    switch (i.Value)
                    {
                        case "!-": stack.Push(stack.Pop() * -1); break;
                        case "+": stack.Push(stack.Pop() + stack.Pop()); break;
                        case "-": {
                                double b = stack.Pop();
                                double a = stack.Pop();
                                stack.Push(a - b);
                            } break;

                        case "*": stack.Push(stack.Pop() * stack.Pop()); break;
                        case "/": {
                                double b = stack.Pop();
                                double a = stack.Pop();
                                stack.Push(a / b);
                            } break;

                        case "%": {
                                double b = stack.Pop();
                                double a = stack.Pop();
                                stack.Push(a % b);
                            } break;

                        case "^": {
                                double b = stack.Pop();
                                double a = stack.Pop();
                                stack.Push(Math.Pow(a,b));
                            } break;
                    }

                    break;

                case Token.Function:
                    EvaluateFunction(i.Value, ref stack);
                    break;
            }

        return stack.Pop();
    }

    void EvaluateFunction(string func, ref Stack<double> stack)
    {
        switch (func)
        {
            case "sin": stack.Push(Math.Sin(stack.Pop())); break;
            case "cos": stack.Push(Math.Cos(stack.Pop())); break;
            case "tan": stack.Push(Math.Tan(stack.Pop())); break;
            case "ctan": stack.Push(1 / Math.Tan(stack.Pop())); break;

            case "arcsin": stack.Push(Math.Asin(stack.Pop())); break;
            case "asin": stack.Push(Math.Asin(stack.Pop())); break;
            case "arccos": stack.Push(Math.Acos(stack.Pop())); break;
            case "acos": stack.Push(Math.Acos(stack.Pop())); break;
            case "arctan": stack.Push(Math.Atan(stack.Pop())); break;
            case "atan": stack.Push(Math.Atan(stack.Pop())); break;

            case "int": stack.Push(Math.Truncate(stack.Pop())); break;
            case "abs": stack.Push(Math.Abs(stack.Pop())); break;
            case "max": stack.Push(Math.Max(stack.Pop(), stack.Pop())); break;
            case "min": stack.Push(Math.Min(stack.Pop(), stack.Pop())); break;
            case "sqrt": stack.Push(Math.Sqrt(stack.Pop())); break;
            case "cbrt": stack.Push(Math.Pow(stack.Pop(), 1.0 / 3.0)); break;

            case "lg": stack.Push(Math.Log10(stack.Pop())); break;
            case "log": stack.Push(Math.Log(stack.Pop(), stack.Pop())); break;
            case "ln": stack.Push(Math.Log(stack.Pop(), Math.E)); break;

            default: throw new Exception("Unknown function " + func);
        }
    }

    #region Helper routines
    private static bool IsLeftAssociative (string op)
    {
        return (op != "^");
    }

    private static int Precedence(string op)
    {
        switch (op)
        {
            case "+":
            case "-": return 1;

            case "*":
            case "/":
            case "%": return 2;

            case "^": return 3;

            case "!-": return 10;

            default: return 0;
        }
    }

    private static bool IsOperator(char c)
    {
        const string operators = "+-*/%^";
        return operators.Contains(c);
    }

    private static bool IsFunction(string s, int index)
    {
        // Skip function/variable name
        while (index < s.Length && char.IsLetterOrDigit(s[index])) index++;
        while (index < s.Length && char.IsWhiteSpace(s[index])) index++;

        // End of string? Than it's a variable
        if (index >= s.Length) return false;

        // If an operator, function separator, or ), variable
        if (s[index] == '(') return true;
        return false;
    }

    private static string GetVariable(string s, ref int index)
    {
        StringBuilder str = new StringBuilder();

        while (index < s.Length && (char.IsLetterOrDigit(s[index])))
            str.Append(s[index++]);

        index -= 1;
        return str.ToString();
    }

    private static string GetLiteral(string s, ref int index)
    {
        StringBuilder str = new StringBuilder();

        while (index < s.Length && (char.IsDigit(s[index]) || s[index] == '.'))
            str.Append (s[index++]);

        index -= 1;
        return str.ToString();
    }

    #endregion
}

To evaluate an expression, first the expression needs to be tokenized using the Tokenize method. After that, apply the ShuntingYard algorithm to prepare the expression. In the end, it can evaluate the expression (assuming you give values to all the input variables).

I didn't manage to test it very thoroughly, and I don't even know how to test for large expressions that I can't calculate in my head.

\$\endgroup\$
  • \$\begingroup\$ A very quick minor thing is I would put braces around your else if statements in the Tokenize method. \$\endgroup\$ – dreza Mar 19 '12 at 21:17
1
\$\begingroup\$

It is very inconvenient to force the client to call your methods in a very specific order. I would have a top level API that is easy to use. Have the API take care of all the grunt work for you. In the following example, take notice that I am using decimal instead of double. This will avoid precision errors that floating point numbers are prone to.

interface IEvaluator
{
    void AddValue(string key, decimal value);
    void RemoveValue(string key);
    decimal Evaluate(string input);
}

Just remember that you should hide things that are irrelevant to client code.

\$\endgroup\$
  • \$\begingroup\$ Thanks, I will do it differently instead. Evaluate() also does the work of the other two functions that need to be called, but only if the expression code was change. Otherwise, just perform the evaluation. This is because I intend to use this class to evaluate an expression many times, with the variable changed. \$\endgroup\$ – Tibi Mar 20 '12 at 14:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.