Answered step by step
Verified Expert Solution
Link Copied!

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

image text in transcribed

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(List exp) { // 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 + " "); } } } }
In 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(List exp) ( > Method to convert an infix expression into a postfix expression: Given an infix expression as a list of tokens, return its equivalent postfix expression. Signature: public static List infixToPostfix(List exp) t... > Method to evaluate a postfix expression: Given a postfix expression, evaluate it and return its value Signature: public static long evaluatePostfix(List exp) { > Method to evaluate an expression tree: Given an expression tree, evaluate it and return its value. Signature: public static long evaluateExpression (Expression tree) f... ) In 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(List exp) ( > Method to convert an infix expression into a postfix expression: Given an infix expression as a list of tokens, return its equivalent postfix expression. Signature: public static List infixToPostfix(List exp) t... > Method to evaluate a postfix expression: Given a postfix expression, evaluate it and return its value Signature: public static long evaluatePostfix(List exp) { > Method to evaluate an expression tree: Given an expression tree, evaluate it and return its value. Signature: public static long evaluateExpression (Expression tree) f... )

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Intranet And Web Databases For Dummies

Authors: Paul Litwin

1st Edition

0764502212, 9780764502217

More Books

Students also viewed these Databases questions

Question

36: How do biology and environment interact in our sleep patterns?

Answered: 1 week ago

Question

Highlight the key challenges faced by MNEs when internationalising.

Answered: 1 week ago