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

namespace Interpreter
{
  	public class Program
	{
		public static void Main(string[] args)
		{
string program = @"
10 FOR X=0 TO 9
20 	FOR Y=0 TO 9
30		LET SUMY = SUMY + Y
40 	NEXT Y
50	LET SUMX = SUMX + X
60 NEXT X
70 PRINT SUMX
80 PRINT SUMY
";
            BasicInterpreter basicInterpreter = new BasicInterpreter();
            basicInterpreter.Execute(program);
            
            program = @"
10 FOR X=STARTFOR TO 9
20 	FOR Y=STARTFOR TO 9
30		LET SUMY = SUMY + Y
40 	NEXT Y
50	LET SUMX = SUMX + X
60 NEXT X
70 PRINT SUMX
80 PRINT SUMY
";
            basicInterpreter = new BasicInterpreter();
            basicInterpreter.Execute(program);

            basicInterpreter.Variables["STARTFOR"] = 1;
            basicInterpreter.Variables["SUMX"] = 0;
            basicInterpreter.Variables["SUMY"] = 0;
            basicInterpreter.Execute();

		}
	}

  
    public interface IExpression
    {
        List<string> Lines { get; }

        IExpression Construct(Context context);

        object Interpret(Context context);
    }

    public class BasicInterpreter
    {
        private Context _Context;

        public List<IExpression> ParserTree { get; private set; }

        public Dictionary<string, int> Variables => _Context.Variables;

        public void Execute(string program)
        {
            _Context = new Context(program);
            this.ParserTree = _Context.BuildParseTree();

            foreach (IExpression expression in this.ParserTree)
            {
                expression.Interpret(_Context);
            }
        }

        public void Execute()
        {
            foreach (IExpression expression in this.ParserTree)
            {
                expression.Interpret(_Context);
            }
        }
    }

    public class Context
    {
        private List<string> _Lines = new List<string>();
        private int _CurrentLineIndex = 0;
        private PostfixExpression _PostfixExpressionPrototype = new PostfixExpression();

        private List<IExpression> _Prototypes = new List<IExpression>
            {
                new ForExpression(),
                new NextExpression(),
                new LetExpression(),
                new PrintExpression()
            };

        public Context(string input)
        {
            Regex regexLine = new Regex(@"\d+\s+(.*)");
            foreach (string line in input.Split(new[] { "\r\n", "\r", "\n" }, StringSplitOptions.None))
            {
                Match match = regexLine.Match(line);
                if (match.Success)
                {
                    _Lines.Add(match.Groups[1].Value);
                }
            }
        }
        public Dictionary<string, int> Variables { get; set; } = new Dictionary<string, int>();
        public List<object> Parameters { get; } = new List<object>();

        public List<IExpression> BuildParseTree()
        {
            List<IExpression> expressions = new List<IExpression>();

            do
            {
                IExpression expression = this.ConstructExpression();

                if (expression != null)
                {
                    expressions.Add(expression);
                }

            } while (this.NextLine());


            return expressions;
        }

        public IExpression ConstructPostfix(string value)
        {
            this.Parameters.Clear();
            this.Parameters.Add(value);

            return _PostfixExpressionPrototype.Construct(this);
        }

        public IExpression ConstructExpression()
        {
            IExpression expression = null;

            foreach (IExpression expressionBase in this._Prototypes)
            {
                expression = expressionBase.Construct(this);

                if (expression != null)
                {
                    return expression;
                }
            }

            return expression;
        }

        public string CurrentLine
        {
            get
            {
                if (_CurrentLineIndex >= _Lines.Count)
                {
                    return null;
                }

                return _Lines[_CurrentLineIndex];
            }
        }

        public bool NextLine()
        {
            _CurrentLineIndex++;

            return (_CurrentLineIndex < _Lines.Count);
        }
    }

    public class ForExpression : IExpression
    {
        public List<string> Lines { get; } = new List<string>();

        public IExpression StartTokens { get; private set; }

        public IExpression EndTokens { get; private set; }

        public string VariableCounter { get; private set; }

        public List<IExpression> MyExpressions { get; } = new List<IExpression>();

        public IExpression Construct(Context context)
        {
            Regex re = new Regex(@"FOR\s+([a-z]+)\s*=\s*([^\s]+)\s+TO\s+([^\s]+)", RegexOptions.IgnoreCase);
            Match match = re.Match(context.CurrentLine);

            if (!match.Success)
            {
                return null;
            }

            ForExpression forExpression = new ForExpression();
            forExpression.Lines.Add(context.CurrentLine);

            forExpression.VariableCounter = match.Groups[1].Value;
            forExpression.StartTokens = context.ConstructPostfix(match.Groups[2].Value);
            forExpression.EndTokens = context.ConstructPostfix(match.Groups[3].Value);

            context.NextLine();
            bool isRepeat = true;
            do
            {
                forExpression.Lines.Add(context.CurrentLine);
                IExpression expression = context.ConstructExpression();

                if (expression != null)
                {
                    NextExpression nextExpression = expression as NextExpression;
                    isRepeat = !(nextExpression?.NextVariable == forExpression.VariableCounter);

                    if (isRepeat)
                    {
                        forExpression.MyExpressions.Add(expression);
                        context.NextLine();
                    }
                }
            } while (isRepeat);


            return forExpression;
        }

        public object Interpret(Context context)
        {
            int start = (int)this.StartTokens.Interpret(context);
            int stop = (int)this.EndTokens.Interpret(context);

            int len = stop - start;

            for (int i = start; i <= len; i++)
            {
                context.Variables[this.VariableCounter] = i;

                foreach (IExpression item in this.MyExpressions)
                {
                    item.Interpret(context);
                }
            }

