Java Program to Construct an Expression Tree for an Infix Expression

This is a java program to construct an expression tree using infix expression and perform the infix, prefix and postfix traversal of the expression tree. The leaves of a binary expression tree are operands, such as constants or variable names, and the other nodes contain operators. These particular trees happen to be binary, because all of the operations are binary, and although this is the simplest case, it is possible for nodes to have more than two children. It is also possible for a node to have only one child, as is the case with the unary minus operator. An expression tree, T, can be evaluated by applying the operator at the root to the values obtained by recursively evaluating the left and right sub-trees.

Here is the source code of the Java Program to Construct an Expression Tree for an Infix Expression. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

//This is a java program to construct Expression Tree using Infix Expression
import java.io.*;
 
class Node
{
    public char data;
    public Node leftChild;
    public Node rightChild;
 
    public Node(char x)
    {
        data = x;
    }
 
    public void displayNode()
    {
        System.out.print(data);
    }
}
 
class Stack1
{
    private Node[] a;
    private int    top, m;
 
    public Stack1(int max)
    {
        m = max;
        a = new Node[m];
        top = -1;
    }
 
    public void push(Node key)
    {
        a[++top] = key;
    }
 
    public Node pop()
    {
        return (a[top--]);
    }
 
    public boolean isEmpty()
    {
        return (top == -1);
    }
}
 
class Stack2
{
    private char[] a;
    private int    top, m;
 
    public Stack2(int max)
    {
        m = max;
        a = new char[m];
        top = -1;
    }
 
    public void push(char key)
    {
        a[++top] = key;
    }
 
    public char pop()
    {
        return (a[top--]);
    }
 
    public boolean isEmpty()
    {
        return (top == -1);
    }
}
 
class Conversion
{
    private Stack2 s;
    private String input;
    private String output = "";
 
    public Conversion(String str)
    {
        input = str;
        s = new Stack2(str.length());
    }
 
    public String inToPost()
    {
        for (int i = 0; i < input.length(); i++)
        {
            char ch = input.charAt(i);
            switch (ch)
            {
                case '+':
                case '-':
                    gotOperator(ch, 1);
                    break;
                case '*':
                case '/':
                    gotOperator(ch, 2);
                    break;
                case '(':
                    s.push(ch);
                    break;
                case ')':
                    gotParenthesis();
                    break;
                default:
                    output = output + ch;
            }
        }
        while (!s.isEmpty())
            output = output + s.pop();
        return output;
    }
 
    private void gotOperator(char opThis, int prec1)
    {
        while (!s.isEmpty())
        {
            char opTop = s.pop();
            if (opTop == '(')
            {
                s.push(opTop);
                break;
            } else
            {
                int prec2;
                if (opTop == '+' || opTop == '-')
                    prec2 = 1;
                else
                    prec2 = 2;
                if (prec2 < prec1)
                {
                    s.push(opTop);
                    break;
                } else
                    output = output + opTop;
            }
        }
        s.push(opThis);
    }
 
    private void gotParenthesis()
    {
        while (!s.isEmpty())
        {
            char ch = s.pop();
            if (ch == '(')
                break;
            else
                output = output + ch;
        }
    }
}
 
class Tree
{
    private Node root;
 
    public Tree()
    {
        root = null;
    }
 
    public void insert(String s)
    {
        Conversion c = new Conversion(s);
        s = c.inToPost();
        Stack1 stk = new Stack1(s.length());
        s = s + "#";
        int i = 0;
        char symbol = s.charAt(i);
        Node newNode;
        while (symbol != '#')
        {
            if (symbol >= '0' && symbol <= '9' || symbol >= 'A'
                    && symbol <= 'Z' || symbol >= 'a' && symbol <= 'z')
            {
                newNode = new Node(symbol);
                stk.push(newNode);
            } else if (symbol == '+' || symbol == '-' || symbol == '/'
                    || symbol == '*')
            {
                Node ptr1 = stk.pop();
                Node ptr2 = stk.pop();
                newNode = new Node(symbol);
                newNode.leftChild = ptr2;
                newNode.rightChild = ptr1;
                stk.push(newNode);
            }
            symbol = s.charAt(++i);
        }
        root = stk.pop();
    }
 
