Expression Trees

Monday, 23/01/2023

Tram Ho

On the first day of the Lunar New Year, I would like to wish everyone a new year full of health, success and luck in life. I hope to finish this series this year.

6.7 Expression Trees

Trees representing an expression are called expression trees. In expression trees, leaf nodes are operands and non-leaf nodes are operators. That is to say, an expression tree is a binary tree where the inner nodes are the operators and the leaves are the operands. An expression tree consists of binary expressions. But for the unary operator, a subtree will be empty. The figure below shows a simple expression tree for

$(A + B_C) / D$ .

In a Postfix Expression , an operator is written after its operands. People can refer to the definition and how to convert these types of expressions here and here

Algorithm to build Expression Trees from Postfix Expression

Now to build the expression tree, we use the stack. We iterate through the input expression and do the following for every character.

If a character is an operand, push that character onto the stack
If a character is an operator, pop two values from the stack, make them its children, and push the current node again. In the end, the only element of the stack will be the root of the expression tree.

The code of this algorithm I have reference here

import java.util.Stack;
 
class Node{
    char data;
    Node left,right;
    public Node(char data){
        this.data = data;
        left = right = null;
    }
}
 
public class Main {
    public static boolean isOperator(char ch){
        if(ch=='+' || ch=='-'|| ch=='*' || ch=='/' || ch=='^'){
            return true;
        }
        return false;
    }
    public static Node expressionTree(String postfix){
        Stack&lt;Node&gt; st = new Stack&lt;Node&gt;();
        Node t1,t2,temp;
 
        for(int i=0;i&lt;postfix.length();i++){
            if(!isOperator(postfix.charAt(i))){
                temp = new Node(postfix.charAt(i));
                st.push(temp);
            }
            else{
                temp = new Node(postfix.charAt(i));
 
                t1 = st.pop();
                t2 = st.pop();
 
                temp.left = t2;
                temp.right = t1;
 
                st.push(temp);
            }
 
        }
        temp = st.pop();
        return temp;
    }
    public static void inorder(Node root){
        if(root==null) return;
 
        inorder(root.left);
        System.out.print(root.data);
        inorder(root.right);
    }
    public static void main(String[] args) {
        String postfix = "ABC*+D/";
 
        Node r = expressionTree(postfix);
        inorder(r);
    }
}

import java.util.Stack;

class Node{

char data;

Node left,right;

public Node(char data){

this.data = data;

left = right = null;

}

public class Main {

public static boolean isOperator(char ch){

if(ch=='+' || ch=='-'|| ch=='*' || ch=='/' || ch=='^'){

return true;

}

return false;

}

public static Node expressionTree(String postfix){

Stack<Node> st = new Stack<Node>();

Node t1,t2,temp;

for(int i=0;i<postfix.length();i++){

if(!isOperator(postfix.charAt(i))){

temp = new Node(postfix.charAt(i));

st.push(temp);

}

else{

temp = new Node(postfix.charAt(i));

t1 = st.pop();

t2 = st.pop();

temp.left = t2;

temp.right = t1;

st.push(temp);

}

temp = st.pop();

return temp;

}

public static void inorder(Node root){

if(root==null) return;

inorder(root.left);

System.out.print(root.data);

inorder(root.right);

}

public static void main(String[] args) {

String postfix = "ABC*+D/";

Node r = expressionTree(postfix);

inorder(r);

}

Describe specifically how the algorithm works

Assume that one element is read at a time. If the element is an operand, we create a node and push it onto a stack. If the element is an operator, pop the two trees T1 and T2 from the stack (T1 is popped first) and form a new tree whose root is the operator and its left and right children point to T2 respectively. and T1. This new node is then pushed onto the stack. For example, let’s say the input is ABC*+D/. The first three symbols are operands, so create tree nodes and push pointers to them on a stack as shown below.