?
Solved

Tree loop problem

Posted on 2005-03-08
10
Medium Priority
?
179 Views
Last Modified: 2010-03-31
Hi,

I have previously coded this program first converting to postfix then passing the expression into the tree and then evaluating the value of the tree. I am now trying to take the infix expression and place it directly into the tree, but for some reason when I come to print the contents of the tree in postorder it loops continously for a second or so displaying an error after which the end of the program is reached as if all nodes in the tree have been visited. Obviously this is not right as I should just see the values in the tree and not the errors.

Any help would be much appreciated.

import java.util.* ;
import java.lang.* ;

class inFixSort
{
      StringTokenizer inputString ;
      
      Stack operandStack ;
      Stack operatorStack ;
      Stack treeStack ;
      String output = "" ;
      int value = 0 ;
      int stackCount = 0 ;
      Node node ;
      Node root = null ;
      int numberCount = 0 ;
      
      
      
      
   
      public inFixSort (String input)
      {
            
            operandStack = new Stack () ;
            operatorStack = new Stack () ;
            treeStack = new Stack () ;
            convertToPostfix (input) ;
            
            
      
      }
      
      
      
      public String popOperator ()
      {
            String temp ="";
            temp += operatorStack.pop () ;
            
            
            return temp ;
      }
      
      
      
      public void displayOperatorStack ()
      {
            
            while( !operatorStack.isEmpty() )    
        {
               output = output + operatorStack.pop();
        }
            System.out.println(output);
      }
      
      public void displayOperandStack ()
      {
            output = "" ;
            while( !operandStack.isEmpty() )    
        {
               output = output + operandStack.pop();
        }
            System.out.println(output);
      }
      
      public void convertToPostfix (String input)
      {
            
            String[] thisString = new String [input.length()] ;
            
            int operatorCount = 0 ;
            int inputCounter = 0 ;
           for(int i = 0 ; i < input.length() ; i ++)      
           {
                 char ch = input.charAt(i) ;
                 System.out.println("Char at " + ch) ;
                 thisString[i] = input.substring(i,i+1) ;
                 
                 
                 inputCounter++ ;
                 if((Character.isLetter(ch)) || (ch == ' '))
                 {
                       //System.out.println("Invalid input") ;
                 }
                 else
                 {      
                       node = new Node (new Character (ch)) ;
                       switch (ch)
                       {
                             case '+':    
                             case '-':
                             case '*':
                             case '/':
                                   
                                   
                                   if((operatorCount == 1) && (numberCount == 2))
                                   {
                                         createRoot (input.length (),inputCounter) ;
                                         numberCount = 1 ;
                                   }
                                   operatorStack.push (node) ;
                                   operatorCount ++ ;
                             break ;
                             
                             default :
                                   numberCount++ ;
                                   operandStack.push(node) ;
                                   if((operatorCount == 1) && (numberCount == 2))
                                   {
                                         createRoot (input.length() ,inputCounter) ;
                                         numberCount = 1 ;
                                   }
                 }
                       
                       
                       
                       
                 }
           }
           
      }
      
      public void createRoot (int length, int counter)
      {
            node.setRight(operandStack.peek()) ;
          operandStack.pop () ;
          node.setLeft(operandStack.peek ()) ;
          operandStack.pop () ;
          operandStack.push(node) ;
          if(length == counter)
          {
          
                root = (Node)operandStack.peek () ;
                printPostorder () ;
          }
          
      }
      
      
      
      public void printPostorder()
        {
              System.out.println("Printing Tree");
             printPostorder(root);
             System.out.println();
      }
      public void printPostorder(Node node)
      {
              if (node == null) return;
      
              // first recur on both subtrees
                    printPostorder(node.left);
                    printPostorder(node.right);
      
        // then deal with the node
                   System.out.print(node.element + "  ");
      }
      
      
      
      
}
class TestStack
{
      public static void main (String args[])
      {
            inFixSort object = new inFixSort("2+5");
      }
}
      class Node
      { ///used for the tree
          Node left;
          Node right;
          Object element;
      
          Node(Object newData)
          {
            left = null;
            right = null;
            element = newData;
          }
          
          
          public void setRight (Object obj)
          {
                right = (Node)obj ;
          }
          
          public void setLeft (Object obj)
          {
                left = (Node)obj ;
          }
    }
0
Comment
Question by:Cyart
  • 5
  • 5
10 Comments
 
LVL 37

Expert Comment

by:zzynx
ID: 13487024
Add the following to printPostOrder:

     public void printPostorder(Node node) {
        if (node == null) return;
        System.out.println("Entered printPostOrder for node = " + node.element +   // <<< add this
                   " L=" + ((node.left.element==null) ? "null" : node.left.element) +        // <<< add this
                   " R=" + ((node.right.element==null) ? "null" : node.right.element) );   // <<< add this
        // first recur on both subtrees
        printPostorder(node.left);
        printPostorder(node.right);
     
        // then deal with the node
        System.out.print(node.element + "  ");
     }