    public void traverse(int type)
    {
        switch (type)
        {
            case 1:
                System.out.print("Preorder Traversal:-    ");
                preOrder(root);
                break;
            case 2:
                System.out.print("Inorder Traversal:-     ");
                inOrder(root);
                break;
            case 3:
                System.out.print("Postorder Traversal:-   ");
                postOrder(root);
                break;
            default:
                System.out.println("Invalid Choice");
        }
    }
 
    private void preOrder(Node localRoot)
    {
        if (localRoot != null)
        {
            localRoot.displayNode();
            preOrder(localRoot.leftChild);
            preOrder(localRoot.rightChild);
        }
    }
 
    private void inOrder(Node localRoot)
    {
        if (localRoot != null)
        {
            inOrder(localRoot.leftChild);
            localRoot.displayNode();
            inOrder(localRoot.rightChild);
        }
    }
 
    private void postOrder(Node localRoot)
    {
        if (localRoot != null)
        {
            postOrder(localRoot.leftChild);
            postOrder(localRoot.rightChild);
            localRoot.displayNode();
        }
    }
}
 
public class Infix_Expression_Tree
{
    public static void main(String args[]) throws IOException
    {
        String ch = "y";
        DataInputStream inp = new DataInputStream(System.in);
        while (ch.equals("y"))
        {
            Tree t1 = new Tree();
            System.out.println("Enter the Expression");
            String a = inp.readLine();
            t1.insert(a);
            t1.traverse(1);
            System.out.println("");
            t1.traverse(2);
            System.out.println("");
            t1.traverse(3);
            System.out.println("");
            System.out.print("Enter y to continue ");
            ch = inp.readLine();
        }
    }
}

Output:

$ javac Infix_Expression_Tree.java
$ java Infix_Expression_Tree
 
Enter the Expression
A+B*C-D
 
Preorder Traversal:-    -+A*BCD
Inorder Traversal:-     A+B*C-D
Postorder Traversal:-   ABC*+D-

Related posts:

Circular Dependencies in Spring
Java Program to Check whether Undirected Graph is Connected using DFS
Fixing 401s with CORS Preflights and Spring Security
Java Program to Remove the Edges in a Given Cyclic Graph such that its Linear Extension can be Found
Java Program to Implement Extended Euclid Algorithm
XML-Based Injection in Spring
Convert a Map to an Array, List or Set in Java
Java Program to Implement Binomial Tree
Introduction to Java Serialization
Java Program to Implement AA Tree
Java Program to Solve a Matching Problem for a Given Specific Case
Java Program to Permute All Letters of an Input String
Giới thiệu java.io.tmpdir
Java Program to Implement LinkedHashMap API
Apache Commons Collections Bag
Functional Interfaces in Java 8
Java Program to Generate a Random Subset by Coin Flipping
How to Delay Code Execution in Java
Java Program to Implement wheel Sieve to Generate Prime Numbers Between Given Range
Remove All Occurrences of a Specific Value from a List
Java Program to Find Nearest Neighbor for Dynamic Data Set
Java Program to Generate Date Between Given Range
Using JWT with Spring Security OAuth (legacy stack)
Java List UnsupportedOperationException
Java Program to Perform Stooge Sort
Java Program to Generate All Possible Combinations Out of a, b, c, d, e
Consumer trong Java 8
Spring Boot - Building RESTful Web Services
Spring Security Registration – Resend Verification Email
Java Scanner hasNext() vs. hasNextLine()
Copy a List to Another List in Java
TreeSet và sử dụng Comparable, Comparator trong java