CS 5040: Data Structures and Algorithms
Fall 2021, Assignment #3 – Stack
The goal for this assignment is to implement Stack ADT using linked-list implementation. Then, write a program to use an object of the developed Stack class to solve simple and practical problems.
Part 1: (20 points)
Develop a new class, called MyStackYourname, to implement, among others, key stack operations [push(e), pop(), peek(), size(), isEmpty(), search(), toString()]we discussed in the class. Again, class Stack needs to be defined as generic stack with type E so that we can create stack objects that can hold data of different types, such as integer stack, string stack, char stack, double stack, etc.
You must inherits java.util.ArrayList or java.util.LinkedList to implement MyStackYourname.
You can refer the MyStack.java code, but please make sure the name of methods are different.
StackYourname Class must have these methods
- methodname(argument): returnType
- isEmpty(): boolean Returns true if this stack is empty
- size(): int Returns the number of elements in this stack
- peek(): E Returns the top element in this stack
- pop(): E Returns and removes the top element in this stack
- push(E element): E Adds a new element to the top of this stack
- toString(): String Returns the String with all elements in current stack
// based on your choice, toString will return the String with all elements in order [top to bottom] or [bottom to top]
Part 2: (10 points)
Next, develop a simple test program called TestStackYourname to test each stack operation listed above and defined in your class MyStackYourname. Try String type stack for the test program. Use proper labels.
Make sure to allow the user to enter the stack content using interactive menu (embedded inside the sentinel loop):
-----MAIN MENU-----
0 - Exit Program
1 – Push // Push should have user input
2 - Pop
3 – Peek (Top)
4 - Size
5 – Is Empty?
6 – Print Stack
Choose menu:
Again, you cannot change method names, return type and parameter types.
To evaluate your Class’s methods, the instructor will use another Test Program and will use your methods.
// We will use main method (check Part 5) for testing both Part 3 and 4 at once
Part 3: (10 points)
Implement a class, call it ExprYourname, which will be used for transform the expressions(infix to prefix) and evaluate prefix.
Write a method
public static String infixToPrefix(String infix){
// Write appropriate codes here
// Return prefix as a returned String of this method
}
Use your MyStackYourname to write the procedure of transformation from infix to prefix. Use the algorithm of infix to prefix translation which is introduced in the lecture, translate infix expression to prefix expression .
Assumption:
Input infix string doesn’t have whitespaces.
All input number is one-digit number. (positive digit 0 to 9)
Input infix can include parenthesis ( )
Operator + - * / ^ can be used.
If postfix input is not calculatable, show the result
The output prefix string doesn’t have whitespaces.
Part 4: (10 points)
In ExprYourname above, implement another method, call it prefixEval, which prompts the user to enter a string value of prefix expression. Using class StackYourname, the program should evaluate the prefix expression and return the correct calculated result.
Write a method
public static double prefixEval(String prefix){
// Write appropriate codes here
// Return calculated result value
}
Assumption:
Input prefix string doesn’t have whitespaces.
All input number is one-digit number. (positive digit 0 to 9)
Operator + - * / ^ can be used.
If postfix input is not calculatable, show the result
Part 5: (10 points)
Write a main method which tests above two methods (Part 3 and Part 4)
Write a method
public static void main(String[] args){
// What is the process of main method.
// - User will insert infix
// - Invoke infixToPrefix to transform it to prefix expression
// - Invoke prefixEval to evaluate prefix expression
// - Show the calculated result
// Write appropriate codes here
}
// Two examples
Enter an infix: (7+3)*(3-1)/2 //user input infix
Prefix Evaluation: /*+73-312
Result value: 10
Enter an infix: (5-6)/4*2-(5+2) //user input infix
Prefix Evaluation: -*/-5642+52
Result value: -7.5
//ignore the number of digits after decimal point
Submission:
Before submitting your programs, make sure you review the assignment submission requirements and grading guidelines on the course webpage. The grading guidelines explain some of the common errors found in programming assignments.
1. One document with screenshots to show all your results, all individual .java files.
2. The assignment is due no later than 11:59 PM on the due day posted in D2L.
3. Please compile and run your java files (only the .java files) right before you upload to the assignment submission folder in D2L.