            return null;
        }
    }

    public class NextExpression : IExpression
    {
        public List<string> Lines { get; } = new List<string>();

        public string NextVariable { get; private set; }

        public IExpression Construct(Context context)
        {
            Regex re = new Regex(@"NEXT\s+(\w+)");
            Match match = re.Match(context.CurrentLine);

            if (!match.Success)
            {
                return null;
            }

            NextExpression nextExpression = new NextExpression() { NextVariable = match.Groups[1].Value };
            return nextExpression;
        }

        public object Interpret(Context context)
        {
            return null;
        }
    }

    public class PostfixExpression : IExpression
    {
        public List<string> MyPostfixTokens { get; private set; } = new List<string>();
        public List<string> Lines { get; } = new List<string>();
        private bool IsAlpha(string c) => Regex.IsMatch(c, "^[a-z]+$", RegexOptions.IgnoreCase);
        private bool IsDigit(string c) => Regex.IsMatch(c, @"^-?\d+$");

        private int GetPriority(string c)
        {
            if (c == "-" || c == "+")
                return 1;
            else if (c == "*" || c == "/")
                return 2;

            return 0;
        }

        public IExpression Construct(Context context)
        {
            string param1 = (string)context.Parameters[0];

            PostfixExpression postfixExpression = new PostfixExpression();
            postfixExpression.Lines.Add(param1);
            postfixExpression.MyPostfixTokens = InfixToPostfix(param1);

            return postfixExpression;
        }

        public object Interpret(Context context)
        {
            Stack<int> numericValues = new Stack<int>();
            foreach (string token in this.MyPostfixTokens)
            {
                if (IsAlpha(token))
                {
                    if (!context.Variables.TryGetValue(token, out int value))
                    {
                        value = 0;
                    }

                    numericValues.Push(value);
                }
                else if (IsDigit(token))
                {
                    numericValues.Push(int.Parse(token));
                }
                else
                {
                    int result = ComputeList(token, numericValues.Pop(), numericValues.Pop());

                    numericValues.Push(result);
                }
            }

            return numericValues.Pop();
        }

        private List<string> InfixToPostfix(string infixString)
        {
            infixString = Regex.Replace(infixString, @"(\d+)", "$1|");
            infixString = Regex.Replace(infixString, @"([a-z]+)", "$1|", RegexOptions.IgnoreCase);
            infixString = Regex.Replace(infixString, @"([+\-*/\(\)])", "$1|");

            List<string> infix = infixString.Split('|').Where(x => !string.IsNullOrEmpty(x)).Select(x => x.Trim()).ToList();

            int l = infix.Count;
            Stack<string> tokenStack = new Stack<string>();
            List<string> output = new List<string>();

            foreach (string token in infix)
            {
                if (IsAlpha(token) || IsDigit(token))
                {
                    output.Add(token);
                }
                else if (token == "(")
                {
                    tokenStack.Push("(");
                }
                else if (token == ")")
                {
                    while (tokenStack.Count != 0 && tokenStack.Peek() != "(")
                    {
                        output.Add(tokenStack.Pop());
                    }

                    if (tokenStack.Count != 0 && tokenStack.Peek() != "(")
                    {
                        throw new InvalidOperationException("Invalid expression");
                    }
                    else
                    {
                        tokenStack.Pop();
                    }
                }
                else
                {
                    while (tokenStack.Count != 0 && GetPriority(token) <= GetPriority(tokenStack.Peek()))
                    {
                        output.Add(tokenStack.Pop());
                    }

                    tokenStack.Push(token);
                }
            }

            while (tokenStack.Count != 0)
            {
                output.Add(tokenStack.Pop());
            }

            return output;
        }

        private int ComputeList(string token, int value2, int value1)
        {
            int result = 0;
            switch (token)
            {
                case "+":
                    result = value1 + value2;
                    break;
                case "-":
                    result = value1 - value2;
                    break;
                case "*":
                    result = value1 * value2;
                    break;
                case "/":
                    result = value1 / value2;
                    break;
            }

            return result;
        }
    }

    public class LetExpression : IExpression
    {
        public List<string> Lines { get; } = new List<string>();

        public string Variable { get; private set; }
        public IExpression LetTokens { get; private set; }

        public IExpression Construct(Context context)
        {
            Regex re = new Regex(@"LET\s+(\w+)\s*=(.*)");
            Match match = re.Match(context.CurrentLine);

            if (!match.Success)
            {
                return null;
            }

            LetExpression letExpression = new LetExpression();

            letExpression.Variable = match.Groups[1].Value;
            letExpression.LetTokens = context.ConstructPostfix(match.Groups[2].Value);

            return letExpression;
        }

        public object Interpret(Context context)
        {
            int value = (int)this.LetTokens.Interpret(context);
            context.Variables[Variable] = value;

            return null;
        }
    }

    public class PrintExpression : IExpression
    {
        public List<string> Lines { get; } = new List<string>();

        public IExpression PrintTokens { get; private set; }

        public IExpression Construct(Context context)
        {
            Regex re = new Regex(@"PRINT\s+(\w+)");
            Match match = re.Match(context.CurrentLine);

            if (!match.Success)
            {
                return null;
            }

            PrintExpression printExpression = new PrintExpression() { PrintTokens = context.ConstructPostfix(match.Groups[1].Value) };
            return printExpression;
        }


        public object Interpret(Context context)
        {
            int value = (int)this.PrintTokens.Interpret(context);
            Console.WriteLine(value);

            return null;
        }
    }
}