Expression Tree | Java program to construct an expression tree ; Java program for expression tree ; A utility function to check if ' c ' is an operator ; Utility function to do inorder traversal ; Returns root of constructed tree for given postfix expression ; Traverse through every character of input expression ; If operand , simply push into stack ; operator ; Pop two top nodes Store top Remove top ; make them children ; System . out . println ( t1 + " " + t2 ) ; Add this subexpression to stack ; only element will be root of expression tree ; Driver program to test above
import java . util . Stack ; class Node { char value ; Node left , right ; Node ( char item ) { value = item ; left = right = null ; } } class ExpressionTree { boolean isOperator ( char c ) { if ( c == ' + ' c == ' - ' c == ' * ' c == ' / ' c == ' ^ ' ) { return true ; } return false ; } void inorder ( Node t ) { if ( t != null ) { inorder ( t . left ) ; System . out . print ( t . value + " ▁ " ) ; inorder ( t . right ) ; } } Node constructTree ( char postfix [ ] ) { Stack < Node > st = new Stack < Node > ( ) ; Node t , t1 , t2 ; for ( int i = 0 ; i < postfix . length ; i ++ ) { if ( ! isOperator ( postfix [ i ] ) ) { t = new Node ( postfix [ i ] ) ; st . push ( t ) ; } else { t = new Node ( postfix [ i ] ) ; t1 = st . pop ( ) ; t2 = st . pop ( ) ; t . right = t1 ; t . left = t2 ; st . push ( t ) ; } } t = st . peek ( ) ; st . pop ( ) ; return t ; } public static void main ( String args [ ] ) { ExpressionTree et = new ExpressionTree ( ) ; String postfix = " ab + ef * g * - " ; char [ ] charArray = postfix . toCharArray ( ) ; Node root = et . constructTree ( charArray ) ; System . out . println ( " infix ▁ expression ▁ is " ) ; et . inorder ( root ) ; } }