Binary Expression Tree

[Cody Biggs]

So, I am trying to finish up this last part of the binary tree and I just cant seem to get it. According to the instructor theres something wrong in my right parentheses case. Here is the algorithm for the right paren I was following.
The output for pre, post and in I get "-" when my expression is ((3 * (8 - 2)) - (1 + 9))"


Case RPAREN:

if (stack is not empty)  
assign current node to child                        
pop stack and assign to currentNode                        
if (currentNode.Left is null)                            
assign child to currentNode.Left                        
else if currentNode.Right is null                            
assign child to right node                        
else                            
unexpected – generate error                        
end if                    
end if                
end case

Here is my right paren code

    case ')':
                        if (nodeStack.Count > 0)
                        {
                            currentNode = child;
                            currentNode = nodeStack.Pop();
                            if (currentNode.left == null)
                            {
                                child = currentNode.left;
                            }//end if
                            else if (currentNode.right == null)
                            {
                                child = currentNode.right;
                            }//end else if
                            else
                            {
                                Console.WriteLine("Something went wrong!!!");
                            }// end else
                        }
                        break;

and the whole class just to show

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

namespace BiggsProgram5
{
    class BinaryExpressionTree
    {
        public int Count { get; set; }
        public BinaryNode<char> RootNode;
        public string Expression { get; private set; }

        public BinaryExpressionTree(String expression)
        {
            this.Expression = expression;
            // get rid of the pesky spaces
            Console.WriteLine(expression);
            Queue<char> expr = new Queue<char>(expression.ToCharArray());
            RootNode = Parse(expr);
        }

        public BinaryNode<char> Parse(Queue<char> expressionQueue)
        {
            Stack<BinaryNode<char>> nodeStack = new Stack<BinaryNode<char>>();

            BinaryNode<char> currentNode = null;
            BinaryNode<char> child = null;
            char nextChar;
            

            while(expressionQueue.Count > 0)
            {
                nextChar = expressionQueue.Dequeue();

                switch (nextChar)
                {
                    case '(' :
                        if(currentNode != null)
                        {
                            nodeStack.Push(currentNode);
                        }
                        currentNode = new BinaryNode<char>();
                        break;

                    case ')':
                        if (nodeStack.Count > 0)
                        {
                            child = currentNode;
                            currentNode = nodeStack.Pop();
                            if (currentNode.left == null)
                            {
                                child = currentNode.left;
                            }//end if
                            else if (currentNode.right == null)
                            {
                                child = currentNode.right;
                            }//end else if
                            else
                            {
                                Console.WriteLine("Something went wrong!!!");
                            }// end else
                        }
                        break;

                    case '+':
                    case '-':
                    case '*':
                    case '/':
                    case '^':
                        currentNode.item = nextChar;
                        break;

                    case '1':
                    case '2':
                    case '3':
                    case '4':
                    case '5':
                    case '6':
                    case '7':
                    case '8':
                    case '9':
                    case '0':
                        BinaryNode<char> bin = new BinaryNode<char>();
                        bin.item = nextChar;
                        if(currentNode.left == null)
                        {
                            bin = currentNode.left;
                        }
                        else if( currentNode.right == null)
                        {
                            bin = currentNode.right;
                        }
                        else
                        {
                            Console.WriteLine("Something went wrong!!!");
                        }
                        break;
                }//end switch
            }//end while
            RootNode = currentNode;
            return RootNode;
        }

        public void DisplayPreOrder()
        {
            if (RootNode != null)
            {
                DisplayPreOrder(RootNode);
                Console.WriteLine();
            }
            else
            {
                Console.WriteLine("Tree is empty.");
            }
        }
        public void DisplayPreOrder(BinaryNode<char> node)
        {
           
            Console.Write(node.item);
            if (node.left != null)
            {
                DisplayPreOrder(node.left);
            }

            if (node.right != null)
            {
                DisplayPreOrder(node.right);
                
            }
        }

        public void DisplayPostOrder()
        {
            if (RootNode != null)
            {
                DisplayPostOrder(RootNode);
                Console.WriteLine();
            }
            else
            {
                Console.WriteLine("Tree is empty.");
            }

        }
        public void DisplayPostOrder(BinaryNode<char> node)
        {
            if (node.left != null)
            {
                DisplayPostOrder(node.left);
            }

            if (node.right != null)
            {
                DisplayPostOrder(node.right);

            }

            Console.Write(node.item);
        }

        public double Eval()
        {
            return Eval(RootNode);
        }

        private double Eval(BinaryNode<char> node)
        {
            double value = 0;
            if (node.isLeaf())
            {
                // cheap way to convert a single digit number to an integer
                value = node.item - '0';
            }
            else
            {
                switch (node.item)
                {
                    case '+':
                        // TODO evaluate operator
                        break;
                    case '-':
                        // TODO evaluate operator
                        break;
                    case '*':
                        // TODO evaluate operator
                        break;
                    case '/':
                        // TODO evaluate operator
                        break;
                    default:
                        Console.WriteLine("Invalid OP {0}", node.item);
                        value = 0;
                        break;
                }
            }

            return value;
        }

        public void DisplayInOrder()
        {
            if (RootNode != null)
            {
                DisplayInOrder(RootNode);
                Console.WriteLine();
            }
            else
            {
                Console.WriteLine("Tree is empty.");
            }
        }

        private void DisplayInOrder(BinaryNode<char> node)
        {
            if (node.left != null)
            {
                Console.Write('(');
                DisplayInOrder(node.left);
            }
            Console.Write(node.item);
            if (node.right != null)
            {
                DisplayInOrder(node.right);
                Console.Write(')');
            }
        }

    }
}

[Cody Biggs]

So made some changes. gets me closer, but still not what I want.

