using System;
using System.Drawing;
using System.Collections;
using System.ComponentModel;
using System.Windows.Forms;
using System.Data;

namespace BinaryTree
{
	/// <summary>
	/// Summary description for Form1.
	/// </summary>
	
	public class Form1 : System.Windows.Forms.Form
	{
		private System.Windows.Forms.TreeView TableTree;
		private System.Windows.Forms.Label label2;
		private System.Windows.Forms.Label label1;
		private System.Windows.Forms.TextBox Output;
		private System.Windows.Forms.Label Test;
		private System.Windows.Forms.Button Solve;
		private System.Windows.Forms.TextBox Input;
		/// <summary>
		/// Required designer variable.
		/// </summary>
		private System.ComponentModel.Container components = null;

		public Form1()
		{
			//
			// Required for Windows Form Designer support
			//
			InitializeComponent();

			//
			// TODO: Add any constructor code after InitializeComponent call
			//
		}

		/// <summary>
		/// Clean up any resources being used.
		/// </summary>
		protected override void Dispose( bool disposing )
		{
			if( disposing )
			{
				if (components != null) 
				{
					components.Dispose();
				}
			}
			base.Dispose( disposing );
		}

		#region Windows Form Designer generated code
		/// <summary>
		/// Required method for Designer support - do not modify
		/// the contents of this method with the code editor.
		/// </summary>
		private void InitializeComponent() {
			this.Input = new System.Windows.Forms.TextBox();
			this.Solve = new System.Windows.Forms.Button();
			this.Test = new System.Windows.Forms.Label();
			this.Output = new System.Windows.Forms.TextBox();
			this.label1 = new System.Windows.Forms.Label();
			this.label2 = new System.Windows.Forms.Label();
			this.TableTree = new System.Windows.Forms.TreeView();
			this.SuspendLayout();
			// 
			// Input
			// 
			this.Input.Location = new System.Drawing.Point(8, 40);
			this.Input.Name = "Input";
			this.Input.Size = new System.Drawing.Size(136, 20);
			this.Input.TabIndex = 0;
			this.Input.Text = "";
			// 
			// Solve
			// 
			this.Solve.Location = new System.Drawing.Point(168, 40);
			this.Solve.Name = "Solve";
			this.Solve.Size = new System.Drawing.Size(72, 24);
			this.Solve.TabIndex = 5;
			this.Solve.Text = "Solve";
			this.Solve.Click += new System.EventHandler(this.Solve_Click);
			// 
			// Test
			// 
			this.Test.Location = new System.Drawing.Point(24, 200);
			this.Test.Name = "Test";
			this.Test.Size = new System.Drawing.Size(264, 96);
			this.Test.TabIndex = 6;
			// 
			// Output
			// 
			this.Output.Location = new System.Drawing.Point(8, 112);
			this.Output.Name = "Output";
			this.Output.Size = new System.Drawing.Size(72, 20);
			this.Output.TabIndex = 3;
			this.Output.Text = "";
			// 
			// label1
			// 
			this.label1.Location = new System.Drawing.Point(8, 8);
			this.label1.Name = "label1";
			this.label1.TabIndex = 1;
			this.label1.Text = "Math Equation";
			// 
			// label2
			// 
			this.label2.Location = new System.Drawing.Point(8, 88);
			this.label2.Name = "label2";
			this.label2.Size = new System.Drawing.Size(64, 16);
			this.label2.TabIndex = 4;
			this.label2.Text = "Answer";
			// 
			// TableTree
			// 
			this.TableTree.ImageIndex = -1;
			this.TableTree.Location = new System.Drawing.Point(336, 8);
			this.TableTree.Name = "TableTree";
			this.TableTree.SelectedImageIndex = -1;
			this.TableTree.Size = new System.Drawing.Size(240, 328);
			this.TableTree.TabIndex = 2;
			// 
			// Form1
			// 
			this.AutoScaleBaseSize = new System.Drawing.Size(5, 13);
			this.ClientSize = new System.Drawing.Size(584, 342);
			this.Controls.Add(this.Test);
			this.Controls.Add(this.Solve);
			this.Controls.Add(this.label2);
			this.Controls.Add(this.Output);
			this.Controls.Add(this.TableTree);
			this.Controls.Add(this.label1);
			this.Controls.Add(this.Input);
			this.Name = "Form1";
			this.Text = "BinaryTree";
			this.Load += new System.EventHandler(this.Form1_Load);
			this.ResumeLayout(false);
		}
		#endregion

		/// <summary>
		/// The main entry point for the application.
		/// </summary>
		[STAThread]
		static void Main() 
		{
			Application.Run(new Form1());
		}


		private void Solve_Click(object sender, System.EventArgs e)
		{
			Tree tree = new Tree();
			string[] token;
			int index = 0;
			string str = "";
			TreeNode first;
			TreeNode op;
			TreeNode second;
			token = Input.Text.Split(' ');
			for(int i = 0; i < token.Length; i++)
			{
				if(tree.Include(token[i], "^") || 
					tree.Include(token[i], "*") ||
					tree.Include(token[i], "/") ||
					tree.Include(token[i], "%"))
				{
					index = i;
					break;
				}
			}
			first = new TreeNode(token[index-1]);
			op = new TreeNode(token[index]);
			second = new TreeNode(token[index+1]);
			tree.InsertRoot(op,first,second);
			if(token.Length > 3 && (index != token.Length - 2))
			{
				int i = index + 2;
				while(i < token.Length)
				{
					op = new TreeNode(token[i]);
					second = new TreeNode(token[i+1]);
					tree.InsertNode(op,second);
					i += 2;
				}

			}
			str = token.ToString();
			if(tree.Nullstr(str, index-2))
			{
				for(int i = 0; i < index - 2; i++)
				{
					op = new TreeNode(token[i + 1]);
					second = new TreeNode(token[i]);
					tree.InsertNode(op,second);
					i += 1;
				}
			}
			tree.PostorderTraversal();

		}

