*In Java* I have a method header: public static TreeNode<String> buildTreeFromSt

Question

*In Java*

I have a method header:

public static TreeNode<String> buildTreeFromString(String expr)

and I need to have this method take an expression written in postfix notation as a String and return back the root node of an expression tree built from that String. The algorithm for building an expression tree from a String is a non-recursivealgorithm that uses a Stack to direct the building of a tree.

Here is what I need the code to do:

Turn the String into an array of operands and operators
Start with an empty Stack of TreeNodes named exprStack
For each element of that array, moving from left to right:
    If the element is an operator:
       Create a new TreeNode containing that operator
       Pop the first element off exprStack, make it the right child of the new TreeNode
       Pop the next element off exprStack, make it the left child of the new TreeNode
       Push the new TreeNode you just built onto the exprStack
    Otherwise (if the element is an operand):
       Create a new TreeNode containing that operand
       Push the new TreeNode onto the exprStack

Explanation / Answer

public class Tree
{

    private final String postfix;
    private TreeNode root;

    public Tree(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 == '/';
    }

    public void createTree() {
        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();
    }

    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);
        }
    }

  
    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)
    {
        Tree Tree1 = new Tree("AB*CD/+");
        Tree1.createTree();
        assertEquals("+*AB/CD", Tree1.prefix());
        assertEquals("A*B+C/D", Tree1.infix());

        Tree Tree2 = new Tree("ABC+*D/");
        Tree2.createTree();
        assertEquals("/*A+BCD", Tree2.prefix());
        assertEquals("A*B+C/D", Tree2.infix());      

        Tree Tree3 = new Tree("ABCD/+*");
        Tree3.createTree();
        assertEquals("*A+B/CD", Tree3.prefix());
        assertEquals("A*B+C/D", Tree3.infix());
    }
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.