using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading;
using System.Globalization;

namespace ShuntingYardAlgorithm
{
    class ShuntingYardAlgorithm
    {
        private Stack<string> pendingTokens;
        private string[] inputTokens;
        private List<string> outputTokens;

        public List<string> Transform(string expression)
        {
            Initialize(expression);
            ProcessTokens();
            return outputTokens;
        }

        private void Initialize(string expression)
        {
            pendingTokens = new Stack<string>();
            inputTokens = new string[expression.Length];
            inputTokens = DevideExpressionIntoPieces(expression ?? "");
            outputTokens = new List<string>();
        }

        private string[] DevideExpressionIntoPieces(string expression)
        {
            string current = String.Empty;
            int inputIndex = 0;
            for (int i = 0; i < expression.Length; i++)
            {
                current = expression[i].ToString();
                if (IsTokenPartOfNumber(current, inputIndex))
                {
                    inputTokens[inputIndex - 1] += current;
                }
                else if (IsTokenPartOfFunctionName(current, inputIndex))
                {
                    inputTokens[inputIndex - 1] += current;
                }
                else
                {
                    if (current == " ")
                    {
                        continue;
                    }
                    inputTokens[inputIndex++] = current;
                }
            }
            return inputTokens;
        }

        private bool IsTokenPartOfFunctionName(string current, int inputIndex)
        {
            return inputIndex > 0 && IsFunctionName(current) && isPreviousTokenPartOfFunctionName(inputTokens[inputIndex - 1]);
        }

        private bool IsTokenPartOfNumber(string current, int inputIndex)
        {
            return inputIndex > 0 && isNumber(current) && isNumber(inputTokens[inputIndex - 1]);
        }

        private bool isPreviousTokenPartOfFunctionName(string token)
        {
            return Regex.IsMatch(token, @"([a-zA-Z])");
        }

        private bool isNumber(string token)
        {
            return Regex.IsMatch(token, @"([0-9.])");
        }

        private void ProcessTokens()
        {
            foreach (string current in inputTokens)
            {
                if (current == null)
                {
                    break;
                }
                if (current == String.Empty)
                {
                    continue;
                }
                if (isNumber(current))
                {
                    AppendToken(current);
                }
                else if ("(" == current)
                {
                    HandleOpenParantheses();
                }
                else if (")" == current)
                {
                    HandleCloseParantheses();
                }
                else if ("," == current)
                {
                    HandleParameterSeperator();
                }
                else
                {
                    HandleOperator(current);
                }
            }
            AppendAllPendingTokens();
        }

        private void HandleParameterSeperator()
        {
            while (!pendingTokens.Peek().Equals("("))
            {
                AppendPendingToken();
            }
        }

        private void HandleOpenParantheses()
        {
            pendingTokens.Push("(");
        }

        private void MoveLastOutputTokenToPendingTokens()
        {
            pendingTokens.Push(outputTokens[CalculateIndexOfLastOutputToken()]);
            outputTokens.RemoveAt(CalculateIndexOfLastOutputToken());
        }

        private int CalculateIndexOfLastOutputToken()
        {
            return outputTokens.Count - 1;
        }

        private bool LastOutputTokenIsFunctionName()
        {
            return outputTokens.Count > 0 && IsFunctionName(outputTokens[CalculateIndexOfLastOutputToken()]);
        }

        private bool IsFunctionName(string token)
        {
            bool result = isPreviousTokenPartOfFunctionName(token);
            if (token[token.Length - 1] == ')')
            {
                return false;
            }
            return result;
        }

        private void HandleCloseParantheses()
        {
            while (!pendingTokens.Peek().Equals("("))
            {
                AppendPendingToken();
            }
            pendingTokens.Pop();
            ConditionallyAddFunctionNameToPendingTokens();
        }

        private void ConditionallyAddFunctionNameToPendingTokens()
        {
            if (LastPendingTokenIsFunctionName())
            {
                AppendToken(pendingTokens.Pop());
            }
        }

