Data Structures Assignment 2

    • Motivation

In lecture, we discussed an stack algorithm for converting an in x expression to a post x expression (\shunting-yard"), and another for evaluating post x expressions. We brie y described how one might pipeline these algorithms to evaluate an in x expression in a single pass using two stacks, without generating the full post x expression in between. In this assignment, you will implement this combined algorithm. Your completed program will evaluate an in x arithmetic expression using two stacks. You may wish to review the revelant algorithms in Chapter 5 of Carrano & Henry.
You are provided with the skeleton of InfixCalculator. This class accepts input from an InputStream and parses it into tokens. When it detects an invalid token, it throws an InvalidExpressionException to report the error. To facilitate ease of use, this class also contains a main method. This method instantiates an object of type InfixCalculator to read from System.in, then evaluates whatever expression is typed. It also catches any InvalidExpressionException that is thrown, and prints the reason for the error.

InfixCalculator 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.

    • Tasks

First, carefully read the provided code. You can nd this code on Pitt Box in a folder named cs445-a2-abc123, where abc123 is your Pitt username. You are allowed to modify the provided code in any way, as long as you do not change how it is used (e.g., do not accept multiple expressions in one execution, or read expressions from a le rather than System.in).

2.1    Implement helper methods, 70 points

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.




1

handleOperand(double): Each time the calculator 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 in x-to-post x and post x-evaluation algorithms.

handleOperator(char): Each time the calculator 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 in x-to-post x and post x-evaluation algorithms.

Each of the following operators must be supported. Integer division should truncate the decimal part, yielding an integer value (so 6\4 yields 1.0 and (0-9)\2 yields -4.0). Follow standard operator precedence. You can assume that ‘-’ is always the binary subtraction operator (e.g., no negative operands in the expression).

    • Addition

    • Subtraction

    • Multiplication

    • Division

\ Integer Division ^ Exponentiation

handleOpenBracket(char): Each time the calculator 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 in x-to-post x and post x-evaluation algorithms.

You must support both round brackets () and square 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 calculator 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 in x-to-post x and post x-evaluation algorithms.

handleRemainingOperators(): When the calculator 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 ex-pression. The provided code throws InvalidExpressionException when encountering an unknown token (for instance, &). You must modify your program so that, whenever it encounters any other type of error in an expression, it throws InvalidExpressionException with a speci c error message. The message should explain what is wrong with the expression (i.e., what the user did wrong), and not what internal implementation detail allowed you to detect it. For instance, your error message should never mention the stack, as the user should not be required to know how the program works.

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 InvalidExpressionException.

2


Hints:

    1. Which pairs of adjacent token types are valid vs. invalid? Consider creating a data member that tracks the most recent token type. When handling a new token, rst 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?




    • Grading

The following points breakdown will be used to assign grades:

70 points are allocated for correctly evaluating valid expressions. These expressions will range from very simple to very complex, but none will contain syntax errors. You should test your program extensively to ensure that it works properly even for complex expressions with multiple sets of nested brackets and combinations of all operators.

30 points are allocated for correctly identifying the syntax errors in invalid expres-sions. These expressions will contain a wide variety of syntax errors. You should test your program with many invalid expressions to ensure that it correctly detects all possible syntax errors.


Note: Code that cannot be compiled and executed will be given a grade of 0.



3.1    Extra credit

In addition to the above tasks, for up to 8 bonus points, you may add additional features to your program. If you do so, include a le named README.txt describing these extra features (please place this le in your cs445-a2-abc123 folder, and not within the cs445/a2/ package folder).

For instance, you may consider errors beside those of syntax. Can you detect and report divide-by-zero? What about other errors in value? Can you support both the binary subtraction operator and the unary negation operator (using the same symbol or a di erent symbol)? Can you add support for additional operators? Hexadecimal operands of the form 0x6a or octal operands like 0o73?

This task encourages you to brainstorm outside of the assignment brief. Try to add unique and interesting features to your calculator.

    • Submission

Upload your java les in the provided Box directory as edits or additions to the provided code.


3


All programs will be tested on the command line, so if you use an IDE to develop your program, you must export the java les from the IDE and ensure that they compile and run on the command line. Do not submit the IDE’s project les. Your TA should be able to download your cs445-a2-abc123 directory from Box, and compile and run your code. Speci cally, javac cs445/a2/InfixCalculator.java and java cs445.a2.InfixCalculator must compile and run your program, when executed from the root of your cs445-a2-abc123 directory.

In addition to your code, you may wish to include a README.txt le that describes features of your program that are not working as expected, to assist the TA in grading the portions that do work as expected. This le should also specify any extra credit tasks that you completed. If you include one, place it in the root of your cs445-a2-abc123 folder (not in the package folder).

Your project is due at 11:59 PM on Monday, October 14. You should upload your progress frequently, even far in advance of this deadline: No late submissions will be accepted.












































4