[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1714
  • Last Modified:

Infix tree

Hello,

I have the following code which firstly converts the infix expression to postfix and then creates an expression tree using the postfix expression. However, I am after some information or links on how to create an expression tree without converting to postfix first. The majority of my resources say it is easier to cretae the tree off of the postfix expression, but I would like to see how it is done via a prefix expression.


import java.util.* ;            //Declaration of classes to import
import java.lang.* ;
import javax.swing.* ;
import java.awt.* ;
import java.awt.event.* ;

//Declaration of class inFixSort that extends JFrame utilises a GUI for users expression input
//and converts the expression into postfix notation with a stack and tree afterwhich the value of the expression tree
//is calculated using a stack
class InFixSort extends JFrame
{
      
      Stack pile ;      //Stack used for storing operators and node objects
      Stack calc ;      //Stack used for calculating the expression
      String output = "" ;      //String variable used for storing the postfix notation of the users input
      
      
      Node node ;            //Declaration of node object
      Node root = null ;      //Declaration and initialisation of root object
      double leftValue = 0 ;            //Declaration of variables used for storing the numeric values of nodes in the tree
      double rightValue = 0 ;
      double treeValue = 0 ;
      
      private JTextField textField1, textField2 ;      //Declaration of JTextField Objects
      private JTextArea textArea1 ;      //Declaration of JTextArea Objects
      
      private JButton updateButton, exitButton ;      //Declaration of JButton Objects
      
      
   
      public InFixSort ()      //Default constructor
      {
            
            super ("Expression Tree") ;            //Used for the title of the JFrame
            Container container = getContentPane () ;            //Creates a container for the JFrame
           container.setLayout (new FlowLayout ()) ;            //Create a layout for the JFrame
           
           textField1 = new JTextField ("Expression to Calculate",20) ;      //Declaration and Initialisation of JTextField
           textField1.setEditable (false) ;
           container.add (textField1) ;
           
           textField2 = new JTextField (20) ;      //Gets the expression from the user
           textField2.setEditable (true) ;
           container.add (textField2) ;
           
           textArea1 = new JTextArea (15,30) ;      //Creates a text area for displaying the output to the user
           textArea1.setEditable (false) ;
           container.add(new JScrollPane(textArea1)) ;
           
           //Button populates the textarea with sorted expression and the value of the expression
           updateButton = new JButton ("Update Display") ;      
           updateButton.addActionListener(
                 
                 new ActionListener() {            //Listens for a key press
                 
                 
                       public void actionPerformed (ActionEvent event)      
                       {      
                       
                             try
                             {
                                   textArea1.setText("") ;      //Clears the text area
                                   pile = new Stack () ;      //Creates a new Stack for holding the operators
                                    calc = new Stack () ;      //Creates a new Stack that stores the value of the expression
                                    //convertToPostfix ((String)textField2.getText()) ;
                                   String value = "(5-4)/(7*9)" ;
                                   textField2.setText(value) ;
                                   convertToPostfix (value) ;            //Processes the equation entered by the user
                                    createTree () ;            //Creates the binary expression tree
                                    textArea1.append("PostOrder value of Expression\n") ;
                                    calcPostOrder () ;      //Calculates the value in the expression tree
                                    expressionValue () ;      //Displays the value of the expression tree
                              }
                              //If the user has not entered an expression catches any empty stack exception
                              catch( EmptyStackException e)      
                              {
                                    
                              }
                       }
                 }
           );
           container.add (updateButton) ;
           
           //Set the size and visibility of the JFrame
           setSize (370,400) ;
           setVisible (true) ;
      }
        
      //Method used for validating the precednce of the operator in the expression typed by the user
      //and the precedence of the operator in the stack
    public void pushIt (String digit, int validate )
      {
            String tempValue ;
            while( !pile.isEmpty() )      //While used while stack is empty
            {
                  tempValue = popIt() ;
                  
                  int matchValue = 0 ;
                  if (tempValue.equals("("))      
                  {
                        //If a ( is passed into the method push the popped value back onto the stack
                        pile.push (tempValue) ;
                        break ;
                  }
                  else
                  {
                        //Validates if the popped value of the stack is a + or - and assigns a value 1 to the match variable
                        if((tempValue.equals("+"))||(tempValue.equals("-")))
                        {
                              matchValue = 1      ;
                        }
                        else //If the popped value is a * or / assign the value 2 to the matchValue variable
                        {
                              matchValue = 2 ;      
                        }
                        if(matchValue < validate)      
                        {
                              //If the precedence of the popped value is less than the precedence of
                              //the digit passed into the  method.push the popped digit back onto the stack
                              pile.push (tempValue) ;
                              break ;
                        }
                        else
                              //Else assign the value in the tempValue variale to the output variable
                              output = output + tempValue ;
                  }
            }
            //Push the digit passed into the method onto the stack
            pile.push (digit) ;
      }
      
      //Method pops a value from the stack and returns the value to the calling method
      public String popIt ()
      {
            String temp ="";
            temp += pile.pop () ;
            
            
            return temp ;      
      }
      
      
      //Method Pops all the operators off of the stack untill the stack is empty
      public void popStack ()
      {
            while( !pile.isEmpty() )    
        {
               output = output + pile.pop();
        }
       
      }
      //Method converts the users expression to postfix
      public void convertToPostfix (String input)
      {
            String[] thisString = new String [input.length()] ;
            
            //For loop used for incrementing through the users input
            for(int i = 0 ; i < input.length() ; i ++)      
           {
                 //Use charAt to validate digit within input string
                 char ch = input.charAt(i) ;
                 
                 //If the digit is a letter or a space do nothing
                 if((Character.isLetter(ch)) || (ch == ' '))
                 {
                       //System.out.println("Invalid input") ;
                 }
                 else
                 {
                       //Else use a switch case statement to validate the input
                       switch(ch)
                       {
                             case '+':    
                             case '-':
                                   //If the digit is a + or - pass the value into the pushIt method
                                   //along with the value 1 to indicate precedence of operator
                                   pushIt (input.substring(i,i+1),1) ;
                                 break;              
                        case '*':              
                        case '/':
                              //If the digit is a * or / pass the value into the pushIt method
                                   //along with the value 2 to indicate precedence of operator
                              pushIt(input.substring(i,i+1),2) ;
                              break;              
                        case '(':              
                                 //Push a ( onto the stack
                                 pile.push(ch);
                                 break;
                        case ')':              
                              //While the stackis not empty pop all operatorsfrom the stack ans assign them to the output
                              //string untill the value popped off of the stack is a (
                                 while( !pile.isEmpty() )
                                {
                                      String gotCh = "" ;
                                      gotCh += popIt();
                                      if( gotCh.equals ("(") )  
                                               break;                
                                       else                      
                                          output = output + gotCh;
                                }  
                               
                           break;
                        default:  
                              //If the digit is numeric add the value to the output variable
                              output = output+ ch ;
                           break;
                       }
                 }
           }
           popStack() ;
      }
      
      //Method used for creating the binary tree from the postfix expression based on the
      //value within the output variable that was constructed using the convertToPostfix method
      public void createTree ()
      {
            //For loop used for incrementing through each digit in the output variable
            for(int i = 0 ; i < output.length() ; i ++)      
           {
                 //Use charAt to validate digit within input string
                 char ch = output.charAt(i) ;
                 //Cast the digit as a character object and create a new node
                 node = new Node (new Character (ch)) ;
                 switch (ch)
                 {
                       case '+':    
                       case '-':
                       case '*':
                       case '/':
                                   //If the ch variable has a value of  +,-,*,/ then assign the value at the peek of the
                                   //stack to the right hand side of the node pop the stack and then assign the value at the
                                   //top of the stack to the left hand side of the stack, then push the newly created node
                                   //with left and right branches onto the stack
                                 node.setRight(pile.peek ()) ;
                                 pile.pop () ;
                                 node.setLeft(pile.peek ()) ;
                                 pile.pop () ;
                                 pile.push(node) ;
                       break ;
                       
                       default :
                             //if the value is not a  +,-,*,/ then push the value onto the stack (indicates a numeric value)
                             pile.push(node) ;
                 }
           }
           //Once all the digits in the output variable have been validated cast the
           //value at the topof the stack to a node and assign this to the root object
           root = (Node)pile.peek () ;
    }
      
      //Recursive helper used for calculating the value of the tree
      public void calcPostOrder()
        {
              //Validate the root node
              calcPostOrder(root);
       }
      
      public void calcPostOrder(Node node)
      {
              if (node == null) return;
      
                    // first recur on both subtrees
                    calcPostOrder(node.left);
                    calcPostOrder(node.right);
      
                  //Cast the node element to a character and assign the value to char variable digit
                    char digit = (Character) node.element ;
                   
                   //Convert the value of digit to a string and append the value to the
                   textArea1.append(Character.toString(digit));
                   double valueOfDigit = 0 ;
                   char charRight = ' ' ;
                   char charLeft = ' ' ;
                   switch (digit)
                   {
                         case '+':  
                               //If the digit is a +, pop the stack and cast to a double then assign the value to a
                               //the variable called rightValue. pop the stack again and cast the value to a double
                               //then assign this value to the leftValue variable.
                               rightValue = (Double) calc.pop () ;
                               leftValue = (Double) calc.pop () ;
                               //Assign the calculation of the left and right value variables to
                               //the treeValue variable, then push the treeValue variable onto the stack
                               treeValue = leftValue + rightValue ;
                               calc.push(treeValue) ;
                               break ;
                       case '-':
                             rightValue = (Double) calc.pop () ;
                               leftValue = (Double) calc.pop () ;
                               treeValue = leftValue - rightValue ;
                               calc.push(treeValue) ;
                               break ;
                       case '*':
                             rightValue = (Double) calc.pop () ;
                               leftValue = (Double) calc.pop () ;
                               treeValue = leftValue * rightValue ;
                               calc.push(treeValue) ;
                               break ;
                       case '/':
                             rightValue = (Double) calc.pop () ;
                               leftValue = (Double) calc.pop () ;
                               treeValue = leftValue / rightValue ;
                               calc.push(treeValue) ;
                             break ;
                       default :
                             //If the digit is not a +,-,*, / then get the numeric value of the character and
                             //assign the value to valueOfDigit variable. Push the value in the variable valueOfDigit
                             //Onto the stack
                             valueOfDigit = Character.getNumericValue(digit) ;
                             calc.push(valueOfDigit) ;
                   }
       }
      
      
      //Method used for displaying the value of the expression to the user
      public void expressionValue ()
      {
            //While the stack is not empty Pop the value off of the top of the stack
            //cast it to a double then assign the value to the value variable. Afterwhich,
            //convert the double value to a string and display it in the text area
            while( !calc.isEmpty() )
            {
                  double value = (Double) calc.pop () ;
                  textArea1.append("\nValue of Expression\n") ;
                  textArea1.append(Double.toString(value)) ;
            }
            
      }
      
      //Declaration of main method
      public static void main (String args[])
      {
            InFixSort object = new InFixSort();
            object.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE) ;
            
      }
      
      
}


//Node class used for constructing the tree
class Node
{
    Node left; //Declaration of left node object
    Node right; //Declaration of right node object
    Object element; //Used for storing the Character objects

      //User defined Constructor used for initialising the left
    Node(Object newData)
    {
      left = null;       //Initialises the left node in the tree to null
      right = null;       //Initialises the right node in the tree to null
      element = newData;       //Initialises the element object to the value passed into the method
    }
   
    //Assigns the right node object the referece of the object passed inot the method
    public void setRight (Object obj)
    {
          right = (Node)obj ;      //Casts the object to a node and assigns the value to the right node object
    }
   
     //Assigns the left node object the referece of the object passed inot the method
    public void setLeft (Object obj)
    {
          left = (Node)obj ;      //Casts the object to a node and assigns the value to the left node object
    }
}
0
Cyart
Asked:
Cyart
1 Solution
 
JakobACommented:
Here is a micro compiler using infix trees:

/*
**  implement a very small interpreter
*/

import java.util.*;
import java.io.*;


class ParseError extends Exception {
    public ParseError( String message ) {
        super( message );
    }
} // endclass ParseError

class RuntimeError extends Exception {
    public RuntimeError( String message ) {
        super( message );
    }
} // endclass RuntimeError


interface Element {  // the groups and atoms of a statement
    public int getValue( ) throws RuntimeError;
    public int setValue( int value ) throws RuntimeError;
} //end interface Element


