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

namespace TestEvaluator
{
    public class Evaluator
    {
        private Dictionary<string, string> _variables = null;

        #region Constructors
        public Evaluator()
        {
        }

        public Evaluator(Dictionary<string, string> vars)
        {
            _variables = vars;
        }
        #endregion

        #region Destructors
        ~Evaluator()
        {
            _variables = null;
        }
        #endregion

        public string Evaluate(string expr)
        {
            return RpnEvaluate(InfixToRpn(expr));
        }

        public static string Evaluate(string expr, Dictionary<string, string> vars)
        {
            return new Evaluator(vars).Evaluate(expr);
        }

        #region Methods: RPN (Evaluate/Infix To RPN)
        private string RpnEvaluate(string rpnExpr)
        {
            StringBuilder digit = new StringBuilder();
            Stack<string> opStack = new Stack<string>();            
            bool skipSpaces = true;

            for (int i = 0; i < rpnExpr.Length; ++i)
            {
                char c = rpnExpr[i];

                if (c == '\'' || c == '\"')
                    skipSpaces = !skipSpaces;

                if (skipSpaces && IsSpace(c))
                {
                    if (digit.Length > 0)
                    {
                        opStack.Push(digit.ToString());
                        digit = new StringBuilder();
                    }
                }
                else if (IsOperator(c))
                {
                    if (digit.Length > 0)
                    {
                        opStack.Push(digit.ToString());
                        digit = new StringBuilder();
                    }

                    if (opStack.Count > 1)
                    {
                        string opRight = opStack.Pop();
                        string opLeft = opStack.Pop();

                        opStack.Push(ExprBinaryEvaluate(opLeft, c, opRight));
                    }
                    else
                    {
                        string operand = opStack.Pop();
                        opStack.Push(ExprUnaryEvaluate(c, operand));
                    }
                }
                else
                {
                    digit.Append(c);
                }
            }

            return (opStack.Count > 0 ? opStack.Pop() : rpnExpr);
        }

        private string InfixToRpn(string expr)
        {
            StringBuilder rpnExpr = new StringBuilder();
            Stack<char> opStack = new Stack<char>();
            char? operatorSymbol = null;
            bool skipSpaces = true;            

            for (int i = 0; i < expr.Length; ++i)
            {
                char c = expr[i];

                if (skipSpaces && IsSpace(c))
                    continue;

                if (c == '\'' || c == '\"')
                    skipSpaces = !skipSpaces;

                if (IsOperator(c))
                {
                    if (operatorSymbol.HasValue)
                        continue;

                    operatorSymbol = c;
                    rpnExpr.Append(' ');
                }
                else
                {
                    if (operatorSymbol.HasValue)
                    {
                        while (opStack.Count > 0 && RpnReduce(opStack.Peek(), operatorSymbol.Value))
                            rpnExpr.Append(opStack.Pop());

                        opStack.Push(operatorSymbol.Value);
                        operatorSymbol = null;
                    }

                    rpnExpr.Append(c);
                }
            }

            while (opStack.Count > 0)
                rpnExpr.Append(opStack.Pop());

            return (rpnExpr.ToString());
        }

        private bool RpnReduce(char op1, char op2)
        {
            string[] operatorPrecedence = new string[] { "-+&|^", "<>", "*/%" };
            int p1 = 0, p2 = 0;

            for (int i = 0; i < operatorPrecedence.Length; ++i)
            {
                if (operatorPrecedence[i].Contains(op1.ToString()))
                    p1 = i;
                if (operatorPrecedence[i].Contains(op2.ToString()))
                    p2 = i;
            }

            return (p1 >= p2);
        }
        #endregion

        #region Methods: Utils
        private bool IsSpace(char c)
        {
            const string spaces = " \t\r\n";
            return (spaces.Contains(c.ToString()));
        }

        private bool IsOperator(char c)
        {
            string operators = "<>+-&|^*/%";
            return operators.Contains(c.ToString());
        }

        private bool IsNumeric(string str)
        {
            for (int i = 0; i < str.Length; ++i)
            {
                char c = str[i];
                if (!((c >= '0' && c <= '9') || c == '.' || c == '-'))
                    return (false);
            }
            return(true);
        }

        private bool IsString(string str)
        {
            return (str[0] == '"' || str[0] == '\'');
        }

        private bool IsVariable(string operand)
        {
            return (!IsString(operand) && !IsNumeric(operand));
        }
        #endregion

        #region Methods: Evaluate Unary/Binary Expression
        private string ExprUnaryEvaluate(char operatorSymbol, string operand)
        {
            if (IsVariable(operand)) operand = _variables[operand];

            if (operatorSymbol != '-' || IsString(operand))
                throw new InvalidOperationException();

            return (-1 * double.Parse(operand)).ToString("g");            
        }

