Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Please Help Me complete the code. The starter code is provided below. It just need the methods. Please Help me complete it. Thank you. FYI:
Please Help Me complete the code. The starter code is provided below. It just need the methods. Please Help me complete it. Thank you. FYI: Dont use your own code. Use the starter code
Starter code:
Starter Code:
import java.util.List; import java.util.LinkedList; import java.util.Scanner; import java.io.FileNotFoundException; import java.io.File; /** Class to store a node of expression tree For each internal node, element contains a binary operator List of operators: +|*|-|/|%|^ Other tokens: (|) Each leaf node contains an operand (long integer) */ public class Expression { public enum TokenType { // NIL is a special token that can be used to mark bottom of stack PLUS, TIMES, MINUS, DIV, MOD, POWER, OPEN, CLOSE, NIL, NUMBER } public static class Token { TokenType token; int priority; // for precedence of operator Long number; // used to store number of token = NUMBER String string; Token(TokenType op, int pri, String tok) { token = op; priority = pri; number = null; string = tok; } // Constructor for number. To be called when other options have been exhausted. Token(String tok) { token = TokenType.NUMBER; number = Long.parseLong(tok); string = tok; } boolean isOperand() { return token == TokenType.NUMBER; } public long getValue() { return isOperand() ? number : 0; } public String toString() { return string; } } Token element; Expression left, right; // Create token corresponding to a string // tok is "+" | "*" | "-" | "/" | "%" | "^" | "(" | ")"| NUMBER // NUMBER is either "0" or "[-]?[1-9][0-9]* static Token getToken(String tok) { // To do Token result; switch(tok) { case "+": result = new Token(TokenType.PLUS, 1, tok); // modify if priority of "+" is not 1 break; // Complete rest of this method default: result = new Token(tok); break; } return result; } private Expression() { element = null; } private Expression(Token oper, Expression left, Expression right) { this.element = oper; this.left = left; this.right = right; } private Expression(Token num) { this.element = num; this.left = null; this.right = null; } // Given a list of tokens corresponding to an infix expression, // return the expression tree corresponding to it. public static Expression infixToExpression(ListIn this project, you will be using stacks to parse/evaluate arithmetic expressions. To parse infix exprssions, use the Shunting Yard algorithm of Dijkstra (discussed in class) Wikipedia page: https://en.wikipedia.org/wiki/Shunting-yard algorithm Algorithms to evaluate postfix expressions and expression trees were discussed in class Use Stack or ArrayDeque from the Java library for the stacks. Do not code your own stack Starter code Expression.java is provided. Add additional fields, methods, clsses as needed Do not change the name of the class or signatures of public methods The following methods need to be completed. No error checking is required. If the expressions passed are valid, then the methods should work correctly Given invalid expressions, your program can return wrong values, print error messages, or throw exceptions Method to convert String to a Token: The string holds exactly one token, with no extra spaces before or after the token Possible tokens are: Operators: PLUS ( " +"), TIMES ("*"), MINUS ("-"), DIV ("/"), MOD ("%"), POWER ("^") Parentheses: OPEN (" ("), CLOSE (")") Number: NUMBER (any valid string that represents an integer) Assume that if a token is not an operator or a parenthesis, then it is a number. Use Long.parseLong (tok) to convert string to long. Signature: static Token getToken(String tok) 1 Tokens have a field "priority" that can be used to store precedence of operators during parsing. Precedence: {^} > {*, /, %} > {+, -). Assume that all operators are left associative. Assign your own values to priority of tokens Field "number" is used to store the value of NUMBER token. A token "NIL" is defined for internal use and it does not correspond to any token in the expressions.It is a convenient token to mark bottom of stack. Method to convert an iniix expression given as a 11st of tokens into an expression tree: Given an infix expression as a list of tokens, return its corresponding expression tree. Signature: public static Expression infixToExpression(Listexp) { // To do return null; } // Given a list of tokens corresponding to an infix expression, // return its equivalent postfix expression as a list of tokens. public static List infixToPostfix(List exp) { // To do return null; } // Given a postfix expression, evaluate it and return its value. public static long evaluatePostfix(List exp) { // To do return 0; } // Given an expression tree, evaluate it and return its value. public static long evaluateExpression(Expression tree) { // To do return 0; } // sample main program for testing public static void main(String[] args) throws FileNotFoundException { Scanner in; if (args.length > 0) { File inputFile = new File(args[0]); in = new Scanner(inputFile); } else { in = new Scanner(System.in); } int count = 0; while(in.hasNext()) { String s = in.nextLine(); List infix = new LinkedList(); Scanner sscan = new Scanner(s); int len = 0; while(sscan.hasNext()) { infix.add(getToken(sscan.next())); len++; } if(len > 0) { count++; System.out.println("Expression number: " + count); System.out.println("Infix expression: " + infix); Expression exp = infixToExpression(infix); List post = infixToPostfix(infix); System.out.println("Postfix expression: " + post); long pval = evaluatePostfix(post); long eval = evaluateExpression(exp); System.out.println("Postfix eval: " + pval + " Exp eval: " + eval + " "); } } } }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started