﻿namespace AlgoDS.Leetcode
{
    using System;
    using System.Collections.Generic;
    using System.Linq;

    /// <summary>
    /// [[Problem]]
    /// Implement a basic calculator to evaluate a simple expression string. The expression string contains only non-negative integers, +, -, *, / operators and empty spaces.The integer division should truncate toward zero.
    /// [[Example]]
    /// Input: "3+2*2"
    /// Output: 7
    /// Input: " 3+5 / 2 "
    /// Output: 5
    /// [[Note]]
    /// You may assume that the given expression is always valid.
    /// Do not use the eval built-in library function.
    /// </summary>
    public sealed class _227 : IOnlineProblem
    {
        /// <summary>
        /// [[Idea]]
        /// If the next operator is '+' or '-', then we can merge current result into final result;
        /// otherwise we keep computing current result with next availabe operand.
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public int SimpleCalculate(string s)
        {
            char op = '+';
            int pos = 0;
            int result = 0;
            int unmergedResult = 0;

            while (pos < s.Length)
            {
                pos = FindFirstNonSpace(s, pos);
                var temp = 0;
                while (pos < s.Length && char.IsDigit(s[pos]))
                {
                    temp = temp * 10 + (s[pos] - '0');
                    pos++;
                }

                switch (op)
                {
                    case '+': unmergedResult += temp; break;
                    case '-': unmergedResult -= temp; break;
                    case '*': unmergedResult *= temp; break;
                    case '/': unmergedResult /= temp; break;
                }

                pos = FindFirstNonSpace(s, pos);
                if (pos < s.Length)
                {
                    op = s[pos];
                    if (op == '+' || op == '-')
                    {
                        result += unmergedResult;
                        unmergedResult = 0;
                    }

                    pos++;
                }
            }

            return result + unmergedResult;
        }

        private int FindFirstNonSpace(string s, int start = 0)
        {
            int index = start;
            while (index < s.Length && char.IsWhiteSpace(s[index]))
            {
                index++;
            }

            return index;
        }

        public int Calculate(string s)
        {
            int index = 0;
            Stack<string> unCalculatedExpression = new Stack<string>();
            string number = string.Empty;
            bool needCompute = false;

            while (index < s.Length)
            {
                while (index < s.Length && char.IsWhiteSpace(s[index]))
                {
                    index++;
                }

                var start = index;
                while (index < s.Length && char.IsDigit(s[index]))
                {
                    index++;
                }

                if (needCompute)
                {
                    int current = int.Parse(s.Substring(start, index - start));
                    var op = unCalculatedExpression.Pop();
                    int previous = int.Parse(unCalculatedExpression.Pop());
                    switch (op)
                    {
                        case "/":
                            unCalculatedExpression.Push((previous / current).ToString());
                            break;
                        case "*":
                            unCalculatedExpression.Push((previous * current).ToString());
                            break;
                        default:
                            break;
                    }
                }
                else
                {
                    unCalculatedExpression.Push(s.Substring(start, index - start));
                }

                while (index < s.Length && char.IsWhiteSpace(s[index]))
                {
                    index++;
                }

                if (index < s.Length)
                {
                    var op = s[index];
                    unCalculatedExpression.Push(op.ToString());
                    if (op == '/' || op == '*')
                    {
                        needCompute = true;
                    }
                    else
                    {
                        needCompute = false;
                    }

                    index++;
                }
            }

            List<string> remaining = new List<string>(unCalculatedExpression.Reverse());
            int result = int.Parse(remaining[0]);
            index = 1;
            while (index < remaining.Count)
            {
                var op = remaining[index++];
                if (op == "+")
                {
                    result += int.Parse(remaining[index++]);
                }
                else
                {
                    result -= int.Parse(remaining[index++]);
                }
            }

            return result;
        }

        public void Solve()
        {
            Console.WriteLine(">>>3+2*2");
            Console.WriteLine(Calculate("3+2*2"));
            Console.WriteLine(SimpleCalculate("3+2*2"));

            Console.WriteLine(">>>3 + 2 * 2");
            Console.WriteLine(Calculate("3 + 2 * 2"));
            Console.WriteLine(SimpleCalculate("3 + 2 * 2"));

            Console.WriteLine(">>> 3 + 5 / 2 ");
            Console.WriteLine(Calculate(" 3 + 5 / 2 "));
            Console.WriteLine(SimpleCalculate(" 3 + 5 / 2 "));

            Console.WriteLine(">>> 5 - 2 * 3");
            Console.WriteLine(Calculate(" 5 - 2 * 3"));
            Console.WriteLine(SimpleCalculate(" 5 - 2 * 3"));

            Console.WriteLine(">>>1-1+1");
            Console.WriteLine(Calculate("1-1+1"));
            Console.WriteLine(SimpleCalculate("1-1+1"));
        }
    }
}
