In Java,  Complete the incomplete method of ExpressionTree.java. The incomplete methods are private Node parsePrefix(Scanner input) // Required public void parseInfix(String string) // Optional public void parsePostfix(String string) // Optional Implementations of parseInfix and parsePostfix require use of a stack. Implementation of parsePrefix does not. Read all of the ExpressionTree.java file before starting your implementation, so that you see the helper methods that are provided and get an idea of the context for your implementation.  Although not needed for your implementation, you should be sure you understand how the toStringPrefix, toStringInfix, and toStringPostfix methods work. Note: The main() method accepts a single String as its argument. The String should be a prefix, infix, or postfix mathematical expression with no characters other than operators (+, -, *, and /) and operands (single characters a-z).  As written, the main() method calls parsePrefix() to create an expression tree from a prefix expression. The main() method then prints the expression tree in prefix, infix, and postfix order, yielding prefix, infix, and postfix expressions that represent the same calculation. Given the (prefix expression) argument "*-ab+cd", the main() method should print input = *-ab+cd prefix = *-ab+cd infix = a-b*c+d postfix = ab-cd+* ExpressionTree.java import java.util.Scanner; import java.util.Stack; // Needed for parseInfix and parsePostfix public class ExpressionTree {     public class Node {         char element;         Node left, right;                  public Node(char element) {             this.element = element;             this.left = null;             this.right = null;         }                  public Node(char element, Node left, Node right) {             this.element = element;             this.left = left;             this.right = right;         }     }          private Node root;          public static void main(String[] args) {         ExpressionTree expressionTree = new ExpressionTree();         String expression = "*-ab+cd";         if (args.length != 0) {             expression = args[0];         }         System.out.println("  input = " + expression);         expressionTree.parsePrefix(expression);         System.out.println(" prefix = " + expressionTree.toStringPrefix());         System.out.println("  infix = " + expressionTree.toStringInfix());         System.out.println("postfix = " + expressionTree.toStringPostfix());     }          /**      * Sets root to the root of the expression tree.      * @param string is a prefix expression to be parsed.      */     public void parsePrefix(String string) {         Scanner input = new Scanner(string);         input.useDelimiter(""); // Each token returned is a single character string                  root = parsePrefix(input);     }     /**      * @param input is the sequence of single character strings (a prefix expression) to be parsed.      * @return the root node of the expression tree for the input      */     private Node parsePrefix(Scanner input) {         // Implement this recursive method     }          /**      * Sets root to the root of the expression tree.      * @param string is an infix expression to be parsed.      */     public void parseInfix(String string) {         // Optional implementation. Note: Use the Java Stack class.     }          /**      * Sets root to the root of the expression tree.      * @param string is a postfix expression to be parsed.      */     public void parsePostfix(String string) {         // Optional implementation. Note: Use the Java Stack class.     }          private Boolean isOperator(char aChar) {         return "+-*/^%".contains(Character.toString(aChar));     }          public String toStringPrefix() {         return toStringPrefix(root);     }          private String toStringPrefix(Node node) {         String result = "";         if (node == null) {             return result;         }         result += String.valueOf(node.element);         result += toStringPrefix(node.left);         result += toStringPrefix(node.right);                  return result;         }          public String toStringInfix() {         return toStringInfix(root);     }          private String toStringInfix(Node node) {         String result = "";         if (node == null) {             return result;         }         result += toStringInfix(node.left);         result += String.valueOf(node.element);         result += toStringInfix(node.right);                  return result;         }          public String toStringPostfix() {         return toStringPostfix(root);     }          private String toStringPostfix(Node node) {         String result = "";         if (node == null) {             return result;         }         result += toStringPostfix(node.left);         result += toStringPostfix(node.right);         result += String.valueOf(node.element);                  return result;         } }

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question

In Java, 

Complete the incomplete method of ExpressionTree.java. The incomplete methods are

  • private Node parsePrefix(Scanner input) // Required
  • public void parseInfix(String string) // Optional
  • public void parsePostfix(String string) // Optional

Implementations of parseInfix and parsePostfix require use of a stack. Implementation of parsePrefix does not.

Read all of the ExpressionTree.java file before starting your implementation, so that you see the helper methods that are provided and get an idea of the context for your implementation.  Although not needed for your implementation, you should be sure you understand how the toStringPrefixtoStringInfix, and toStringPostfix methods work.

Note:

  • The main() method accepts a single String as its argument. The String should be a prefix, infix, or postfix mathematical expression with no characters other than operators (+, -, *, and /) and operands (single characters a-z). 
  • As written, the main() method calls parsePrefix() to create an expression tree from a prefix expression.
  • The main() method then prints the expression tree in prefix, infix, and postfix order, yielding prefix, infix, and postfix expressions that represent the same calculation.
  • Given the (prefix expression) argument "*-ab+cd", the main() method should print

input = *-ab+cd prefix = *-ab+cd infix = a-b*c+d postfix = ab-cd+*

ExpressionTree.java

import java.util.Scanner;
import java.util.Stack; // Needed for parseInfix and parsePostfix

public class ExpressionTree {
    public class Node {
        char element;
        Node left, right;
        
