Basic Calculator

1. Background

In this assignment you will implement a small calculator that can process simple mathematical expressions that involve only (as input): positive integers, parentheses, and the four operators: addition, subtraction, multiplication, and (floating-point) division. For example, the following expressions are supported:

(12-2)*2/(3+2)

1+1*4

(1)

(12)-(45-5)

1/3

but the following are not supported:

-1-2

2.5*4

For this assignment, the graphical portion of the code is implemented for you. Your task is to supply the code responsible for processing the expression and evaluating it, and for detecting errors in invalid expressions.

Evaluating mathematical expressions may seem like a daunting task at first, but it is relatively simple if you choose the right data structures (which we have seen in class) and are familiar with two key concepts: tokenization and reverse Polish notation.

[url removed, login to view]

Tokenization is the process of breaking up a sequence of characters into units that are meaningful for a certain task (in our case, computing mathematical expressions). For instance, in the expression 123+456, it is not convenient to consider the digits individually. Instead, we would prefer to work with a sequence of three units: [123][+][456] (here square brackets are used as token delimiters). As part of your task, you will write a tokenizer that does three things:

Ignore ("swallow") all white spaces;

Flag an error if any invalid character is discovered (an invalid character is any character except a white space, digit, parenthesis, or operator).

Package the string into a stream of tokens.

Example of tokenization:

(123+34)/(3*4*5) -> [(][123][+][34][)][/][(][3][*][4][*][5][)]

[url removed, login to view] Polish Notation

Mathematical expressions such as (1+2)/3 are in infix notation, that is, the operator is placed between operands. It turns out that evaluating operations directly in infix notation is unnecessarily complex. A better way is to convert infix expressions into Reverse Polish Notation (RPN), where operators follow their operands. In the following examples, the first line is an expression in infix notation and the line below is the same expression in RPN. Note that in RPN parentheses are superfluous and not used.

[1][+][2]

[1][2][+]

[1][+][1][*][4]

[1][1][4][*][+]

[(][12][-][2][)][*][2][/][(][3][+][2][)]

[12][2][-][2][*][3][2][+][/]

As part of the assignment, one of your task is to convert the original expression in infix notation into its RPN equivalent. To do this, you can pretty much directly implement the famous Shunting-yard algorithm. If you use the previous (Wikipedia) reference, simply omit the steps that involve function calls since function calls are not supported by our calculator. As usual, our four operators are left-associative and multiplication and division have precedence over addition and subtraction.

Once you have an expression in RPN, evaluating it is trivial using a Stack (figuring out how to do this is part of the assignment).

5. Recommended Sequence

There is a natural dependency order in the pieces you need to implement for this assignment and you are strongly encouraged to follow this order:

Implement the Token hierarchy and the Tokenizer. Test the tokenizer thoroughly.

Implement the processExpression method and test that it produces correct RPN expressions.

Implement the evaluateExpression method.

If you feel overwhelmed at first, implement a first version that assumes perfectly well-formed expressions. You should be able to add the error checking incrementally after the fact.

Java

Project ID: #7312544

About the project