Assignment 3
CSE 214
In this assignment, you are required to write your own generic stack implementation in Java, and
use this implementation to convert and evaluate arithmetic expressions. Your code must handle the
general expressions, and not just those that are fully paranthesized. Details are provided below.
1. Generic Stack Implementation
a. Your stack class must contain a private static nested class called Node.
b. Your stack must have all instance variables as private.
c. It must have the stack operation methods isEmpty, peek, pop, push and size. Remember
to carefully deal with exceptions in these methods (wherever needed).
2. Infix to Postfix conversion
Write a class called InfixToPostfixConverter. This class, as its name suggests, will be responsible
for converting infix expressions to postfix expressions using your stack implementation.
a. Your class must contain a public String convert(char[] infix) method that takes as
input an infix expression, and outputs the equivalent postfix expression.
3. Evaluating a Postfix expression
Write a class called PostfixEvaluator to evaluate postfix expressions.
a. It must contain a public int evaluate(char[] postfix) method.
b. It must contain a public static void main(String[] args) method to run your code.
This main method should ask the user to input one infix expression per line until the user
types “q” or “Q”. After every input, it should print out the equivalent postfix expression, and
the final value of the expression, and then ask for the next input.
c. You should assume no whitespace in the infix expression provided by the user. For example,
your code should work for inputs like “2+3.5×2”. The postfix that you will print, however,
should have tokens separated by whitespace. For example, “3.5×21” should have the postfix
“3.5 21 ×”, and not “3.521×”.
Important Notes
• You may not use any Java data structures directly (other than arrays). Using
Java’s native data structures in this homework will result in a zero score.
Note that you will not need to use linked list for this stack implementation.
• There are points in this homework for properly using Java keywords. For instance, don’t fill
up your code with new instances of the same variable. If you are repeatedly using a particular
value, use the suitable Java keywords.
(Hint: Think in terms of examples like “public static final PI” that we have discussed.)
• It may be useful to look into the official Java documentation1 of StringBuilder and Character.
1
http://docs.oracle.com/javase/7/docs/api/index.html?overview-summary.html
CSE 214 Assignment 3
Points Distribution Total: 50 points
Stack implementation 10 points
Infix to postfix conversion 20 points
Evaluating a postfix expression 10 points
Proper usage of Java keywords 5 points
Main method in PostfixEvaluator 5 points
Submission Guidelines
1. Submit a single .zip file consisting of three .java files:
i. Stack.java
ii. InfixToPostfixConverter.java
iii. PostfixEvaluator.java
Grading
For this assignment, it is EXTREMELY important that your code compiles properly, and that the
main method can be used. The TA cannot test your code unless this is done properly. So,
if this step is missing or wrongly done, there is NO POSSIBILITY OF PARTIAL CREDIT.
• If you are running out of time before the submission deadline, it is strongly recommended
that you submit a partial solution that can be run and tested, rather than a submission where
you have done a lot of work, but because there’s no main method, the TA cannot run/test
your code.
Assignments will not be regraded if you submit the wrong files.
So, double/triple-check what you are submitting!
Submission Deadline
The due date for this assignment is 11:59 PM of Thursday, Apr 06, 2017.