Converting from reverse Polish notation(RPN) into a tree form?

Question

I dont understand how to do this? Can someone please explain how to convert, for example, ac+ ac+*into a binary tree form?? I need to turn this expression into a full parenthesized string representation of this tree.

Answer 1

You need to build the tree just the way you would process the postfix input. However, when you encounter an operation, instead of calculating the value, you make the arguments on the stack the children of the operator node. Then you push it on the stack (just as you would push the calculation result on the stack in postfix notation).

At the end, the only element on the stack should be the root of the complete tree.

Should look roughly like this:

public class Node {
    char value;
    Node left, right;

    public Node(char value) {
        this.value = value;
    }

    public static Node parseUpn(String s) {
        Stack<Node> stack = new Stack<Node>();

        for (char c: s.toCharArray()) {
            if (c != ' ') {
                Node node = new Node(c);
                if ("+-*/".indexOf(c) != -1) { 
                    node.right = stack.pop();
                    node.left = stack.pop();
                }
            }
            stack.push(node);
        }

        if (stack.size() != 1) {
            throw new RuntimeException("Expected exactly one stack value.");
        }
        return stack.pop();
    }

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

Answer 2

I am going to use a class Node to represent the nodes of the tree. All my node needs is the following:

public interface Node<T> {
    public void addChild(Node<T>);
}

We will assume I have an implementing class TreeNode<T> that has a constructor public TreeNode(T value).

I am going to assume that you have already chopped up the string and parsed all the characters in some other method, so that you have an array of Tokens that represent the expression:

public interface Token {

    /**
     * @return The number of operands this token takes.
     * A return value of 0 indicates this token does not
     * take any operands.
     */
    public int getOperandCount();

}

(It may be desirable to include additional methods in your classes, so that you can read the values from the tree, but that is not strictly necessary to build it.)

Also,

public class MalformedExpressionException extends IllegalArgumentException{
    public MalformedExpressionException(String reason){/* [ ... ] */};
    // [ ... ]
}

With that out of the way, the following function will produce you a tree, returning its root node.

public static Node<Token> makeTree(Token [] tokens){
    Stack<Node<Token>> stack = new Stack<>();

    try{
        for(Token t:tokens){
            Node<Token> node = new TreeNode<Token>(t);
            for(int idx = 0; idx < t.getOperandCount(); idx++)
                node.addChild(stack.pop());
            stack.push(node);
        }
    }catch (EmptyStackException e){
        throw new MalformedExpressionException("too few operands");
    }

    if(stack.size() != 1)
        throw new MalformedExpressionException("too many operands");

    return stack.pop();
}