class Value implements Element {

    private int value;

    public Value ( int value ) { this.value = value; }
   
    public int getValue( ) throws RuntimeError {
        return this.value;
    }
   
    public int setValue( int value ) throws RuntimeError {
        throw new RuntimeError( "attempt to change the value of a constant." );
    }

} //endclass Value


class Variable implements Element {
   
    private static final Variable[] vt = new Variable[26]; // the nametable
   
    private int value;
    private boolean initialized;
    private String name;
   
    private Variable ( String name ) { // instances created only by getVariable()
        this.initialized = false;
        this.name = name;
    }
   
    static Variable getVariable( String name ) {
        for ( int i=0; i<vt.length; i++ ) {      // return existing variable
            if ( vt[i] != null && vt[i].name.equals(name) ) return vt[i];
        }
        for ( int i=0; i<vt.length; i++ ) {      // or create a new one
            if ( vt[i] == null  ) return ( vt[i] = new Variable( name ) );  
        }
        throw new Error( "Impossible error. More that 26 variables used." );
    }
   
    public int getValue( ) throws RuntimeError {
        if ( this.initialized ) return this.value;
        throw new RuntimeError( "variable " +name +" not initialized." );
    }

    public int setValue( int value ) throws RuntimeError {
        this.initialized = true;
        return ( this.value = value );
    }

} //endclass variable


