math-suite/Source/GraphingCalculator/Expression/Expression.cs

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

namespace GraphingCalculator
{
    public class Expression
    {
        #region Token type
        public enum Token
        {
            None, Literal, Variable, Operator, Function, FunctionArgumentSeparator,
            LeftParanthesis, RightParanthesis
        };
        #endregion

        #region Variables, properties
        private string expressionString;
        private bool isProcessed = false;

        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>();

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

        public string ExpressionString
        {
            get { return expressionString; }
            set
            {
                expressionString = value;
                isProcessed = false;
            }
        }
        #endregion

        #region Other stuff
        public void AddVariable(string name, double value)
        {
            variables[name] = value;
        }

        #endregion

        #region Constructor
        public Expression()
        {
            Variables.Add("pi", Math.PI);
            Variables.Add("e", Math.E);
        }

        public Expression(string expr)
            : this()
        {
            expressionString = expr;
        }
        #endregion

        #region Processor
        private void Tokenize()
        {
            tokens.Clear();

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

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

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

                }

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

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

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

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

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

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

        private 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.Count > 0 && 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 void Process()
        {
            if (!isProcessed)
            {
                tokens.Clear();
                output.Clear();

                Tokenize();
                ShuntingYard();
            }
        }

        public double Evaluate()
        {
            Process();
            if (Output.Count == 0) return 0;

            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("Undefined variable '" + 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();
        }
        #endregion

        #region Helper routines

        private void EvaluateFunction(string func, ref Stack<double> stack)
        {
            switch (func)
            {
                case "sin": stack.Push(Math.Sin(stack.Pop())); break;
                case "sinh": stack.Push(Math.Sinh(stack.Pop())); break;
                case "cos": stack.Push(Math.Cos(stack.Pop())); break;
                case "cosh": stack.Push(Math.Cosh(stack.Pop())); break;
                case "tan": stack.Push(Math.Tan(stack.Pop())); break;
                case "tanh": stack.Push(Math.Tanh(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 "truncate":
                case "int": stack.Push(Math.Truncate(stack.Pop())); break;
                case "floor": stack.Push(Math.Floor(stack.Pop())); break;
                case "ceil":
                case "ceiling": stack.Push(Math.Ceiling(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 "root": stack.Push(Math.Pow(stack.Pop(), 1 / 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 "round": {
                        double dec = stack.Pop(), val = stack.Pop();
                        dec = Math.Max(0, dec);
                        dec = Math.Min(15, dec);

                        stack.Push(Math.Round(val, Convert.ToInt32(dec)));
                        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("Undefined function '" + func + "'.");
            }
        }

        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

    }
}