Java Program to Create Expression Tree from Infix, Postfix and Prefix Expressions

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.

  1. //This is a java program to construct Expression Tree using Infix Expression
  2. import java.io.*;
  3.  
  4. class Node
  5. {
  6.     public char data;
  7.     public Node leftChild;
  8.     public Node rightChild;
  9.  
  10.     public Node(char x)
  11.     {
  12.         data = x;
  13.     }
  14.  
  15.     public void displayNode()
  16.     {
  17.         System.out.print(data);
  18.     }
  19. }
  20.  
  21. class Stack1
  22. {
  23.     private Node[] a;
  24.     private int    top, m;
  25.  
  26.     public Stack1(int max)
  27.     {
  28.         m = max;
  29.         a = new Node[m];
  30.         top = -1;
  31.     }
  32.  
  33.     public void push(Node key)
  34.     {
  35.         a[++top] = key;
  36.     }
  37.  
  38.     public Node pop()
  39.     {
  40.         return (a[top--]);
  41.     }
  42.  
  43.     public boolean isEmpty()
  44.     {
  45.         return (top == -1);
  46.     }
  47. }
  48.  
  49. class Stack2
  50. {
  51.     private char[] a;
  52.     private int    top, m;
  53.  
  54.     public Stack2(int max)
  55.     {
  56.         m = max;
  57.         a = new char[m];
  58.         top = -1;
  59.     }
  60.  
  61.     public void push(char key)
  62.     {
  63.         a[++top] = key;
  64.     }
  65.  
  66.     public char pop()
  67.     {
  68.         return (a[top--]);
  69.     }
  70.  
  71.     public boolean isEmpty()
  72.     {
  73.         return (top == -1);
  74.     }
  75. }
  76.  
  77. class Conversion
  78. {
  79.     private Stack2 s;
  80.     private String input;
  81.     private String output = "";
  82.  
  83.     public Conversion(String str)
  84.     {
  85.         input = str;
  86.         s = new Stack2(str.length());
  87.     }
  88.  
  89.     public String inToPost()
  90.     {
  91.         for (int i = 0; i < input.length(); i++)
  92.         {
  93.             char ch = input.charAt(i);
  94.             switch (ch)
  95.             {
  96.                 case '+':
  97.                 case '-':
  98.                     gotOperator(ch, 1);
  99.                     break;
  100.                 case '*':
  101.                 case '/':
  102.                     gotOperator(ch, 2);
  103.                     break;
  104.                 case '(':
  105.                     s.push(ch);
  106.                     break;
  107.                 case ')':
  108.                     gotParenthesis();
  109.                     break;
  110.                 default:
  111.                     output = output + ch;
  112.             }
  113.         }
  114.         while (!s.isEmpty())
  115.             output = output + s.pop();
  116.         return output;
  117.     }
  118.  
  119.     private void gotOperator(char opThis, int prec1)
  120.     {
  121.         while (!s.isEmpty())
  122.         {
  123.             char opTop = s.pop();
  124.             if (opTop == '(')
  125.             {
  126.                 s.push(opTop);
  127.                 break;
  128.             } else
  129.             {
  130.                 int prec2;
  131.                 if (opTop == '+' || opTop == '-')
  132.                     prec2 = 1;
  133.                 else
  134.                     prec2 = 2;
  135.                 if (prec2 < prec1)
  136.                 {
  137.                     s.push(opTop);
  138.                     break;
  139.                 } else
  140.                     output = output + opTop;
  141.             }
  142.         }
  143.         s.push(opThis);
  144.     }
  145.  
  146.     private void gotParenthesis()
  147.     {
  148.         while (!s.isEmpty())
  149.         {
  150.             char ch = s.pop();
  151.             if (ch == '(')
  152.                 break;
  153.             else
  154.                 output = output + ch;
  155.         }
  156.     }
  157. }
  158.  
  159. class Tree
  160. {
  161.     private Node root;
  162.  
  163.     public Tree()
  164.     {
  165.         root = null;
  166.     }
  167.  
  168.     public void insert(String s)
  169.     {
  170.         Conversion c = new Conversion(s);
  171.         s = c.inToPost();
  172.         Stack1 stk = new Stack1(s.length());
  173.         s = s + "#";
  174.         int i = 0;
  175.         char symbol = s.charAt(i);
  176.         Node newNode;
  177.         while (symbol != '#')
  178.         {
  179.             if (symbol >= '0' && symbol <= '9' || symbol >= 'A'
  180.                     && symbol <= 'Z' || symbol >= 'a' && symbol <= 'z')
  181.             {
  182.                 newNode = new Node(symbol);
  183.                 stk.push(newNode);
  184.             } else if (symbol == '+' || symbol == '-' || symbol == '/'
  185.                     || symbol == '*')
  186.             {
  187.                 Node ptr1 = stk.pop();
  188.                 Node ptr2 = stk.pop();
  189.                 newNode = new Node(symbol);
  190.                 newNode.leftChild = ptr2;
  191.                 newNode.rightChild = ptr1;
  192.                 stk.push(newNode);
  193.             }
  194.             symbol = s.charAt(++i);
  195.         }
  196.         root = stk.pop();
  197.     }
  198.  
  199.     public void traverse(int type)
  200.     {
  201.         switch (type)
  202.         {
  203.             case 1:
  204.                 System.out.print("Preorder Traversal:-    ");
  205.                 preOrder(root);
  206.                 break;
  207.             case 2:
  208.                 System.out.print("Inorder Traversal:-     ");
  209.                 inOrder(root);
  210.                 break;
  211.             case 3:
  212.                 System.out.print("Postorder Traversal:-   ");
  213.                 postOrder(root);
  214.                 break;
  215.             default:
  216.                 System.out.println("Invalid Choice");
  217.         }
  218.     }
  219.  
  220.     private void preOrder(Node localRoot)
  221.     {
  222.         if (localRoot != null)
  223.         {
  224.             localRoot.displayNode();
  225.             preOrder(localRoot.leftChild);
  226.             preOrder(localRoot.rightChild);
  227.         }
  228.     }
  229.  
  230.     private void inOrder(Node localRoot)
  231.     {
  232.         if (localRoot != null)
  233.         {
  234.             inOrder(localRoot.leftChild);
  235.             localRoot.displayNode();
  236.             inOrder(localRoot.rightChild);
  237.         }
  238.     }
  239.  
  240.     private void postOrder(Node localRoot)
  241.     {
  242.         if (localRoot != null)
  243.         {
  244.             postOrder(localRoot.leftChild);
  245.             postOrder(localRoot.rightChild);
  246.             localRoot.displayNode();
  247.         }
  248.     }
  249. }
  250.  
  251. public class Infix_Expression_Tree
  252. {
  253.     public static void main(String args[]) throws IOException
  254.     {
  255.         String ch = "y";
  256.         DataInputStream inp = new DataInputStream(System.in);
  257.         while (ch.equals("y"))
  258.         {
  259.             Tree t1 = new Tree();
  260.             System.out.println("Enter the Expression");
  261.             String a = inp.readLine();
  262.             t1.insert(a);
  263.             t1.traverse(1);
  264.             System.out.println("");
  265.             t1.traverse(2);
  266.             System.out.println("");
  267.             t1.traverse(3);
  268.             System.out.println("");
  269.             System.out.print("Enter y to continue ");
  270.             ch = inp.readLine();
  271.         }
  272.     }
  273. }

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-

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.