class Triple implements Element {
   
    private Element operand1, operand2;
    private char  operator;  
   
    public Triple ( Element op1, char operator, Element op2 ) {
        this.operand1 = op1;
        this.operator = operator;
        this.operand2 = op2;
    }
       
    public int getValue() throws RuntimeError {
        switch ( this.operator ) {
            case '=': return operand1.setValue( operand2.getValue() );
            case '+': return operand1.getValue() + operand2.getValue();
            case '-': return operand1.getValue() - operand2.getValue();
            case '*': return operand1.getValue() * operand2.getValue();
            case '/': {
                int divisor = operand2.getValue();
                if ( divisor != 0 ) return operand1.getValue() / divisor;
                throw new RuntimeError( "attempted division by 0.'" );
            }
            default:
                throw new RuntimeError( "unknown operator code '" +operator +"'." );
        }
    }

    public int setValue( int value ) throws RuntimeError {
        throw new RuntimeError( "attempt to change the value of an expression." );
    }

} // endclass Triple



        //   adds a one-token lookahead
class Tokenizer extends StringTokenizer {
   
    String next;
   
    public Tokenizer( String s ) {
        super( s );
        next = hasMoreTokens() ? nextToken() : " ";
    }
    char peekNextChar() {
        return next.charAt(0);
    }
    boolean skipPredicted( String s ) {
        if ( ! s.equals(next) ) return false;
        next = hasMoreTokens() ? nextToken() : " ";
        return true;
    }
    String fetchNext( ) {
        String temp = this.next;
        next = hasMoreTokens() ? nextToken() : " ";
        return temp;
    }
       
} // endclass Tokenizer


        // inplement the simple syntax
class Compile {
   
    static Tokenizer t;

    static final String names = "ABCDEFGHIJKLMNOPQRSTUVWXUZ";
    static final String digits = "0123456789";
   
    static Element lValue() throws ParseError {
        String name = t.fetchNext();
        if ( names.indexOf(name)  >= 0 ) return Variable.getVariable( name );
        if ( digits.indexOf(name) >= 0 ) return new Value( Integer.parseInt( name ) );
        throw new ParseError( "bad left side variable '" +name +"'." );
    }
    static Element parenthetical() throws ParseError {
        Element temp = expression();
        if ( t.skipPredicted(")") ) return temp;
        throw new ParseError( "bad parenthetical, ')' expected." );
    }
    static Element factor() throws ParseError {
        String nxt = t.fetchNext();
        if ( nxt.equals( "(" ) ) return parenthetical();
        if ( names.indexOf(nxt)  >= 0 ) return Variable.getVariable( nxt );
        if ( digits.indexOf(nxt) >= 0 ) return new Value( Integer.parseInt( nxt ) );
        throw new ParseError( "Bad Factor at '" +nxt +"'." );
    }
    static Element term() throws ParseError {
        Element op1 = factor();
        char opr = t.peekNextChar();
        while ( opr == '*' || opr == '/' ) {
            t.fetchNext();
            op1 = new Triple( op1, opr, factor() );
            opr = t.peekNextChar();
        }
        return op1;
    }
    static Element expression() throws ParseError {
        Element op1 = term();
        char opr = t.peekNextChar();
        while ( opr == '+' || opr == '-' ) {
            t.fetchNext();
            op1 = new Triple( op1, opr, term() );
            opr = t.peekNextChar();
        }
        return op1;
    }
    static Element statement( String s ) {
        t = new Tokenizer( s );
        try {
            Element op1 = lValue();
            Element op2;
            if ( t.skipPredicted("=") ) {
                op2 = expression();
            } else {
                throw new ParseError( "no assignment in statement." );
            }
            if ( t.skipPredicted(";") ) return new Triple( op1, '=', op2 );
            throw new ParseError( "missing ';' at end of statement." );
        } catch ( ParseError e ) {
            System.out.println( "error in line: " +s );
            System.out.println( "Parsing error: " +e.getMessage() );
        }
        return new Value( -666 );
    }
   
} // endclass Compile


        // the main class compile and execute a file containing a simple program
