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
				);
		}
	}
}