It gives:
Entered printPostOrder for node = 5 L=2 R=5

That's the reason
0
 
LVL 37

Expert Comment

by:zzynx
ID: 13487163
Give it a try with

     public void createRoot (int length, int counter)
     {
         node.setRight(operatorStack.peek()) ;
         operatorStack.pop();
         operandStack.pop () ;
         node.setLeft(operandStack.peek ()) ;
         operandStack.pop () ;
         operandStack.push(node) ;
         if(length == counter)
         {
         
              root = (Node)operandStack.peek () ;
              printPostorder () ;
         }
         
     }

and

     public void printPostorder(Node node)
     {
        if (node == null || node.element==null) return;
        // first recur on both subtrees
        printPostorder(node.left);
        printPostorder(node.right);
     
        // then deal with the node
        System.out.print(node.element + "  ");
     }

It gives me:
Char at 2
Char at +
Char at 5
Printing Tree
2  +  5
0
 

Author Comment

by:Cyart
ID: 13488003
Yes works fine with the original statement in TestStack but will not deal with other expressions ie

inFixSort object = new inFixSort("2+5-6");

cheers
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:Cyart
ID: 13488167
Just playing I think I have sorted the problem with addition to your code, will get back to you later when i have a bit more time many thanks
0
 

Author Comment

by:Cyart
ID: 13488217
Sorry, one question why did you code this like this i.e set the operator to the right and then remove the element at the top of the operand stack and place the first element in the operand stack to the left? How does it know about the 2nd operand that was popped of  of the stack?

{
         node.setRight(operatorStack.peek()) ;            //here
         operatorStack.pop();
         operandStack.pop () ;                    //here
         node.setLeft(operandStack.peek ()) ;
         operandStack.pop () ;                //here
         operandStack.push(node) ;
         if(length == counter)
         {
         
              root = (Node)operandStack.peek () ;
              printPostorder () ;
         }
         
     }
0
 

Author Comment

by:Cyart
ID: 13489871
Just looked at your solution but it does not use the printPostOrder correctly i.e 25+
0
 
LVL 37

Expert Comment

by:zzynx
ID: 13493702
Well, I'm not that familiar with what the end results should be,
but I think with the hints I gave you should be able to fix all your problems.
It was clear what the reason of the loop was:
>> Entered printPostOrder for node = 5 L=2 R=5
So, just consider my first comment that reveals the problem and not my tries to solve it ;°)
0
 
LVL 37

Accepted Solution

by:
zzynx earned 900 total points
ID: 13493813
2nd try ;°)

[1]
In convertToPostfix() you have to add
        operatorCount--;
after each call to createRoot()

i.e.
                    switch (ch)
                    {
                         case '+':    
                         case '-':
                         case '*':
                         case '/':
                              if((operatorCount == 1) && (numberCount == 2))
                              {
                                   createRoot (input.length (),inputCounter) ;
                                   numberCount = 1 ;
                                   operatorCount -- ;   // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
                              }
                              operatorStack.push (node) ;
                              operatorCount ++ ;
                         break ;
                         
                         default :
                              numberCount++ ;
                              operandStack.push(node) ;
                              if((operatorCount == 1) && (numberCount == 2))
                              {
                                  createRoot (input.length() ,inputCounter) ;
                                  numberCount = 1 ;
                                  operatorCount -- ;  // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
                              }
               }

[2]
In createRoot() your first instruction should be
       node = (Node)operatorStack.pop();
i.e.

     public void createRoot (int length, int counter)
     {
         node = (Node)operatorStack.pop();  // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
         node.setRight(operandStack.peek()) ;
         operandStack.pop();
         node.setLeft(operandStack.peek ()) ;
         operandStack.pop();
         operandStack.push(node) ;
         if(length == counter) {
            root = (Node)operandStack.peek();
            printPostorder();
         }
     }

Result for "2+5":
-------------------
Char at 2
Char at +
Char at 5
Printing Tree
2  5  +

Result for "2+5-6":
----------------------
Char at 2
Char at +
Char at 5
Char at -
Char at 6
Printing Tree
2  5  +  6  -  

Result for "2+5-6*9":
------------------------
Char at 2
Char at +
Char at 5
Char at -
Char at 6
Char at *
Char at 9
Printing Tree
2  5  +  6  -  9  *
0
 

Author Comment

by:Cyart
ID: 13628882
Got it all sorted in the end, thanks for your help
0
 
LVL 37

Expert Comment

by:zzynx
ID: 13628920
thanks
0

Featured Post

Receive 1:1 tech help

Solve your biggest tech problems alongside global tech experts with 1:1 help.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

INTRODUCTION Working with files is a moderately common task in Java.  For most projects hard coding the file names, using parameters in configuration files, or using command-line arguments is sufficient.   However, when your application has vi…
Introduction This article is the last of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers our test design approach and then goes through a simple test case example, how …
This video teaches viewers about errors in exception handling.
This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.
Suggested Courses
Course of the Month9 days, 15 hours left to enroll

569 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question