		private void Form1_Load(object sender, System.EventArgs e)
		{
		
		}



	}
	// class TreeNode definition
	 public class TreeNode 
	{
		private TreeNode leftNode;   
		private string data;        
		private TreeNode rightNode;  
		// initialize data and make this a leaf node
		public TreeNode( string nodeData )
		{ 
			data = nodeData;              
			leftNode = rightNode = null;  // node has no children
		}
		public TreeNode()
		{

		}
      
		// LeftNode property
		public TreeNode LeftNode 
		{
			get 
			{
				return leftNode;
			}
         
			set
			{
				leftNode = value;
			}
		}
      
		// Data property
		public string Data
		{
			get 
			{
				return data;
			}

			set 
			{
				data = value;
			}
		}
      
		// RightNode property
		public TreeNode RightNode 
		{
			get 
			{
				return rightNode;
			}
         
			set
			{
				rightNode = value;
			}
		}

	}  // end class TreeNode

	// class Tree definition
	public class Tree 
	{
		private TreeNode root;
		public string[] order = {"+-", " */%", "^"};
		// construct an empty Tree of stringegers
		public Tree() 
		{ 
			root = null; 
		}

		public TreeNode Root
		{
			get
			{
				return root;
			}

		}

		// Insert a new node in the binary search tree.
		// If the root node is null, create the root node here.
		

		public void InsertNode(TreeNode op, TreeNode second)
		{
			lock ( this ) 
			{                          
				//if ( root == null )
				//	root = new TreeNode( insertValue );

				//else
					InsertHelper(ref root , op, second);
			}
		}





		public bool IsNumeric(string num)
		{
			try
			{
				int n = Int32.Parse(num);
			}
			catch(FormatException)
			{
				return false;
			}
			return true;
		}
		private void InsertHelper(ref TreeNode root, TreeNode op, TreeNode second)
		{
			if(IsNumeric(root.Data))
			{
				op.LeftNode = root;
				op.RightNode = second;
				root = op;
			}
			else if(Order(root.Data) < Order(op.Data))
			{
				TreeNode temproot = root.RightNode;
				InsertHelper(ref temproot, op, second);
			}
			else
			{
				op.LeftNode = root;
				op.RightNode = second;
				root = op;
			}
		}  // end method Insert
		public bool Include(string txt, string strchar)
		{
			for(int i = 0; i < txt.Length; i++)
			{
				if(strchar == txt[i].ToString())
				{
					return true;
				}
			}
			return false;
		}

		public int Order(string oper)
		{
			for(int i = 0; i < order.Length; i++)
			{
				if(Include(order[i], oper))
				{
					return i+1;
				}
			}
			return 0;
		}







		// begin preorder traversal
		public void PreorderTraversal()
		{ 
			lock ( this ) 
			{
				PreorderHelper( root ); 
			}
		}

		// recursive method to perform preorder traversal
		private void PreorderHelper( TreeNode node )
		{
			if ( node == null )
				return;

			// output node data
			MessageBox.Show( node.Data + " " );

			// traverse left subtree
			PreorderHelper( node.LeftNode );     

			// traverse right subtree
			PreorderHelper( node.RightNode );     
		}

		// begin inorder traversal
		public void InorderTraversal()
		{ 
			lock ( this ) 
			{
				InorderHelper( root ); 
			}
		}

		// recursive method to perform inorder traversal
		private void InorderHelper( TreeNode node )
		{
			if ( node == null )
				return;

			// traverse left subtree
			InorderHelper( node.LeftNode );

			// output node data
			MessageBox.Show( node.Data + " " );

			// traverse right subtree
			InorderHelper( node.RightNode );
		}

		// begin postorder traversal
		public void PostorderTraversal()
		{ 
			lock ( this ) 
			{
				PostorderHelper( root ); 
			}
		}

		// recursive method to perform postorder traversal
		private void PostorderHelper( TreeNode node )
		{
			if ( node == null )
				return;

			// traverse left subtree
			PostorderHelper( node.LeftNode );

			// traverse right subtree
			PostorderHelper( node.RightNode );

			// output node data
			MessageBox.Show( node.Data + " " );
		}
		public int Count()
		{
			lock (this)
			{
				return CountHelper( root );
			}
		}

		private int CountHelper( TreeNode node )
		{
			int count = 0;
			if ( node == null )
				return count;
			else
			{
				if(node.LeftNode != null)
					count += 1;
				if(node.RightNode != null)
					count += 1;
				CountHelper(node);
			}
			return count;

		}
		public bool Nullstr(string text, int index)
		{
			try
			{
				char str = text[index];
			}
			catch(IndexOutOfRangeException)
			{
				return true;
			}
			return true;
		}

		public void InsertRoot( TreeNode tree, TreeNode left, TreeNode right )
		{
			root = tree;
			root.RightNode = right;
			root.LeftNode = left;
		}
	}  // end class Tree
}

	
                        for(int i = 0; i < token.Length; i++)
			{
				if(tree.Include(token[i], "^") ||
					tree.Include(token[i], "*") ||
					tree.Include(token[i], "/") ||
					tree.Include(token[i], "%"))
				{
					index = i;
					break;
				}
			}