Create a Binary Tree from postfix expression

Question

Let's say I have the following postfix expression : 5372-*-

I want to create a binary tree from this expression. My algoritm is : If my char is number put it into a stack if it is an operator pop two elements from the stack and make them the childs of the operator. Then push the operator into the stack. Which seems like it is working but I cannot manage to connect the little trees that I create.

My current code is :

public void myInsert(char ch, Stack s) {
    if (Character.isDigit(ch)) // initial cond.
        s.push(ch);
    else {
        TreeNode tParent = new TreeNode(ch);
        TreeNode t = new TreeNode(s.pop());
        TreeNode t2 = new TreeNode(s.pop());
        tParent.right = t;
        tParent.left = t2;
        s.push(ch);
        System.out.println("par" + tParent.ch);
        System.out.println("cright" + tParent.right.ch);
        System.out.println("cleft" + tParent.left.ch);
    }
}

My test class :

Stack stree = new Stack();

    BST b = new BST();
    String str = "5-3*(7-2)";
    String postfix = b.convertToPosFix(str);
    System.out.println(postfix);

    for (char ch : postfix.toCharArray()) {
         b.myInsert(ch, stree);

    }

My output is :

par-
cright2
cleft7
par*
cright-
cleft3
par-
cright*
cleft5

Answer 1

Use a Stack of TreeNodes, not a Stack of chars. You have to combine the TreeNodes after all and not the chars:

public void myInsert(char ch, Stack<TreeNode> s) {
    if (Character.isDigit(ch)) {
        // leaf (literal)
        s.push(new TreeNode(ch));
    } else {
        // operator node
        TreeNode tParent = new TreeNode(ch);

        // add operands
        tParent.right = s.pop();
        tParent.left = s.pop();

        // push result to operand stack
        s.push(tParent);
    }
}

TreeNode

public class TreeNode {
    public TreeNode right = null;
    public TreeNode left = null;
    public final char ch;

    TreeNode(char ch) {
        this.ch = ch;
    }

    @Override
    public String toString() {
        return (right == null && left == null) ? Character.toString(ch) : "(" + left.toString()+ ch + right.toString() + ")";
    }

}

main

public static TreeNode postfixToTree(String s) {
    Stack<TreeNode> stree = new Stack<>();

    BST b = new BST();
    for (char ch : s.toCharArray()) {
        b.myInsert(ch, stree);
    }
    return stree.pop();
}

public static void main(String[] args) {
    System.out.println(postfixToTree("5372-*-"));
    System.out.println(postfixToTree("512+4*+3−"));
    System.out.println(postfixToTree("51*24*+"));
}

This will print

(5-(3*(7-2)))
((5+((1+2)*4))−3)
((5*1)+(2*4))