Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Given a postfix expression, construct an expression tree. Looking code code review, optimizations and best practices.

public class ExpressionTree {

    private final String postfix;
    private TreeNode root;

    /**
     * Takes in a valid postfix expression and later its used to construct the expression tree.
     * The posfix expression, if invalid, leads to invalid results 
     * 
     * @param postfix   the postfix expression.
     */
    public ExpressionTree(String postfix) {
        if (postfix == null) { throw new NullPointerException("The posfix should not be null"); }
        if (postfix.length() == 0)  { throw new IllegalArgumentException("The postfix should not be empty"); } 
        this.postfix = postfix;
    }

    private static class TreeNode {
        TreeNode left;
        char ch;
        TreeNode right;

        TreeNode(TreeNode left, char ch, TreeNode right) {
            this.left = left;
            this.ch = ch;
            this.right = right;
        }
    }


    private boolean isOperator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/';
    }


    /**
     * Constructs an expression tree, using the postfix expression
     */
    public void createExpressionTree() {
        final Stack<TreeNode> nodes = new Stack<TreeNode>();
        for (int i = 0; i < postfix.length(); i++) {
            char ch  = postfix.charAt(i);
            if (isOperator(ch)) {
               TreeNode rightNode = nodes.pop();
               TreeNode leftNode = nodes.pop();
               nodes.push(new TreeNode(leftNode, ch, rightNode));
            } else {
                nodes.add(new TreeNode(null, ch, null));
            }
        }
        root = nodes.pop();
    }


    /**
     * Returns the prefix notation
     * 
     * @return the prefix notation
     */
    public String prefix() {
        if (root == null) {
            throw new NoSuchElementException("The root is empty, the tree has not yet been constructed.");
        }

        final StringBuilder prefix = new StringBuilder();
        preOrder(root, prefix);
        return prefix.toString();
    }

    private void preOrder(TreeNode node, StringBuilder prefix) {
        if (node != null) {
            prefix.append(node.ch);
            preOrder(node.left, prefix);
            preOrder(node.right, prefix);
        }
    }

    /**
     * Returns the infix expression
     * 
     * @return  the string of infix.
     */
    public String infix() {
        if (root == null) {
            throw new NoSuchElementException("The root is empty, the tree has not yet been constructed.");
        }
        final StringBuilder infix = new StringBuilder();
        inOrder(root, infix);
        return infix.toString();
    }

    private void inOrder(TreeNode node, StringBuilder infix) {
        if (node != null) {
            inOrder(node.left, infix);
            infix.append(node.ch);
            inOrder(node.right, infix);
        }
    }


    public static void main(String[] args) {
        ExpressionTree expressionTree1 = new ExpressionTree("AB*CD/+");
        expressionTree1.createExpressionTree();
        assertEquals("+*AB/CD", expressionTree1.prefix());
        assertEquals("A*B+C/D", expressionTree1.infix());

        ExpressionTree expressionTree2 = new ExpressionTree("ABC+*D/");
        expressionTree2.createExpressionTree();
        assertEquals("/*A+BCD", expressionTree2.prefix());
        assertEquals("A*B+C/D", expressionTree2.infix());        

        ExpressionTree expressionTree3 = new ExpressionTree("ABCD/+*");
        expressionTree3.createExpressionTree();
        assertEquals("*A+B/CD", expressionTree3.prefix());
        assertEquals("A*B+C/D", expressionTree3.infix());
    }
}
share|improve this question
    
It way not be part of your problem definition, but the infix notation you currently output is ambiguous. You should consider adding brackets: "ABC+*D/" => "((A*(B+C))/D)" –  RoToRa Apr 11 at 15:14

1 Answer 1

Make your structs immutable
TreeNode is a helper structure, with public members, which is fine, but you better make them final, so you know they won't be changed after the object is created.

Choose your validations
Don't throw NullPointerException on your own. It may confuse a future debugger. Either throw an IllegalArgumentException or let the runtime throw the NullPointerException for you.

Choose your comments
Most of your comments do not add much to the methods, and are therefore redundant. Let the names of the method and variables do the work for you. If you feel the name prefix is not clear enough on its own, it is better to rename it (maybe to toPrefixNotation()) and then you can safely remove your comments.

Being nice is better than being strict
Unless there is some requirement restriction, I don't think you need to throw an exception if root is null - why not simply call createExpressionTree() instead of telling the developer he should?
Since there is no meaning for calling createExpressionTree() twice (postfix is final...), you might as well hide it altogether, and call it when needed.

Use the power of String
Use String#indexOf to make isOperator more succinct:

private boolean isOperator(char c) {
    return "+-*/".indexOf(c) != -1
}
share|improve this answer
1  
+1 for choose your validations, +1 for methods explicit names, +1 for automatic call to createExpressionTree(). -1 I don't really like using indexOf() like this, because it gets away from its initial meaning, thus reducing readability. Also it might be worse in terms of performance, but it's just a guess here. –  Joffrey Apr 11 at 13:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.