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

namespace ExpressionParser
{
    public class ExpressionParser
    {
        private static Dictionary<string, int> precedence = new Dictionary<string, int>
        {
            ["("] = -1,
            ["+"] = 2,
            ["-"] = 2,
            ["*"] = 3,
            ["/"] = 3,
            ["^"] = 4,
        };
        public decimal Parse(string expression)
        {
            var tokens = Tokenize(expression);
            var postfixTokens = AsPostfix(tokens);

            return ReducePostfix(postfixTokens);
        }

        private decimal ReducePostfix(string[] postfixTokens)
        {
            var stack = new Stack<decimal>();
            foreach (var token in postfixTokens)
            {
                if (IsNumber(token))
                {
                    stack.Push(Decimal.Parse(token));
                }
                else
                {
                    var b = stack.Pop();
                    var a = stack.Pop();

                    stack.Push(Result(token, a, b));
                }
            }
            return stack.Pop();
        }

        private decimal Result(string token, decimal a, decimal b)
        {
            switch (token)
            {
                case "+":
                    return a + b;
                case "-":
                    return a - b;
                case "/":
                    return a / b;
                case "*":
                    return a * b;
                case "^":
                    return (decimal)Math.Pow((double)a, (double)b);
                default:
                    throw new SyntaxException();
            }
        }

        private string[] AsPostfix(string[] tokens)
        {
            var stack = new Stack<string>();
            var outputQueue = new Queue<string>();
            foreach (var token in tokens)
            {
                if(String.IsNullOrWhiteSpace(token))
                {
                    //do nothing
                }
                else if (IsNumber(token))
                {
                    outputQueue.Enqueue(token);
                }
                else if (IsOperator(token))
                {
                    while (stack.Any())
                    {
                        var tokenOperator = token;
                        var stackOperator = stack.Peek();

                        if ((IsLeftAssosiative(tokenOperator) && precedence[tokenOperator] == precedence[stackOperator]) ||
                            (precedence[tokenOperator] < precedence[stackOperator]))
                        {
                            outputQueue.Enqueue(stack.Pop());
                        }
                        else
                        {
                            break;
                        }
                    }
                    stack.Push(token);
                } else if(token.Equals("("))
                {
                    stack.Push(token);
                }
                else if(token.Equals(")"))
                {
                    while(stack.Any() && stack.Peek() != "(")
                    {
                        outputQueue.Enqueue(stack.Pop());
                    }
                    stack.Pop(); // Pop left parenthesis
                }
                else
                {
                    throw new SyntaxException();
                }


            }
            while (stack.Any())
            {
                outputQueue.Enqueue(stack.Pop());
            }
            return outputQueue.ToArray();
        }

        bool IsLeftAssosiative(string token)
        {
            return !token.Equals("^");
        }

        private bool IsOperator(string token)
        {
            return Regex.IsMatch(token, @"[+-/*]{1}");
        }

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

        private string[] specialChars = { "+", "-", "/", "*", "^", "(", ")" };
        private string[] Tokenize(string expression)
        {
            foreach(var specialChar in specialChars)
            {
                expression = expression.Replace(specialChar, " " + specialChar + " ");
            }

            return Regex.Split(expression, @"\s");
        }
    }
}