        public Node(char element) {
            this.element = element;
            this.left = null;
            this.right = null;
        }
        
        public Node(char element, Node left, Node right) {
            this.element = element;
            this.left = left;
            this.right = right;
        }
    }
    
    private Node root;
    
    public static void main(String[] args) {
        ExpressionTree expressionTree = new ExpressionTree();
        String expression = "*-ab+cd";
        if (args.length != 0) {
            expression = args[0];
        }
        System.out.println("  input = " + expression);
        expressionTree.parsePrefix(expression);
        System.out.println(" prefix = " + expressionTree.toStringPrefix());
        System.out.println("  infix = " + expressionTree.toStringInfix());
        System.out.println("postfix = " + expressionTree.toStringPostfix());
    }
    
    /**
     * Sets root to the root of the expression tree.
     * @param string is a prefix expression to be parsed.
     */
    public void parsePrefix(String string) {
        Scanner input = new Scanner(string);
        input.useDelimiter(""); // Each token returned is a single character string
        
        root = parsePrefix(input);
    }

    /**
     * @param input is the sequence of single character strings (a prefix expression) to be parsed.
     * @return the root node of the expression tree for the input
     */
    private Node parsePrefix(Scanner input) {
        // Implement this recursive method
    }
    
    /**
     * Sets root to the root of the expression tree.
     * @param string is an infix expression to be parsed.
     */
    public void parseInfix(String string) {
        // Optional implementation. Note: Use the Java Stack class.
    }
    
    /**
     * Sets root to the root of the expression tree.
     * @param string is a postfix expression to be parsed.
     */
    public void parsePostfix(String string) {
        // Optional implementation. Note: Use the Java Stack class.
    }
    
    private Boolean isOperator(char aChar) {
        return "+-*/^%".contains(Character.toString(aChar));
    }
    
    public String toStringPrefix() {
        return toStringPrefix(root);
    }
    
    private String toStringPrefix(Node node) {
        String result = "";
        if (node == null) {
            return result;
        }
        result += String.valueOf(node.element);
        result += toStringPrefix(node.left);
        result += toStringPrefix(node.right);
        
        return result;    
    }
    
    public String toStringInfix() {
        return toStringInfix(root);
    }
    
    private String toStringInfix(Node node) {
        String result = "";
        if (node == null) {
            return result;
        }
        result += toStringInfix(node.left);
        result += String.valueOf(node.element);
        result += toStringInfix(node.right);
        
        return result;    
    }
    
    public String toStringPostfix() {
        return toStringPostfix(root);
    }
    
    private String toStringPostfix(Node node) {
        String result = "";
        if (node == null) {
            return result;
        }
        result += toStringPostfix(node.left);
        result += toStringPostfix(node.right);
        result += String.valueOf(node.element);
        
        return result;    
    }
}

Expert Solution
Step 1

The algorithm of the code is given below:-

  1. Define a Node class that represents a node in the expression tree.
  2. Define a Main class that contains methods for parsing prefix, infix, and postfix expressions and converting them to string format.
  3. In the Node class, define a constructor that takes an element, a left child node, and a right child node as arguments. This constructor initializes the instance variables.
  4. In the Main class, define a private Node parsePrefix(Scanner input) method that takes a Scanner object as an argument. This method recursively parses a prefix expression and returns the root node of the resulting expression tree.
  5. In the parsePrefix method, check if the input has no more elements. If so, return null.
  6. Read the next character from the input.
  7. If the character is not an operator, create a new node with the character as its element and return it.
  8. Otherwise, recursively call the parsePrefix method to create the left and right child nodes, then create a new node with the operator as its element and the left and right child nodes as its children.
  9. In the Main class, define a parseInfix method that takes an infix expression as a string argument. This method uses a stack to parse the expression and returns the root node of the resulting expression tree.
  10. Create a new Stack object to store nodes.
  11. Create a Scanner object from the input string and set the delimiter to the empty string.
  12. While the input has more elements, read the next character.
  13. If the character is not an operator, create a new node with the character as its element and push it onto the stack.
  14. Otherwise, pop the top two nodes from the stack and create a new node with the operator as its element and the two nodes as its left and right children. Push the new node onto the stack.
  15. When there are no more elements in the input, the last node on the stack is the root node of the expression tree.
  16. In the Main class, define a parsePostfix method that takes a postfix expression as a string argument. This method is similar to the parseInfix method but reads the input from right to left.
  17. In the Main class, define a toStringPrefix method that returns the prefix string representation of the expression tree.
  18. In the toStringPrefix method, recursively traverse the expression tree in prefix order and append the element of each node to a string.
  19. In the Main class, define a toStringInfix method that returns the infix string representation of the expression tree.
  20. In the toStringInfix method, recursively traverse the expression tree in infix order and append the element of each node to a string.
  21. In the Main class, define a toStringPostfix method that returns the postfix string representation of the expression tree.
  22. In the toStringPostfix method, recursively traverse the expression tree in postfix order and append the element of each node to a string.

 

trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 6 steps with 8 images

Blurred answer
Knowledge Booster
Types of trees
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education