Right paren case is now

case ')':
                        if (nodeStack.Count > 0)
                        {
                            child = currentNode; ;
                            currentNode = nodeStack.Pop();
                            if (currentNode.left == null)
                            {
                                currentNode.left = child;
                            }//end if
                            else if (currentNode.right == null)
                            {
                                currentNode.right = child;
                            }//end else if
                            else
                            {
                                Console.WriteLine("Something went wrong!!!");
                            }// end else
                        }
                        break;

and number case is

case '1':
                    case '2':
                    case '3':
                    case '4':
                    case '5':
                    case '6':
                    case '7':
                    case '8':
                    case '9':
                    case '0':
                        BinaryNode<char> bin = new BinaryNode<char>();
                        nextChar = bin.item;
                        if(currentNode.left == null)
                        {
                            currentNode.left = bin;
                        }
                        else if( currentNode.right == null)
                        {
                            currentNode.right = bin;
                        }
                        else
                        {
                            Console.WriteLine("Something went wrong!!!");
                        }
                        break;

[Cody Biggs]

Solved it....Just need to slow down and look carefully at what the program is asking.

full fixed class just in case anyone saw this, and was thinking

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

namespace BiggsProgram5
{
    class BinaryExpressionTree
    {
        public int Count { get; set; }
        public BinaryNode<char> RootNode;
        public string Expression { get; private set; }

        public BinaryExpressionTree(String expression)
        {
            this.Expression = expression;
            // get rid of the pesky spaces
            Console.WriteLine(expression);
            Queue<char> expr = new Queue<char>(expression.ToCharArray());
            RootNode = Parse(expr);
        }

        public BinaryNode<char> Parse(Queue<char> expressionQueue)
        {
            Stack<BinaryNode<char>> nodeStack = new Stack<BinaryNode<char>>();

            BinaryNode<char> currentNode = null;
            BinaryNode<char> child = null;
            char nextChar;
            

            while(expressionQueue.Count > 0)
            {
                nextChar = expressionQueue.Dequeue();

                switch (nextChar)
                {
                    case '(' :
                        if(currentNode != null)
                        {
                            nodeStack.Push(currentNode);
                        }
                        currentNode = new BinaryNode<char>();
                        break;

                    case ')':
                        if (nodeStack.Count > 0)
                        {
                            child = currentNode; ;
                            currentNode = nodeStack.Pop();
                            if (currentNode.left == null)
                            {
                                currentNode.left = child;
                            }//end if
                            else if (currentNode.right == null)
                            {
                                currentNode.right = child;
                            }//end else if
                            else
                            {
                                Console.WriteLine("Something went wrong!!!");
                            }// end else
                        }
                        break;

                    case '+':
                    case '-':
                    case '*':
                    case '/':
                    case '^':
                        currentNode.item = nextChar;
                        break;

                    case '1':
                    case '2':
                    case '3':
                    case '4':
                    case '5':
                    case '6':
                    case '7':
                    case '8':
                    case '9':
                    case '0':
                        BinaryNode<char> bin = new BinaryNode<char>();
                        bin.item = nextChar;
                        if(currentNode.left == null)
                        {
                            currentNode.left = bin;
                        }
                        else if( currentNode.right == null)
                        {
                            currentNode.right = bin;
                        }
                        else
                        {
                            Console.WriteLine("Something went wrong!!!");
                        }
                        break;
                }//end switch
            }//end while
            RootNode = currentNode;
            return RootNode;
        }

        public void DisplayPreOrder()
        {
            if (RootNode != null)
            {
                DisplayPreOrder(RootNode);
                Console.WriteLine();
            }
            else
            {
                Console.WriteLine("Tree is empty.");
            }
        }
        public void DisplayPreOrder(BinaryNode<char> node)
        {
           
            Console.Write(node.item);
            if (node.left != null)
            {
                DisplayPreOrder(node.left);
            }

            if (node.right != null)
            {
                DisplayPreOrder(node.right);
                
            }
        }

        public void DisplayPostOrder()
        {
            if (RootNode != null)
            {
                DisplayPostOrder(RootNode);
                Console.WriteLine();
            }
            else
            {
                Console.WriteLine("Tree is empty.");
            }

        }
        public void DisplayPostOrder(BinaryNode<char> node)
        {
            if (node.left != null)
            {
                DisplayPostOrder(node.left);
            }

            if (node.right != null)
            {
                DisplayPostOrder(node.right);

            }

            Console.Write(node.item);
        }

        public double Eval()
        {
            return Eval(RootNode);
        }

        private double Eval(BinaryNode<char> node)
        {
            double value = 0;
            if (node.isLeaf())
            {
                // cheap way to convert a single digit number to an integer
                value = node.item - '0';
            }
            else
            {
                switch (node.item)
                {
                    case '+':
                        // TODO evaluate operator
                        break;
                    case '-':
                        // TODO evaluate operator
                        break;
                    case '*':
                        // TODO evaluate operator
                        break;
                    case '/':
                        // TODO evaluate operator
                        break;
                    default:
                        Console.WriteLine("Invalid OP {0}", node.item);
                        value = 0;
                        break;
                }
            }

            return value;
        }

        public void DisplayInOrder()
        {
            if (RootNode != null)
            {
                DisplayInOrder(RootNode);
                Console.WriteLine();
            }
            else
            {
                Console.WriteLine("Tree is empty.");
            }
        }

        private void DisplayInOrder(BinaryNode<char> node)
        {
            if (node.left != null)
            {
                Console.Write('(');
                DisplayInOrder(node.left);
            }
            Console.Write(node.item);
            if (node.right != null)
            {
                DisplayInOrder(node.right);
                Console.Write(')');
            }
        }

    }
}