Equation Through InOrder Traversal

using System;

using System.Collections.Generic;

using System.Collections;

 

namespace ConsoleApplication1

{

    public class Node

    {

        private Node left;

        private Node right;

        private string value;

        public Node(Node left, Node right, string value)

        {

            this.left = left;

            this.right = right;

            this.value = value;

        }

        public Node getLeft()

        {

            return left;

        }

        public Node getRight()

        {

            return right;

        }

        public string getValue()

        {

            return value;

        }

    }

 

    class Program

    {

        public static string equation = "";

        static void Main(string[] args)

        {

            //Initializing the tree structure

            Node bottomFirst = new Node(null, null, "5");

            Node bottomSecond = new Node(null, null, "6");

            Node bottomThird = new Node(null, null, "/");

            Node middleFirst = new Node(null, null, "4");

            Node middleSecond = new Node(bottomFirst, bottomSecond, "-");

            Node middleThird = new Node(null, bottomThird, "8");

            Node middleFourth = new Node(null, null, "7");

            Node topFirst = new Node(middleFirst, middleSecond, "2");

            Node topSecond = new Node(middleThird, middleFourth, "3");

            Node root = new Node(topFirst, topSecond, "+");

            EquationThroughInOrderTraversal(root);

            Console.WriteLine("Expression: " + equation);

            //Extracting the post fix expression from the equation

            Stack oper = new Stack();

            ArrayList operand = new ArrayList();

            string tempStr = "";

            for (int i = 0; i < equation.Length; i++)

            {

                if (char.IsDigit((char)equation[i]))

                {

                    tempStr = tempStr + equation[i];

                }

                else

                {

                    operand.Add(tempStr);

                    tempStr = "";

                    if (oper.Count == 0)

                    {

                        oper.Push(equation[i]);

                    }

                    else

                    {

                        if (Precedence((char)oper.Peek(), (char)equation[i]) < 0)

                        {

                            oper.Push(equation[i]);

                        }

                        else

                        {

                            operand.Add(oper.Pop());

                            oper.Push(equation[i]);

                        }

                    }

                }

            }

            if (tempStr != "")

            {

                operand.Add(tempStr);

            }

            while (oper.Count != 0)

            {

                operand.Add(oper.Pop());

            }

            //Operand array contains the post fix expression

            for (int i = 0; i < operand.Count; i++)

            {

                if (operand[i].ToString().Contains(‘/’) || operand[i].ToString().Contains(‘*’) || operand[i].ToString().Contains(‘+’) || operand[i].ToString().Contains(‘-‘))

                {

                    int result = Operate(oper, (char)operand[i]);

                    oper.Push(result.ToString());

                }

                else

                {

                    oper.Push(operand[i]);

                }

            }

            Console.WriteLine("Expression Value = " + oper.Pop());

        }

        public static int Precedence(char ch1, char ch2)

        {

            string str = @"-+*/";

            int pos1 = -1;

            int pos2 = -1;

            for (int i = 0; i < str.Length; i++)

            {

                if ((char)str[i] == ch1)

                {

                    pos1 = i;

                }

                if ((char)str[i] == ch2)

                {

                    pos2 = i;

                }

                if (pos1 != -1 && pos2 != -1)

                {

                    return (pos1 – pos2);

                }

            }

            return -1;

        }

        public static void EquationThroughInOrderTraversal(Node root)

        {

            if (root == null)

            {

                return;

            }

            EquationThroughInOrderTraversal(root.getLeft());

            equation = equation + root.getValue();

            EquationThroughInOrderTraversal(root.getRight());

        }

        public static int Operate(Stack aStack, char ch)

        {

            int num1 = int.Parse((string)aStack.Pop());

            int num2 = int.Parse((string)aStack.Pop());

            int result = 0;

            switch (ch)

            {

                case ‘/’: result = num2 / num1;

                    break;

                case ‘*’: result = num2 * num1;

                    break;

                case ‘+’: result = num2 + num1;

                    break;

                case ‘-‘: result = num2 – num1;

                    break;

                default: break;

            }

            return result;

        }

    }

}

Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s