Expression Tree | C ++ program for expression tree ; An expression tree node ; A utility function to check if ' c ' is an operator ; Utility function to do inorder traversal ; A utility function to create a new node ; 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 ; make them children ; Add this subexpression to stack ; only element will be root of expression tree ; Driver program to test above
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct et { char value ; et * left , * right ; } ; bool isOperator ( char c ) { if ( c == ' + ' c == ' - ' c == ' * ' c == ' / ' c == ' ^ ' ) return true ; return false ; } void inorder ( et * t ) { if ( t ) { inorder ( t -> left ) ; printf ( " % c ▁ " , t -> value ) ; inorder ( t -> right ) ; } } et * newNode ( char v ) { et * temp = new et ; temp -> left = temp -> right = NULL ; temp -> value = v ; return temp ; } ; et * constructTree ( char postfix [ ] ) { stack < et * > st ; et * t , * t1 , * t2 ; for ( int i = 0 ; i < strlen ( postfix ) ; i ++ ) { if ( ! isOperator ( postfix [ i ] ) ) { t = newNode ( postfix [ i ] ) ; st . push ( t ) ; } else { t = newNode ( postfix [ i ] ) ; t1 = st . top ( ) ; st . pop ( ) ; t2 = st . top ( ) ; st . pop ( ) ; t -> right = t1 ; t -> left = t2 ; st . push ( t ) ; } } t = st . top ( ) ; st . pop ( ) ; return t ; } int main ( ) { char postfix [ ] = " ab + ef * g * - " ; et * r = constructTree ( postfix ) ; printf ( " infix ▁ expression ▁ is ▁ STRNEWLINE " ) ; inorder ( r ) ; return 0 ; }