Wednesday, March 9, 2016

CS 2420 - Assignment 5 - Part 3

I have not been able to make my Binary Search Tree self balancing. I know how the nodes should behave on paper, but I haven't been able to do it in code.

Yesterday after class, I figured out how to finish my Expression Tree and the Parser that takes the user's input.

Expression Tree:

using System;

namespace Assignment5
{
    class ExpressionTree
    {
        public TreeNode<string> root;
        public int node_count;

        public ExpressionTree()
        {
            root = null;
        }

        // TODO Finish Evaluate
        public void Evaluate()
        {

        }

        public string TraversePre(MyList<string> list, TreeNode<string> node)
        {
            list.Add(node.data);
            if (node.left != null)
                TraversePre(list, node.left);
            if (node.right != null)
                TraversePre(list, node.right);
            return string.Join(", ", list);
        }

        public string TraverseIn(MyList<string> list, TreeNode<string> node)
        {
            if (node.left != null)
                TraverseIn(list, node.left);
            list.Add(node.data);
            if (node.right != null)
                TraverseIn(list, node.right);
            return string.Join(", ", list);
        }

        public string TraversePost(MyList<string> list, TreeNode<string> node)
        {
            if (node.left != null)
                TraversePost(list, node.left);
            if (node.right != null)
                TraversePost(list, node.right);
            list.Add(node.data);
            return string.Join(", ", list);
        }
    }
}

Parser:

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

namespace Assignment5
{
    class ExpressionParser
    {
        private Stack<TreeNode<string>> numberStack, operatorStack;

        public ExpressionParser(ExpressionTree ETree, string input)
        {
            numberStack = new Stack<TreeNode<string>>();
            operatorStack = new Stack<TreeNode<string>>();

            ToArray(ETree, input);
        }

        public void ToArray(ExpressionTree ETree, string input)
        {
            string[] expressions = new string[input.Length];
            expressions = input.Split();

            BuildNodes(expressions, ETree);
        }

        private void BuildNodes(string[] expressions, ExpressionTree ETree)
        {
            foreach (string item in expressions)
            {
                int tempInt;
                if (Int32.TryParse(item, out tempInt))
                {
                    TreeNode<string> number_node = new TreeNode<string> { data = tempInt.ToString() };
                    numberStack.Push(number_node);
                }
                else                {
                    TreeNode<string> operator_node = new TreeNode<string> { data = item };
                    operatorStack.Push(operator_node);
                }
            }
            BuildTree(ETree);
        }

        private void BuildTree(ExpressionTree ETree)
        {
            ETree.node_count = numberStack.Count + operatorStack.Count;

            while (operatorStack.Count != 0)
            {
                TreeNode<string> tempRoot = operatorStack.Pop();
                tempRoot.right = numberStack.Pop();
                tempRoot.left = numberStack.Pop();
                numberStack.Push(tempRoot);
            }

            ETree.root = numberStack.Pop();
        }
    }
}

I will continue to work on this assignment. Thanks for reading!

No comments:

Post a Comment