        private string ExprBinaryEvaluate(string opLeft, char operatorSymbol, string opRight)
        {
            if (IsVariable(opRight)) opRight = _variables[opRight];
            if (IsVariable(opLeft)) opLeft = _variables[opLeft];            

            bool rightIsNumeric = IsNumeric(opRight);
            bool leftIsNumeric = IsNumeric(opLeft);

            if (leftIsNumeric && rightIsNumeric)
                return EvaluateNumericExpr(double.Parse(opLeft), operatorSymbol, double.Parse(opRight));

            if (leftIsNumeric && !rightIsNumeric) 
                return EvaluateStringNumberExpr(opRight, operatorSymbol, double.Parse(opLeft));                

            if (!leftIsNumeric && rightIsNumeric) 
                return EvaluateStringNumberExpr(opLeft, operatorSymbol, double.Parse(opRight));                

            return EvaluateStringExpr(opLeft, operatorSymbol, opRight);
        }
        #endregion

        #region Methods: Evaluate Expressions
        private string EvaluateNumericExpr(double opLeft, char operatorSymbol, double opRight)
        {
            switch (operatorSymbol)
            {
                case '+': return (opLeft + opRight).ToString("g");
                case '-': return (opLeft - opRight).ToString("g");

                case '*': return (opLeft * opRight).ToString("g");
                case '/': return (opLeft / opRight).ToString("g");
                case '%': return (opLeft % opRight).ToString("g");

                case '&': return ((long)opLeft & (long)opRight).ToString("g");
                case '|': return ((long)opLeft | (long)opRight).ToString("g");
                case '^': return ((long)opLeft ^ (long)opRight).ToString("g");

                case '<': return ((long)opLeft << (int)opRight).ToString("g");
                case '>': return ((long)opLeft >> (int)opRight).ToString("g");

                default:
                    throw new InvalidOperationException();
            }
        }

        private string EvaluateStringExpr(string opLeft, char operatorSymbol, string opRight)
        {
            switch (operatorSymbol)
            {
                case '+':
                    return String.Format("'{0}{1}'", opLeft.Substring(1, opLeft.Length - 2), opRight.Substring(1, opRight.Length - 2));
                default:
                    throw new InvalidOperationException();
            }
        }

        private string EvaluateStringNumberExpr(string opLeft, char operatorSymbol, double opRight)
        {
            switch (operatorSymbol)
            {
                case '*':
                    StringBuilder result = new StringBuilder();
                    result.Append("'");
                    while (opRight-- > 0)
                        result.Append(opLeft.Substring(1, opLeft.Length - 2));
                    result.Append("'");
                    return result.ToString();
                default:
                    throw new InvalidOperationException();
            }
        }
        #endregion
    }

    public class Operation
    {
        private List<Operation> _opList = null;
        private StringBuilder _op = null;

        public Operation()
        {
            _opList = new List<Operation>();
            _op = new StringBuilder();
        }

        ~Operation()
        {
            _opList = null;
            _op = null;
        }

        public void Add(char chr)
        {
            _op.Append(chr);
        }

        public void AddOperation(Operation operation)
        {
            _op.AppendFormat("({0})", _opList.Count);
            _opList.Add(operation);
        }

        public string Evaluate()
        {
            StringBuilder evalOp = new StringBuilder(_op.ToString());
            for (int i=0; i < _opList.Count; ++i) 
                evalOp = evalOp.Replace(String.Format("({0})", i), _opList[i].Evaluate());

            return new Evaluator().Evaluate(evalOp.ToString());
        }

        public string Evaluate(Dictionary<string, string> vars)
        {
            StringBuilder evalOp = new StringBuilder(_op.ToString());
            for (int i = 0; i < _opList.Count; ++i)
                evalOp = evalOp.Replace(String.Format("({0})", i), _opList[i].Evaluate(vars));

            return Evaluator.Evaluate(evalOp.ToString(), vars);
        }
    }

    public class MyTokener
    {
        public Operation Parser(string text)
        {
            Stack<Operation> opStack = new Stack<Operation>();
            Operation opList = new Operation();
            opStack.Push(opList);
            for (int i = 0; i < text.Length; ++i)
            {
                switch (text[i])
                {
                    case '(':
                        if (opStack.Count > 0)
                        {
                            Operation op = new Operation();

                            Operation lastOp = opStack.Peek();
                            lastOp.AddOperation(op);
                            opStack.Push(op);
                        }
                        break;
                    case ')':
                        opStack.Pop();
                        break;
                    default:
                        if (opStack.Count > 0)
                        {
                            Operation op = opStack.Peek();
                            op.Add(text[i]);
                        }
                        break;
                }
            }

            return opList;
        }

        public static void Test()
        {
            Dictionary<string, string> vars = new Dictionary<string, string>();
            vars.Add("A", "1");
            vars.Add("B", "1");
            vars.Add("C", "1");
            vars.Add("D", "1");
            vars.Add("K", "1");
            vars.Add("L", "1");

            List<string> exprList = new List<string>();
            exprList.Add("(A + B) + C + (D * (K + (L - 1)))");
            exprList.Add("10 + 5 - (2 + (3 * 4) + (5 * 3)) - 4 ^ 2 << 8");
            exprList.Add("4 ^ 2 << 8");
            exprList.Add("'Hello' * 3");
            exprList.Add("'Hello' + ' ' * 3 + \"World\"");

            foreach (string expr in exprList)
            {
                Operation operation = new MyTokener().Parser(expr);
                Console.WriteLine("[{0}] = {1}", expr, operation.Evaluate(vars));
            }
        }

		public static void Main(string[] args) {
			MyTokener.Test();
		}
    }
}