Question

Expand EquationBinaryTree to include a populate method for prefix and postfix. The populate methods should not convert to the other type before populating the tree nodes. Add Big-O notation to all 3 populate methods.

//ab+ = (a+b)
   public void populateFromPostfix(String equation)
   {
       //does not require recursion to solve
      
      
   }
  
   //+ab = (a+b)
   public void populateFromPrefix(String equation)
    {
       //does not require recursion to solve
      
   }

Answer 1

Please let me know if you have any doubts or you want me to modify the answer. And if you find this answer useful then don't forget to rate my answer as thumps up. Thank you! :)

import java.util.*;

public class EquationBinaryTree {
    private EquationTreeNode root;
    private String keyword;
    private String infix = "Infix";
    private String postfix = "Postfix";
    private String prefix = "Prefix";
    private String infixFormula, postfixFormula, prefixFormula;
    private Scanner scan = new Scanner(System.in);

    public EquationBinaryTree()
    {
        root = null;
    }
    private class EquationTreeNode{
        String value;
        EquationTreeNode left;
        EquationTreeNode right;
        public EquationTreeNode(String v)
        {
            value = v;
            left = null;
            right = null;
        }
        public String toString()
        {
            return value.toString();
        }
    }

    public void populateFromInfix(String inf)
    {
        root = populateInfix(inf);
    }

    private EquationTreeNode populateInfix(String inf)
    {
        EquationTreeNode node;
        if(inf.length() == 1)
        {
            node = new EquationTreeNode(inf);
        }
        else
        {
            String[] parts = infixConversion(inf);
            node = new EquationTreeNode(parts[2]);
            if(!parts[0].equals(""))
                node.left = populateInfix(parts[0]);
            if(!parts[1].equals(""))
                node.right = populateInfix(parts[1]);
        }
        return node;
    }
    private String[] infixConversion(String inf)
    {
        String[] parts = new String[3];
        inf = inf.substring(1, inf.length()-1);
        int parenCount = 0;
        int i = 0;
        for(i = 0; i < inf.length(); i++)
        {
            if(inf.charAt(i) == '(')
                parenCount++;
            else if(inf.charAt(i) == ')')
                parenCount--;
            if(parenCount == 0)
                break;
        }
        parts[0] = inf.substring(0, i+1);
        parts[1] = inf.substring(i+2);
        parts[2] = ""+inf.charAt(i+1);
        return parts;
    }

    public String printInfix()
    {
        String output = "";
        output += printInfixFunction(root);
        return output;
    }
    private String printInfixFunction(EquationTreeNode node)
    {
        String output = "";
        if(node.left != null)
        {
            output += "(";
            output += printInfixFunction(node.left);
        }
        output += node;
        if(node.right != null)
        {
            output += printInfixFunction(node.right);
            output += ")";
        }
        return output;
    }

    public String printPostfix()
    {
        String output = "";
        output += printPostFunction(root);
        return output;
    }
    private String printPostFunction(EquationTreeNode node)
    {
        String output = "";
        if(node.left != null)
        {
            output += printPostFunction(node.left);
        }
        if(node.right != null)
        {
            output += printPostFunction(node.right);
        }
        output += node;
        return output;
    }
    public String printPrefix()
    {
        String output = "";
        output += printPrefixFunction(root);
        return output;
    }
    private String printPrefixFunction(EquationTreeNode node)
    {
        String output = "";
        output += node;
        if(node.left != null)
        {
            output += printPrefixFunction(node.left);
        }
        if(node.right != null)
        {
            output += printPrefixFunction(node.right);
        }
        return output;
    }

    private boolean isOperator(char ch)
    {
        if(ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^' || ch == '%')
            return true;
        return false;
    }

    public void populateFromPostfix(String postfix)
    {
        root = populatePostFunction(postfix);
    }

    private EquationTreeNode populatePostFunction(String postfix){
        Stack<EquationTreeNode> treeStack = new Stack<>();
        EquationTreeNode node;

        char[] charArray = postfix.toCharArray();
        for(int i = 0; i < charArray.length; i++){
            if(!isOperator(charArray[i])){
                String value = String.valueOf(charArray[i]);
                node = new EquationTreeNode(value);
                treeStack.push(node);
            }else
            {
                String value = String.valueOf(charArray[i]);
                node = new EquationTreeNode(value);
                node.right = treeStack.pop();
                node.left = treeStack.pop();
                treeStack.push(node);
            }
        }
        node = treeStack.pop();
        return node;
    }

    public void populateFromPrefix(String prefix)
    {
        root = PrefixFunction(prefix);
    }

    private EquationTreeNode PrefixFunction(String prefix){
        Stack<EquationTreeNode> treeStack = new Stack<>();
        EquationTreeNode node, node1, node2;

        char[] charArray = prefix.toCharArray();
        for(int i = charArray.length -1; i != -1; i--){
            if(!isOperator(charArray[i])){
                String value = String.valueOf(charArray[i]);
                node = new EquationTreeNode(value);
                treeStack.push(node);
            }else
            {
                node1 = treeStack.pop();
                node2 = treeStack.pop();
                String value = String.valueOf(charArray[i]);
                node = new EquationTreeNode(value);
                node.left = node1;
                node.right = node2;
                treeStack.push(node);
            }
        }
        node = treeStack.pop();
        return node;
    }

    public void input(){
        System.out.println("Enter the keyword (Infix/Postfix/Prefix) of the expression you would like to convert:");
        keyword = scan.nextLine();
        while(!(keyword.equalsIgnoreCase(infix) || keyword.equalsIgnoreCase(postfix) || keyword.equalsIgnoreCase(prefix))){
            System.out.println("Please enter a valid keyword.");
            keyword = scan.nextLine();
        }
        if(keyword.equalsIgnoreCase(infix)){
            System.out.println("Please enter your Infix Expression: (Must include parentheses)");
            infixFormula = scan.nextLine();
            populateFromInfix(infixFormula);
            printAll();
        }else if(keyword.equalsIgnoreCase(postfix)){
            System.out.println("Please enter your Postfix Expression:");
            postfixFormula = scan.nextLine();
            populateFromPostfix(postfixFormula);
            printAll();
        }else if(keyword.equalsIgnoreCase(prefix)){
            System.out.println("Please enter your Prefix Expression:");
            prefixFormula = scan.nextLine();
            populateFromPrefix(prefixFormula);
            printAll();
        }
    }

    public void printAll(){
        System.out.println("Infix   : " + printInfix());
        System.out.println("Postfix : " + printPostfix());
        System.out.println("Prefix : " + printPrefix());
    }

    public static void main(String[] args) {
        EquationBinaryTree ebt = new EquationBinaryTree();
        ebt.input();
    }
}