using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
using ExpressionComputer.Utility;
 
namespace ExpressionComputer
{   
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("6 == {0}\n", Exp.Compute ("1 + 2 * 3 - 4 + 5 * 6 / 2 - 2 * 3 ^ 2 + ( 5 - 2 ) * 2"));
 
 
            Console.WriteLine("19 == {0}\n", Exp.Compute("1 + 2 * 3 ^ 2"));
 
 
            Console.WriteLine("{0}\n", Exp.ConvertToRpnString("1 + 2 + 3 + 4 + 5"));
 
            string orig = "1 + 2 * 3 + 4";
            Console.WriteLine(orig);
            IList<string> rpn = Exp.ConvertToRpn(orig);
            Console.WriteLine(Exp.ConvertRpnToString(rpn));
            int n = Exp.ComputeRpn(rpn);
            Console.WriteLine("11 == {0}\n", n);
 
 
 
            string orig2 = "1 + 2 * ( 3 + 4 )";
            Console.WriteLine(orig2);
            IList<string> rpn2 = Exp.ConvertToRpn(orig2);
            Console.WriteLine("{0}", Exp.ConvertRpnToString(rpn2));
            Console.WriteLine("15 == {0}\n", Exp.ComputeRpn(rpn2));
 
 
            Console.WriteLine("23 == {0}", Exp.Compute("1 + 2 * 3 + 4 + 2 * 6"));
            Console.WriteLine("17 == {0}\n", Exp.Compute("1 + 2 * 3 + 4 + 2 * 6 / 2"));
 
 
            string orig3 = "1 + 2 * 3 + 4 + 2 * 6 / 2 - 1";
            Console.WriteLine ("{0}",orig3);
            string exp2 = Exp.ConvertToRpnString(orig3);
            Console.WriteLine(exp2);
            Console.WriteLine("16 == {0}", Exp.Compute(orig3));
 
             
             
 
 
 
 
            Console.ReadLine();
        }
    }
 
 
    public static class Exp
    {
 
        public static string ConvertRpnToString(IList<string> rpn)
        {
            return string.Join(" ", rpn.ToArray());
        }
 
        public static string ConvertToRpnString(string exp)
        {
            var rpn = Exp.ConvertToRpn(exp);
 
            return string.Join(" ", rpn.ToArray());
        }
 
        public static IList<string> ConvertToRpn(string exp)
        {
            IList<string> output = new List<string>();
            Stack<string> opStack = new Stack<string>();
 
            string[] tokens = exp.Split(' ');
 
            foreach (var token in tokens)
            {
                bool isOperator = token.IsOperator();
 
                if (token == "(" || token == ")")
                {
                    if (token == "(")
                    {
                        opStack.Push(token);
                    }
                    else if (token == ")")
                    {
                        string op = "";
                        while ((op = opStack.Pop()) != "(")
                        {
                            output.Add(op);
                        }
 
                    }
 
                }
                else if (!isOperator)
                {
                    output.Add(token);
                }
                else
                {
                    while (opStack.Count > 0 && 
                                (
                                    (token.IsLeftAssociative() && token.OperatorPrecedence() <= opStack.Peek().OperatorPrecedence())
                                    ||
                                    (token.OperatorPrecedence() < opStack.Peek().OperatorPrecedence())
                                )                       
                          )
                    {
                        output.Add(opStack.Pop());
                    }
                    opStack.Push(token);
                }
            }
 
            while (opStack.Count > 0)
                output.Add(opStack.Pop());
 
 
            return output;
        }
 
        public static int Compute(string expr)
        {
            return ComputeRpn(ConvertToRpn(expr));
        }
 
        public static int ComputeRpn(IList<string> rpn)
        {
            Stack<string> values = new Stack<string>();
 
            int n = 0;
            foreach (string token in rpn)
            {
                bool isOperator = token.IsOperator();
 
                if (isOperator)
                {
                    int opB = int.Parse(values.Pop());
                    int opA = int.Parse(values.Pop());
                    int result = 0;
                    switch (token)
                    {
                        case "*":
                            result = opA * opB;
                            break;
                        case "/":
                            result = opA / opB;
                            break;
                        case "+":
                            result = opA + opB;
                            break;
                        case "-":
                            result = opA - opB;
                            break;
                        case "^":
                            result = (int)Math.Pow((double)opA, (double)opB);
                            break;
                    }
                    values.Push(result.ToString());
                }
                else
                {
                    values.Push(token);
                }
            }
 
            return int.Parse(values.Pop());
        }
    }
 
}
 
namespace ExpressionComputer.Utility
{
    public static class Helper
    {
 
        public static int OperatorPrecedence(this string op)
        {
            switch (op)
            {
                case "^":
                    return 3;
                case "*":
                case "/":
                    return 2;
                case "+":
                case "-":
                    return 1;
            }
            return 0;
        }
 
        public static bool HasLowerOrEqualPrecedenceThan(this string opA, string opB)
        {
            return opA.OperatorPrecedence() <= opB.OperatorPrecedence();
        }
 
        public static bool IsOperator(this string token)
        {
            return new[] { "*", "/", "+", "-", "^" }.Contains(token);
        }
 
        public static bool IsRightAssociative(this string token)
        {
            return new[] { "^" }.Contains(token);
        }
 
        public static bool IsLeftAssociative(this string token)
        {
            return !token.IsRightAssociative();
        }
    }
 
 
}