Question
Can you modify the main.java and infixexpression.java to use an ArrayQueue and LinkedQueue instead of the ArrayStack and LinkedStack? (Please don't change anything from the
Can you modify the main.java and infixexpression.java to use an ArrayQueue and LinkedQueue instead of the ArrayStack and LinkedStack? (Please don't change anything from the queue and stack classes. Thank you.
___________________________________________________________________________________
/**
Main driver that tests the InfixExpression class's methods function. Also tests that the
ArrayStack and LinkedStack are working correctly for the InfixExpression class.
@author Jae Kim
@version 1.0
@date 5/11/2017
@system windows/eclipse
*/
import java.io.*;
import java.util.Scanner;
public class Main {
/**
* calls the openInputFile method and testHW method to see if those methods
* are working correctly. It will keep reading until the line in the file is
* blank.
*
* @param args
*/
public static void main(String[] args) {
Scanner Scanning = openInputFile(); // the return of Scanned file of the
// openInputFile
while (Scanning.hasNextLine()) {
String lineRead = Scanning.nextLine(); //The next line of the file read.
InfixExpression inputLineCalculation = new InfixExpression();
inputLineCalculation.setWholeExpr(lineRead);
System.out.println(inputLineCalculation.toString());
}
testHW1();
}
public static Scanner userScanner = new Scanner(System.in);
/**
* Declares a new instance of the InfixExpression to test the null parameter
* and a string parameter to see if the InfixExpression class works
* correctly. It also tests if the ArrayStack and the LinkedStack classes
* are working correctly.
*/
public static void testHW1() { // testing InfixExpression more:
InfixExpression infix1, infix2;
infix1 = new InfixExpression(null);
infix2 = new InfixExpression("( 234.5 * ( 5.6 + 7.0 ) ) / 100.2");
System.out.println(" Testing InfixExpression:");
System.out.println("When passing null, the String and double = " + infix1.toString());
System.out.println("When passing a valid String, the String and double = " + infix2.toString());
// testing ArrayStack and LinkedStack more:
ArrayStack
LinkedStack
String[] strArray = { "First", "Second", "Third", "Fourth", "Fifth", "Sixth", "Seventh", "Eighth", "Ninth",
"Tenth" };
// Testing ArrayStack
System.out.println(" Testing the ArrayStack:");
for (int i = 0; i < strArray.length; ++i) {
if (!arrStack.push(strArray[i] + " 1"))
System.out.println("Error: couldn't push " + strArray[i] + " 1");
}
for (int i = 0; i < strArray.length; ++i) {
if (!arrStack.push(strArray[i] + " 2")) {
System.out.println("Out of space, removing " + arrStack.pop());
if (!arrStack.push(strArray[i] + " 2"))
System.out.println("Error pushing!" + strArray[i] + " 2");
}
}
System.out.println("The size of the ArrayStack is now " + arrStack.size());
while (!arrStack.isEmpty()) {
System.out.println("Popping " + arrStack.pop());
}
System.out.println("The size of the ArrayStack is now " + arrStack.size());
if (!arrStack.push(strArray[0] + " 3"))
System.out.println("Error: couldn't push " + strArray[0] + " 3");
else
System.out.println(
"After pushing " + arrStack.peek() + ", the size of the ArrayStack is now " + arrStack.size());
// testing LinkedStack
System.out.println(" Testing the LinkedStack:");
for (int i = 0; i < strArray.length; ++i)
linkStack.push(strArray[i] + " 4");
System.out.println("The size of the LinkedStack is " + linkStack.size());
for (int i = 0; i < strArray.length / 2; ++i) {
System.out.println("Popping " + linkStack.pop());
}
System.out.println("The size of the LinkedStack is now " + linkStack.size());
while (!linkStack.isEmpty()) {
System.out.println("Popping " + linkStack.pop());
}
System.out.println("The size of the LinkedStack is now " + linkStack.size());
if (!linkStack.push(strArray[0] + " 5"))
System.out.println("Error: couldn't push " + strArray[0] + " 5");
else
System.out.println(
"After pushing " + linkStack.peek() + ", the size of the LinkedStack is now " + linkStack.size());
} // end stackTester
/**
* This method reads the file that is typed in from the console so that the
* file is read.
*
* @return Scanner
*/
public static Scanner openInputFile() {
String filename;
Scanner scanner = null;
System.out.print("Enter the input filename: ");
filename = userScanner.nextLine();
File file = new File(filename);
try {
scanner = new Scanner(file);
} // end try
catch (FileNotFoundException fe) {
System.out.println("Can't open input file ");
return null; // array of 0 elements
} // end catch
return scanner;
} // end openInputFile
}
___________________________________________________________________________
/**
* A class of stacks whose entries are stored in a chain of nodes.
* @author Jae Kim
* @version 1.0
* @date 5/11/2017
* @system windows/eclipse
*/
/**
* @author Frank M. Carrano
* @author Timothy M. Henry
* @version 4.0 UPDATED by C. Lee-Klawender
*/
public class LinkedStack
private Node topNode; // References the first node in the chain
private int numOfEntries;
// ADD A PRIVATE INT FOR COUNTER THAT INDICATES HOW MANY NODES ARE IN THE
// STACK
public LinkedStack() {
topNode = null;
numOfEntries = 0;
} // end default constructor
public boolean push(T newEntry) {
topNode = new Node(newEntry, topNode);
numOfEntries++;
// ADD CODE SO THE COUNTER IS CORRECT
return true;
} // end push
public T peek() {
if (isEmpty())
return null;
else
return topNode.getData();
} // end peek
public T pop() {
T top = peek();
if (topNode != null) {
topNode = topNode.getNextNode();
numOfEntries--;
// ADD CODE SO THE COUNTER IS CORRECT
}
return top;
} // end pop
public boolean isEmpty() {
if (topNode == null) {
return true;
} else
return false;
} // end isEmpty
public int size() {
return numOfEntries;
}
// WRITE THE "MISSING" METHOD, REQUIRED FOR THIS CLASS SO IT'S NOT ABSTRACT
// (also Ex. 2.2):
private class Node {
private T data; // Entry in stack
private Node next; // Link to next node
private Node(T dataPortion) {
this(dataPortion, null);
} // end constructor
private Node(T dataPortion, Node linkPortion) {
data = dataPortion;
next = linkPortion;
} // end constructor
private T getData() {
return data;
} // end getData
private void setData(T newData) {
data = newData;
} // end setData
private Node getNextNode() {
return next;
} // end getNextNode
private void setNextNode(Node nextNode) {
next = nextNode;
} // end setNextNode
} // end Node
} // end LinkedStack
_______________________________________________________________
import java.util.StringTokenizer;
import java.util.ArrayList;
/**
* InfixExpression breaks the line that is passed into tokens so that it can be
* stored in an arraylist and seperates the token into a value or an operator so
* that it can calculate the expression which is a string and turn it into a
* double value.
*
* @author Jae Kim
* @version 1.0
* @date 5/11/2017
* @system windows/eclipse
*/
public class InfixExpression {
private String wholeExpr; // whole line that is being read for calculation
private ArrayList
// line.
private double finalResult; // result of the calculation done by the methods
public InfixExpression() {
wholeExpr = " ";
tokenizedArrayList = new ArrayList
finalResult = 0;
}
/**
* Calls the default constructor and sets the wholeExpr to the parameter
* expression
*
* @param expression
*/
public InfixExpression(String expression) {
this();
setWholeExpr(expression);
}
/**
* Sets the wholeExpr to the parameter Expr.
*
* @param Expr
*/
public void setWholeExpr(String Expr) {
wholeExpr = Expr;
if (wholeExpr != null) {
Tokenize();
Evaluate();
}
}
/**
* It returns the String wholeExpr.
*
* @return
*/
public String getWholeExpr() {
return wholeExpr;
}
/**
* This method returns the finalResult.
*
* @return
*/
public double getFinalResult() {
return finalResult;
}
/**
* This method splits the line by " " into tokens and stores in the Array
* which later is added into the ArrayList
*/
private void Tokenize() {
String[] tokenizedArray = wholeExpr.split("[ \t]+");
tokenizedArrayList.clear(); // clear the ArrayList
for (int i = 0; i < tokenizedArray.length; ++i) {
tokenizedArrayList.add(tokenizedArray[i]); // add the next token to
// the ArrayList
}
}
/**
* This method seperates the tokens into operators or operands and stores it
* into opStack if it is an operator and valStack if it is a numeral value.
* It then calls the execute method in the value of precedence.
*/
private void Evaluate() {
StackInterface
StackInterface
for (int i = 0; i < tokenizedArrayList.size(); i++) {
String token = tokenizedArrayList.get(i);
if (OpChecker(token)) {
if (opStack.isEmpty()) {
opStack.push(token);
} else if (Precedence(token) > Precedence(opStack.peek())) {
opStack.push(token);
} else {
while (!opStack.isEmpty() && Precedence(token) <= Precedence(opStack.peek())) {
execute(opStack, valStack);
}
opStack.push(token);
}
} else if (token.equals("(")) {
opStack.push(token);
} else if (token.equals(")")) {
// added a condition to check if the stack is empty
while (opStack.peek() != "(" && !opStack.isEmpty()) {
execute(opStack, valStack);
}
} else {
valStack.push(Double.parseDouble(token));
}
}
while (!opStack.isEmpty()) {
execute(opStack, valStack);
}
if (valStack.size() == 1) {
finalResult = valStack.peek();
} else {
finalResult = 0;
}
}
/**
* This method brings in the parameter opStack and valStack from the
* Evaluate() and does the actual calculations that returns the value and
* restores into the valStack and removes an operation from the opStack.
*
* @param opStack
* @param valStack
*/
private void execute(StackInterface
double rightOperand = 0;// the top value of the valStack
double leftOperand = 0;// the second top value of the valStack
double temp = 0;// the value of the operation of the right and
// leftOperand
String op = opStack.pop();
if (valStack.isEmpty()) {
return;
} else {
rightOperand = valStack.pop();
}
if (valStack.isEmpty()) {
valStack.push(rightOperand);
return;
} else {
leftOperand = valStack.pop();
}
switch (op) {
case "+":
temp = leftOperand + rightOperand;
break;
case "-":
temp = leftOperand - rightOperand;
break;
case "*":
temp = leftOperand * rightOperand;
break;
case "/":
temp = leftOperand / rightOperand;
break;
// I added the default just in case that it is not any of the cases up
// above
default:
valStack.push(leftOperand);
valStack.push(rightOperand);
return;
}
valStack.push(temp);
}
/**
* This method returns true if the parametere String is an operator, false
* if not.
*
* @param operator
* @return
*/
private boolean OpChecker(String operator) {
if (operator.equals("+") || operator.equals("-") || operator.equals("*") || operator.equals("/")) {
return true;
} else
return false;
}
/**
* This returns the int value of the operators so it can be determined which
* operator to execute first
*
* @param operator
* @return
*/
private int Precedence(String operator) {
if (operator.equals("(") || operator.equals(")")) {
return 1;
} else if (operator.equals("/") || operator.equals("*")) {
return 2;
} else
return 3;
}
/**
* This method returns the String form of the wholeExpr and the final
* result.
*/
public String toString() {
return "Infix String: " + wholeExpr + ", " + "result: " + finalResult;
}
}
______________________________________________________________
import java.util.*;
/**
* A class of stacks whose entries are stored in an array.
* @author Jae Kim
* @version 1.0
* @date 5/11/2017
* @system windows/eclipse
*/
/**
* @author Frank M. Carrano
* @author Timothy M. Henry
* @version 4.0 UPDATED by C. Lee-Klawender
*/
public class ArrayStack
private T[] stack; // Array of stack entries
private int topIndex; // Index of top entry
private static final int DEFAULT_CAPACITY = 15;
private static final int MAX_CAPACITY = 100;
public ArrayStack() {
this(DEFAULT_CAPACITY);
} // end default constructor
public ArrayStack(int initialCapacity) {
if (initialCapacity > MAX_CAPACITY)
initialCapacity = MAX_CAPACITY;
else if (initialCapacity < DEFAULT_CAPACITY)
initialCapacity = DEFAULT_CAPACITY;
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] tempStack = (T[]) new Object[initialCapacity];
stack = tempStack;
topIndex = -1;
} // end constructor
public boolean push(T newEntry) {
if (topIndex + 1 < stack.length) {
stack[topIndex + 1] = newEntry;
topIndex++;
return true;
}
return false;
} // end push
public T peek() {
if (isEmpty()) // UPDATE FOR HW#1
return null;
else
return stack[topIndex];
} // end peek
public T pop() {
if (isEmpty()) // UPDATE FOR HW#1
return null;
else {
T top = stack[topIndex];
stack[topIndex] = null;
topIndex--;
return top;
} // end if
} // end pop
public boolean isEmpty() {
if (stack[0] == null) {
return true;
} else
return false;
}
public int size() {
return 0;
}
// TWO MORE METHODS ARE REQUIRED HERE (PART OF EXERCISE 2.1)
} // end ArrayStack
______________________________________________________________________
public interface StackInterface
/**
* Adds a new entry to the top of this stack.
*
* @param newEntry
* An object to be added to the stack.
*/
public boolean push(T newEntry);
/**
* Removes and returns this stack's top entry.
*
* @return The object at the top of the stack. or null if the stack is empty
*/
public T pop();
/**
* Retrieves this stack's top entry (without removing).
*
* @return The object at the top of the stack. or null if the stack is
* empty.
*/
public T peek();
/**
* Detects whether this stack is empty.
*
* @return True if the stack is empty.
*/
public boolean isEmpty();
/**
* Returns number of items in this stack
*
* @return: Number of items
*/
public int size();
} // end StackInterface
____________________________________________________________________
/**
A class that implements the ADT queue by using a chain of nodes
that has both head and tail references.
@author Frank M. Carrano
@author Timothy M. Henry
@version 4.0
UPDATED by C. Lee-Klawender
NOTE: the LinkedQueue class includes the Node class as an inner class
*/
public class LinkedQueue
{
private Node frontNode; // References node at front of queue
private Node backNode; // References node at back of queue
private int count = 0;
public LinkedQueue()
{
frontNode = null;
backNode = null;
} // end default constructor
public boolean enqueue(T newEntry)
{
if(count == 0){
frontNode = new Node(newEntry);
backNode = frontNode;
} else {
if(backNode == frontNode){
backNode = frontNode.next;
backNode = new Node(newEntry);
} else {
backNode = backNode.next;
backNode = new Node(newEntry);
}
}
// ADD CODE TO add data to linked list HERE!
// In addition to updating the backNode, also
// make sure you check if the list was empty before adding this
// and update the correct variable if so
++count;
return true;
} // end enqueue
public T peekFront()
{
if (isEmpty())
return null;
else
return frontNode.getData();
} // end getFront
public T dequeue()
{
T front = peekFront();
if( count > 0 )
{
frontNode.data = null;
frontNode = frontNode.next;
// ADD CODE TO remove data from linked list HERE!
// In addition to updating the frontNode, also
// make sure to check if the list becomes empty and
// update the correct variable if so
--count;
}
return front;
} // end dequeue
public boolean isEmpty()
{
if(frontNode == null)
return true;
else
return false;
} // end isEmpty
public int size()
{
return count;
}
private class Node
{
private T data; // Entry in queue
private Node next; // Link to next node
private Node(T dataPortion)
{
data = dataPortion;
next = null;
} // end constructor
private Node(T dataPortion, Node linkPortion)
{
data = dataPortion;
next = linkPortion;
} // end constructor
private T getData()
{
return data;
} // end getData
private void setData(T newData)
{
data = newData;
} // end setData
private Node getNextNode()
{
return next;
} // end getNextNode
private void setNextNode(Node nextNode)
{
next = nextNode;
} // end setNextNode
} // end Node
} // end Linkedqueue
________________________________________________________________________
/**
* A class that implements the ADT queue by using an expandable circular array
* with one unused location after the back of the queue.
*
* @author Frank M. Carrano
* @author Timothy M. Henry
* @version 4.1 UPDATED BY C. Lee-Klawender
*/
public final class ArrayQueue
private T[] queue; // Circular array of queue entries
private int frontIndex; // Index of front entry
private int backIndex; // Index of back entry
private int count;
private static final int DEFAULT_CAPACITY = 5;
private static final int MAX_CAPACITY = 100;
public ArrayQueue() {
this(DEFAULT_CAPACITY);
} // end default constructor
public ArrayQueue(int initialCapacity) {
if (initialCapacity < DEFAULT_CAPACITY)
initialCapacity = DEFAULT_CAPACITY;
else if (initialCapacity > MAX_CAPACITY)
initialCapacity = MAX_CAPACITY;
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] tempQueue = (T[]) new Object[initialCapacity];
queue = tempQueue;
frontIndex = 0;
backIndex = queue.length - 1;
count = 0;
} // end constructor
public boolean enqueue(T newEntry) {
if (count < queue.length) {
backIndex = (backIndex + 1) % queue.length;
queue[backIndex] = newEntry;
++count;
return true;
} else
return false;
} // end enqueue
public T peekFront() {
if (isEmpty())
return null;
return queue[frontIndex];
} // end getFront
public T dequeue() {
if (isEmpty())
return null;
else {
--count;
T frontItem = queue[frontIndex];
queue[frontIndex] = null;
frontIndex = (frontIndex + 1) % queue.length; // Index of new front
// of queue
return frontItem;
} // end if
} // end dequeue
public boolean isEmpty() {
return count == 0;
} // end isEmpty
public int size() {
return count;
}
} // end ArrayQueue
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started