Description
Introduction
The purpose of this lab is to design a program to implement a calculator, but there is a
difference this time around: the calculator will first perform an infix to postfix conversion
and then evaluate the resulting postfix expression.
You should implement the calculator in two parts:
A Converter class that will convert the input string to postfix expression. A
Calculator class that will evaluate the postfix expression.
Both the Converter and Calculator classes should use either the ArrayStack or the
LinkedStack adapted from the book. You are not allowed to use any pre-built classes in
the Java library (such as ArrayList or something else).
Implementation and Design
The PostfixCalculator class
You will need to do the following in your PostfixCalculator class:
● The Calculator class will instantiate an object of the Converter class in order to
have the infix expression converted to a postfix expression.
● An additional operator, “^”, will be added. Java has a built in exponent function:
Math.pow(x, y). Use this to evaluate x^y.
● Parentheses are legal in the infix expression (Note: the parentheses are needed
in the infix expression. After your Converter class’ algorithm converts the
expression to postfix, it will no longer have parentheses because they are not
necessary in postfix expressions.)
In postfix notation, the operator is written after the two operands. An expression with
multiple operators is evaluated in the same way, from left to right which each operator
applied to the two previous operands.
If you are having trouble with figuring out the algorithm for how to evaluate postfix
expressions, consult the Postfix notation definition in the textbook.
The Converter class
The purpose of the Converter class is to take an infix expression that is generated by
the user, and convert it to a postfix expression that can be evaluated using code. The
Converter class uses a stack to accomplish this. Here is how it works:
● When the Converter class is instantiated, a String is passed representing the infix
expression entered by the user. This should be saved as an instance variable.
● The method that does all the work in the Converter class should be called
toPostFix(). It will convert the infix expression to a postfix expression. The postfix
expression should be a string that can be evaluated by the calculator. Each
operator and operand should be separated by spaces. This is not necessarily
true of the input (i.e., the original infix expression might look like “2+2” instead of
“2 + 2”).
● The first thing the converter class does is to tokenize the input string into a list of
tokens representing operators and operands. Parenthesis are also allowed in
infix expressions, so “(” and “)” are valid tokens. A parser method has been
provided to you for your convenience – see the ParserHelper.java file.
● Once the input is tokenized, a stack is used to convert to a postfix expression.
We will go over the algorithm in recitation. Here is the basic idea: create a stack
and an output string. Read all of the tokens from left to right.
The algorithm:
1. Whenever you come upon an operand, append it onto the end of the
output string.
2. Whenever you come upon an operator, look at the top of the stack to
make sure the operator on the stack has a lower precedence.
○ If the token has higher precedence, then push it onto the stack.
○ If the token has lower precedence, then pop operators out of the
stack and append them to the output string. You may stop popping
stack elements once the top of the stack has lower precedence
than the current token. You will of course have to stop popping
elements if the stack becomes empty.
3. Whenever you come upon an open parenthesis, always put it on the
stack.
4. Whenever you come upon a closed parenthesis, pop out all the operators
on the stack and append them to output until you find the matching
parenthesis. Pop out the matching parenthesis and don’t add either paren
to the output (remember: postfix doesn’t have parenthesis!)
● The details and helper methods used in this class are left up to you.
The input will always be some mathematical expression that contains a
combination of the operations +,-,*,/, and ^. All of the numbers will be integers.
You may assume that the expressions will never miss an operand (e.g., you
won’t encounter something like “3 + ”). Here are some example inputs to try out:
● 3+4*5/6
● (300+23)*(43-21)/(84+7)
● (4+8)*(6-5)/((3-2)*(2+2))
Example output
Given (4+8)*(6-5)/((3-2)*(2+2)), your output should show the converted postfix
string and the result of the calculation.
type your infix expression:
(4+8)*(6-5)/((3-2)*(2+2))
converted to postfix: 4 8 + 6 5 – * 3 2 – 2 2 + * /
answer is 3.0
Formatting and Style
The output for this assignment is pretty simple, so just make sure that it is legible and clear.
Make sure not to leave out any operands and/or operators.
Coding style will be important, especially since this assignment brings together a lot of the
concepts of OOP that we have recently covered. Put to use the best practices we’ve talked
about so far in the course.
Grading Rubric
Criteria
Compiles successfully (1 point)
Converter class performs infix to postfix expression successfully, uses Stack class (3
points)
Calculator class evaluates postfix expressions correctly, uses Stack class (3 points)
Good style demonstrated in the code; sensible formatting (1 point)
