?
Solved

Tree loop problem

Posted on 2005-03-08
10
Medium Priority
?
172 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 

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

Industry Leaders: 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!

Question has a verified solution.

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

For beginner Java programmers or at least those new to the Eclipse IDE, the following tutorial will show some (four) ways in which you can import your Java projects to your Eclipse workbench. Introduction While learning Java can be done with…
Introduction Java can be integrated with native programs using an interface called JNI(Java Native Interface). Native programs are programs which can directly run on the processor. JNI is simply a naming and calling convention so that the JVM (Java…
Video by: Michael
Viewers learn about how to reduce the potential repetitiveness of coding in main by developing methods to perform specific tasks for their program. Additionally, objects are introduced for the purpose of learning how to call methods in Java. Define …
This theoretical tutorial explains exceptions, reasons for exceptions, different categories of exception and exception hierarchy.
Suggested Courses

752 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