class CalcFunction {
   
    static final int MAX = 100;     // max 100 statements
    static Element[] statements = new Element[MAX];
    static String[] lines     = new String[MAX];
    static int programLength = 0;
   
    static String readLine( InputStream reader ) {
        String line = "";
        int ch;
        try {
            while ( (ch=reader.read()) != 13 && ch != -1 ) {
                if ( ch != 10 ) line += (char)ch;
            }
        } catch ( Exception e ) {
            System.out.print( "error in readLine." );
        }
        return line;
    }
   
    static void compile( String fileName ) {
        FileInputStream fil;
        try {
            fil = new FileInputStream( fileName );
        } catch ( Exception e ) {
            System.out.print( "no such file found." );
            throw new Error( "compilation terminated in error." );
        }
        String line = readLine( fil );
        while ( ! line.equals( "" ) ) {
            lines[programLength] = line;
            statements[ programLength++ ] = Compile.statement( line );
            line = readLine( fil );
        }
    }

    static void execute( ) {
        for ( int i=0; i<programLength; i++ ) {
            System.out.println( i +": " +lines[i] );
            try {
                System.out.println( "      calculated value is " +statements[i].getValue() );
            } catch ( RuntimeError e ) {
                System.out.println ( "statement nr " +i +" failed: " +e.getMessage() );
            }
        }
    }

    public static void main( String[] args ) {
        String fileName = "c:/testprogram.txt";
       
        System.out.println( "\n--- Compiling '" +fileName +"'." );
        compile( fileName );
       
        System.out.println( "\n\n--- Running '" +fileName +"'." );
        execute( );
       
        System.out.println( "1997*(1.0/1997) gives " +( 1997 * ( 1.0 / 1997 ) ) );
           
    }
   
} // endclass CalcFunction


/*        file  c:/testprogram.txt  contain:

A = 5 ;
B = A * 2 + 9 ;
C = A + B * ( 1 - 1 ) ;
C = A + B / ( 1 - 1 ) ;  // divide by zero
C = 7 + C ;
D = B + C + A * 2 ;
E = A * ( B + C ) ;
F = E / 5 ;
G = A + ( B + ( C + ( D + ( E + ( F * 2 ) ) ) ) ) ;
9 = 4 * A ;             // assign to a number

*/

/*        and gives the below output:

--- Compiling 'c:/testprogram.txt'.
error in line: 9 = 4 * A ;
Parsing error: bad left side variable '9'.

--- Running 'c:/testprogram.txt'.
0: A = 5 ;               should give 5
      calculated value is 5
1: B = A * 2 + 9 ;       should give 19
      calculated value is 19
2: C = A + B * ( 1 - 1 ) ;
      calculated value is 5
3: C = A + B / ( 1 - 1 ) ;
statement nr 3 failed: attempted division by 0.'
4: C = 7 + C ;
      calculated value is 12
5: D = B + C + A * 2 ;
      calculated value is 41
6: E = A * ( B + C ) ;
      calculated value is 155
7: F = E / 5 ;
      calculated value is 31
8: G = A + ( B + ( C + ( D + ( E + ( F * 2 ) ) ) ) ) ;
      calculated value is 294
9: 9 = 4 * A ;
      calculated value is -666

Process Exit.

*/

ask if it is too incomprehensible :-))

regards JakobA
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!

Tackle projects and never again get stuck behind a technical roadblock.
Join Now