QuestionQuestion

Transcribed TextTranscribed Text

Data Structures Assignment 2 1 Motivation In lecture, we discussed an stack algorithm for converting an infix expression to a postfix expression, and another for evaluating postfix expressions. We briefly described how one might pipeline these algorithms to evaluate an infix expression in a single pass using two stacks, without generating the full postfix expression in between. In this assignment, you will be implementing this combined algorithm. Your completed program will evaluate an infix arithmetic expression using two stacks. You are provided with the skeleton of InfixExpressionEvaluator. This class accepts input from an InputStream and parses it into tokens. When it detects an invalid token, it throws an ExpressionError to end execution. To facilitate ease of use, this class also contains a main method. This method instantiates an object of type InfixExpressionEvaluator to read from System.in, then evaluates whatever expression is typed. It also catches any potential ExpressionErrors and prints the reason for the error. InfixExpressionEvaluator uses composition to store the operator and operand stacks, and calls several private helper methods to manipulate these stacks when handling various tokens. You will need to complete these helper methods and add error checking to ensure the expression is valid. 2 Tasks First, carefully read the provided code. 2.1 Implement helper methods, As tokens are parsed, helper methods are called to handle them. In the included code, these helper methods do not do anything. You must implement the following methods to handle the various types of tokens. • handleOperand(double): Each time the evaluator encounters an operand, it passes it (as a double) to this method, which should handle it by manipulating the operand and/or operator stack according to the infix-to-postfix and postfix-evaluation algorithms. 1 • handleOperator(char): Each time the evaluator encounters an operator, it passes it (as a char) to this method, which should handle it by manipulating the operand and/or operator stack according to the infix-to-postfix and postfix-evaluation algorithms. Each of the following operators must be supported. Follow standard operator precedence. You can assume that - is always the binary subtraction operator (e.g., no negative operands). + Addition - Subtraction * Multiplication / Division ^ Exponentiation • handleOpenBracket(char): Each time the evaluator encounters an open bracket, it passes it (as a char) to this method, which should handle it by manipulating the operand and/or operator stack according to the infix-to-postfix and postfix-evaluation algorithms. You must support both round brackets () and curly brackets {}. These brackets can be used interchangeably, but must be nested properly—a ( cannot be closed with a }, and vice-versa. • handleCloseBracket(char): Each time the evaluator encounters a close bracket, it passes it (as a char) to this method, which should handle it by manipulating the operand and/or operator stack according to the infix-to-postfix and postfix-evaluation algorithms. • handleRemainingOperators(): When the evaluator encounters the end of the expression, it calls this method to handle the remaining operators on the operator stack. 2.2 Error checking, 30 points This task requires that you modify your program to account for errors in the input expression. The provided code throws ExpressionError when encountering an unknown token (for instance, &). You must modify your program to throw this exception (with an appropriate message) whenever the expression is invalid. This requires careful consideration of all the possible syntax errors. What if an operand follows another operand? An operator following an open bracket? What about brackets that do not nest properly? All such syntax errors must be handled using ExpressionError. Hints: 1. Which pairs of adjacent token types are valid vs. invalid? Create a data member that tracks the most recent token type. When handling a new token, first ensure that it is legal for the current token type to follow the previous token type. 2. Trace through the algorithm by hand using expressions with various bracket errors. When during the process can each error be detected?

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

package.a2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
* This class uses two stacks to evaluate an infix arithmetic expression from an
* InputStream. It should not create a full postfix expression along the way; it
* should convert and evaluate in a pipelined fashion, in a single pass.
*/
public class InfixExpressionEvaluator {
// Tokenizer to break up our input into tokens
StreamTokenizer tokenizer;

// Stacks for operators (for converting to postfix) and operands (for
// evaluating)
StackInterface<Character> operatorStack;
StackInterface<Double> operandStack;

/**
   * Initializes the evaluator to read an infix expression from an input
   * stream.
   * @param input the input stream from which to read the expression
   */
public InfixExpressionEvaluator(InputStream input) {
    // Initialize the tokenizer to read from the given InputStream
    tokenizer = new StreamTokenizer(new BufferedReader(
                                                       new InputStreamReader(input)));
   
    // StreamTokenizer likes to consider - and / to have special meaning.
    // Tell it that these are regular characters, so that they can be parsed
    // as operators
    tokenizer.ordinaryChar('-');
    tokenizer.ordinaryChar('/');
   
    // Allow the tokenizer to recognize end-of-line, which marks the end of
    // the expression
    tokenizer.eolIsSignificant(true);
   
    // Initialize the stacks
    operatorStack = new ArrayStack<Character>();
    operandStack = new ArrayStack<Double>();
}

/**
   * Parses and evaluates the expression read from the pr...

By purchasing this solution you'll be able to access the following files:
Solution.zip.

$75.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats