CmSc 155 Fundamentals of computing II
Programming Project 02: Calculator, due 03/26
The purpose of this programming project is to implement a calculator. The project will be based on the code provided in Chapter 9, with the following modifications:
1. The restriction to have spaces between the numbers and the operators will be abandoned
2. The expression will be verified for correctness:
3. The numbers will be converted from strings to integers using Horner’s method for computing polynomials (without using the Java parseInt method).
The program should accomplish the following tasks:
1. Enter a string containing the expression. This is done through the calculator GUI either by clicking the necessary buttons or by typing in the expression (You will use the code provided by the authors)
2. Tokenize the expression. This means to separate the individual elements in the expression and store them in some data structure, e.g. an array of type String. The expression may contain any number of spaces between its elements, however spaces are not required as delimiters, i.e. your program should not use the Java tokenizer, because the latter requires spaces to separate the elements in the expression.
Expression tokens are:
the operators +, *, /, –
opening parenthesis, closing parenthesis
numbers as strings of digits
3. Check the expression for correctness and identify the unary negative signs:
· A correct expression should have matching parentheses and should not start with a closing parentheses. Note that the presence of parentheses is not required.
· A correct expression should not start with an operator, except for ‘-‘ (unary minus)
· A correct expression should not end with an operator
· A correct expression should not contain:
- two consecutive integers
- two consecutive operators
- operator followed by closing parenthesis
- opening parenthesis followed by +.*, /
- any symbols different from digits, (, ), +, -, *, /, and spaces
· A negative sign is unary when it is either at the beginning of the expression, or following an opening parenthesis. When a negative sign is recognized as unary minus, it has to be replaced by the symbol ‘~’ .
See more hints at the end of this document
4. Convert the expression to postfix notation (based on the code in the textbook). The algorithm to convert an infix into postfix expression is the following:
1. Initialize two stacks: operatorStack and postfixStack
2. For each token in the expression do
in case the token is:
an operand (string of digits) : push onto postfixStack
( : push onto operatorStack
) : pop and from operatorStack and push onto
postfixStack all operators until
encountering ‘(‘, then pop ‘(‘
* or / : pop from operatorStack and push onto
postfixStack all operators ‘*’ and ‘/’ from
the top down to but not including the
topmost ‘(‘, ‘+’, ‘-‘, ‘~’, or to the bottom
of the stack. Then push onto the
operatorStack the new symbol * or /
+ , -, ~ : pop from operatorStack and push onto
postfixStack all operators from the top
down to but not including the topmost ‘(‘
or to the bottom of the stack. Then push
onto operatorStack the new symbol ‘+’, ‘-‘
or ‘~’
end_of_expression : pop from operatorStack and push onto
postfixStack all remaining operators
The expression in postfixStack will be in reverse order, so you have to reverse the stack.
5. Evaluate the postfix expression (based on the code in the textbook)
Algorithm:
Initialize a valueStack used to compute the value of the expression, elements in the valueStack have to be integers
While the postfixStack is not empty
Pop an element from posfixStack
If it is an operand, convert it to integer number and push onto valueStack
If it is a unary minus
Pop a number from valueStack, multiply by (-1) and push back.
If it is a binary operator
Pop operand2 from valueStack
Pop operand1 from valueStack
Apply the operator to operand1 and operand2,
Push the result onto valueStack.
Pop the result from valueStack – this is the value of the expression
6. Deliver the result in the calculator text field (based on the code in the textbook)
The project will be documented following the standards in http://java.sun.com/j2se/1.4.2/docs/api/index.html
The implementation will be done in steps, with some of the tasks implemented as homework assignments.
Checking for correctness:
tokens array
prev – char variable contains the type of the previous token
curr – char variable contains the type of the current token
token types:
‘o’ – operator
‘d’ – digits (i.e. number)
‘(‘
‘)’
The following table gives the valid pairs prev – curr:
curr ->prev / - / + / * / / / ( / ) / digits
- / E / E / E / E / E
+ / E / E / E / E / E
* / E / E / E / E / E
/ / E / E / E / E / E
( / ~ / E / E / E / E
) / E / E
digits / E / E
E: Error
Types of errors that can be found and how they are recognized:
Types of errors / Indicated by1. Opening parentheses more than closing / Parentheses stack not empty at the end of processing
2. Closing parentheses more than opening / Attempt to pop from parentheses stack when it is empty
3. Expression starts with a closing parenthesis / Check the first token
4. Expression starts with an operator that is not unary minus / Check the first token
5. Expression ends with an operator / Check the last token
6. Incorrect sequencing / Check the relation ‘prev – curr’
Algorithm:
1. initialize a stack to be used for checking the parentheses
2. set prev = ‘a’, error = false, type of error = 0
3. for i from 0 to the end of the tokens in tokens array and not error
a. Determine the type of the current token. Types are: ‘o’ for operator, ‘d’ for number, ‘(‘ and ‘)’
b. If i = 0 and (type = ‘o’ but not ‘-‘, or type = ‘)’)
i. set error = true,
ii. set type of error = 3 if type of token is ‘)’, or type of error = 4 otherwise, exit
c. If i = 0 and no error,
i. If type = ‘(‘ push in parentheses stack
ii. set prev = curr
d. if i not 0,
i. check the relation prev – curr for incompatible types. If error is found, set error = true, set type or error = 6, exit
ii. if unary minus, change ‘-‘ to ‘~’ in tokens array
iii. if ‘)’ pop from stack, if not empty. If the stack is empty set error = true, type of error = 2, exit.
iv. if ‘(’ push in parentheses stack
v. Set prev = curr
When the loop ends
1. If no error, check the last symbol – should not be operator. If it is an operator, set error = true, type of error = 5
2. If no error, check parentheses stack –
if not empty set error = true, type of error = 1.
3. If no error, check the first symbol, if unary minus, replace it with ‘~’
Return type of error
4