        private bool LastPendingTokenIsFunctionName()
        {
            return pendingTokens.Count > 0 && IsFunctionName(pendingTokens.Peek());
        }

        private void HandleOperator(string current)
        {
            while (PendingTokenExecutesBefore(current))
            {
                AppendPendingToken();
            }
            pendingTokens.Push(current);
        }

        private void AppendAllPendingTokens()
        {
            while (ThereArePendingTokens())
            {
                AppendPendingToken();
            }
        }

        private void AppendPendingToken()
        {
            string current;
            if (ThereArePendingTokens())
            {
                current = pendingTokens.Pop();
                AppendToken(current);
            }
        }

        private bool PendingTokenExecutesBefore(string current)
        {
            if (ThereArePendingTokens())
            {
                int pendingPrecedence = CalculatePrecedence(pendingTokens.Peek());
                int currentPrecedence = CalculatePrecedence(current);
                return pendingPrecedence >= currentPrecedence;
            }
            return false;
        }

        private bool ThereArePendingTokens()
        {
            return pendingTokens.Count > 0;
        }

        private int CalculatePrecedence(string current)
        {
            switch (current)
            {
                case "*":
                case "/":
                    return 100;
                case "+":
                case "-":
                    return 10;
                case "pow":
                case "ln":
                case "sqrt":
                    return 1000;
                case "(":
                case ")":
                    return -1;
                default:
                    return 1;
            }
        }

        private void AppendToken(string token)
        {
            if (token.Length > 0)
            {
                outputTokens.Add(token);
            }
        }

        private double CalculateOutputTokens(ref List<string> output)
        {
            Stack<double> outputStack = new Stack<double>();
            string current;
            for (int indexCurrent = 0; indexCurrent < output.Count; indexCurrent++)
            {
                current = output[indexCurrent];
                if (isNumber(current))
                {
                    outputStack.Push(double.Parse(current));
                }
                else
                {
                    switch (current)
                    {
                        case "+":
                            outputStack.Push(outputStack.Pop() + outputStack.Pop());
                            break;
                        case "-":
                            if (outputStack.Count > 1)
                            {
                                outputStack.Push(outputStack.Pop() * (-1) + outputStack.Pop());
                            }
                            else
                            {
                                outputStack.Push(outputStack.Pop() * (-1));
                            }
                            break;
                        case "*":
                            outputStack.Push(outputStack.Pop() * outputStack.Pop());
                            break;
                        case "/":
                            double devider = outputStack.Pop();
                            outputStack.Push(outputStack.Pop() / devider);
                            break;
                        case "sqrt":
                            outputStack.Push(Math.Sqrt(outputStack.Pop()));
                            break;
                        case "pow":
                            double power = outputStack.Pop();
                            outputStack.Push(Math.Pow(outputStack.Pop(), power));
                            break;
                        case "ln":
                            outputStack.Push(Math.Log(outputStack.Pop()));
                            break;
                        default:
                            Console.WriteLine("Error.");
                            break;
                    }
                }
            }
            double result = outputStack.Pop();
            return result;
        }

        static void Main(string[] args)
        {
            Thread.CurrentThread.CurrentCulture =
            CultureInfo.GetCultureInfo("en-US");
            ShuntingYardAlgorithm tr = new ShuntingYardAlgorithm();
            string[] expressions = {

                                       "pow(2, 3.14) * (3 - (3 * sqrt(2) - 3.2) + 1.5*0.3)",
                                       "  (-3 +5.3)*  2.7-  ln(22)   /  pow( 5  +  3 ,    ln  (  10  )  )   ",
                                       "-(-15) - 10",
                                       "-(-15 - 10)",
                                       "ln(ln(ln(pow(10, sqrt(pow(1 + 2, (2 + 2*9)/10))))))",
                                    };
            foreach (var item in expressions)
            {
                tr.Transform(item);
                Console.WriteLine(tr.CalculateOutputTokens(ref tr.outputTokens));
            }
        }
    }
}