ArithmeticParserToTree

using System;
using System.Collections.Generic;
using System.Linq;

namespace ArithmeticExpressionsTree
{
    public struct Operation
    {
        public Operation(String symbol, Int32 priority, Boolean isLeftAssociative,
            Func<Double, Double, Double> calculationMethod)
        {
            Symbol = symbol;
            Priority = priority;
            IsLeftAssociative = isLeftAssociative;
            CalculationMethod = calculationMethod;
        }

        public readonly String Symbol;
        public readonly Int32 Priority;
        public readonly Boolean IsLeftAssociative;
        public readonly Func<Double, Double, Double> CalculationMethod;
    }

    internal static class Program
    {
        public static ArithmeticExpressionTree ParseExpression(String[] tokens)
        {
            var leveledTokens = new List<LeveledToken>();

            Int32 currentLevel = 0;
            foreach (String token in tokens)
            {
                if (IsOpeningBrace(token))
                    currentLevel++;
                else if (IsClosingBrace(token))
                    currentLevel--;
                else
                    leveledTokens.Add(new LeveledToken(token, currentLevel));
            }

            return ParseRecursvely(leveledTokens);
        }

        private struct LeveledToken
        {
            public LeveledToken(String token, Int32 level)
            {
                Token = token;
                Level = level;
            }

            public readonly String Token;
            public readonly Int32 Level;
        }

        private static ArithmeticExpressionTree ParseRecursvely(List<LeveledToken> leveledTokens,
            ArithmeticExpressionTree tree = null, Int32 parentNodeIndex = 0)
        {
            List<LeveledToken> operationsTokens = leveledTokens.FindAll(t => IsOperation(t.Token));
            if (operationsTokens.Count == 0)
            {
                if (tree == null)
                    return new ArithmeticExpressionTree(leveledTokens[0].Token);
                else
                {
                    tree.AddNode(parentNodeIndex, leveledTokens[0].Token);
                    return tree;
                }
            }

            Int32 lowestNestingLevel = operationsTokens.Min(t => t.Level);
            Int32 lowestPriority =
                operationsTokens.FindAll(t => t.Level == lowestNestingLevel).Min(t => ArithmeticFunctions[t.Token].Priority);

            Int32 firstSuitableOperationIndex =
                leveledTokens.FindIndex(
                    t =>
                        (t.Level == lowestNestingLevel) && ArithmeticFunctions.ContainsKey(t.Token) &&
                        (ArithmeticFunctions[t.Token].Priority == lowestPriority));

            List<LeveledToken> leftTokens = leveledTokens.GetRange(0, firstSuitableOperationIndex);
            List<LeveledToken> rightTokens = leveledTokens.GetRange(firstSuitableOperationIndex + 1,
                leveledTokens.Count - firstSuitableOperationIndex - 1);

            Int32 newNodeIndex = 0;
            if (tree == null)
                tree = new ArithmeticExpressionTree(leveledTokens[firstSuitableOperationIndex].Token);
            else
                newNodeIndex = tree.AddNode(parentNodeIndex, leveledTokens[firstSuitableOperationIndex].Token);

            ParseRecursvely(leftTokens, tree, newNodeIndex);
            ParseRecursvely(rightTokens, tree, newNodeIndex);

            return tree;
        }

        private static readonly Dictionary<String, Operation> ArithmeticFunctions = new Dictionary<String, Operation>
        {
            {"+", new Operation("+", 0, true, (a, b) => a + b)},
            {"-", new Operation("-", 0, true, (a, b) => a - b)},
            {"*", new Operation("*", 1, true, (a, b) => a*b)},
            {"/", new Operation("/", 1, true, (a, b) => a/b)},
            {"^", new Operation("^", 2, false, Math.Pow)}
        };

        public static void PrintTree(ArithmeticExpressionTree tree, Int32 nodeIndex, Int32 level = 1)
        {
            if (level == 1)
                Console.WriteLine(tree.Root.Value);

            foreach (Int32 childrenIndex in tree.GetAllChildrenIndexes(nodeIndex))
            {
                Console.WriteLine(new String('  ', level) + tree.GetNode(childrenIndex).Value);
                PrintTree(tree, childrenIndex, level + 1);
            }
        }

        private static Boolean IsOperation(String lexem)
        {
            return ArithmeticFunctions.ContainsKey(lexem);
        }

        private static Boolean IsOpeningBrace(String lexem)
        {
            return (lexem == "(");
        }

        private static Boolean IsClosingBrace(String lexem)
        {
            return lexem == ")";
        }

        private static void Main(String[] args)
        {
            PrintTree(
                ParseExpression(args[0].Split(' ')),
                0
                );
        }
    }
}