Java Problem Create a program using Java that will implement a stack object to c

ID: 646488 • Letter: J

Question

Java Problem

Create a program using Java that will implement a stack object to convert algebraic statements from either infix notation to postfix notation or vice-versa. The program will also have a link list data structure to track all the conversions done.

The Program should have a menu like the following:?

Please select what type of conversion you would like to do:

1) Infix to postfix

2) Postfix to infix

3) Print Equations

4) Exit

If the user selects the first option the user will enter the equation minus the assignment portion of the equation. So x= a+b; would just be a+b;.

You may assume that each operand is only a single character. Use the semicolon as the string termination.

The program should keep track of each conversion and add it into a link list structure.

When the user finally selects the Exit feature of the menu the List of all converted equations should be printed to the screen.

The link list node structure should be of a String Type.

You will find the Linked List and the Stack Code in the text.

------------------------------------

Definitions:

Infix notation: X + Y

Operators are written in-between their operands. This is the usual way we write expressions. An expression such as A * ( B + C ) / D is usually taken to mean something like: "First add B and C together, then multiply the result by A, then divide by D to give the final answer."

Infix notation needs extra information to make the order of evaluation of the operators clear: rules built into the language about operator precedence and associativity, and brackets ( ) to allow users to override these rules. For example, the usual rules for associativity say that we perform operations from left to right, so the multiplication by A is assumed to come before the division by D. Similarly, the usual rules for precedence say that we perform multiplication and division before we perform addition and subtraction.

Postfix notation (also known as "Reverse Polish notation"): X Y +

Operators are written after their operands. The infix expression given above is equivalent to A B C + * D / The order of evaluation of operators is always left-to-right, and brackets cannot be used to change this order. Because the "+" is to the left of the "*" in the example above, the addition must be performed before the multiplication. Operators act on values immediately to the left of them. For example, the "+" above uses the "B" and "C". We can add (totally unnecessary) brackets to make this explicit: ( (A (B C +) *) D /) Thus, the "*" uses the two values immediately preceding: "A", and the result of the addition. Similarly, the "/" uses the result of the multiplication and the "D".

------------------------------------

Algorithm for Infix to Postfix:

1. Initialize an operator stack.?

2. Input characters of infix string from left to right ignoring white spaces.?

3. IF character = operand THEN insert it into postfix output string.

4. IF character = operator AND stack is empty, THEN push operator onto stack.?

5. IF character = operator AND stack is not empty, THEN peek at the stack and compare the precedence of the popped operator with the newly read operator. IF peeked operator has less or equal precedence than the newly read character THEN leave the stack alone...ELSE move peeked operator to postfix string and pop the stack.?

6. Push the newly read operator onto the operator stack.?

7. When there are no more characters to read in the infix string, pop the operator stack and add the operators to the postfix string.

------------------------------------------------------------

Algorithm for Postfix Expression Evaluator:

1. Initialize an operand stack.?

2. Input characters of postfix string from left to right ignoring white spaces.?

3. IF character = operand THEN push it onto operand stack.?

4. IF character = operator THEN pop operand stack twice and perform operation of recently read operator on both popped operands. Push the result onto the top of the stack.?

5. IF there are no more characters to be read THEN pop the last number in the operand stack and display it as the final evaluated expression result.

_______________________________________________________________________

public interface LinkedListADT extends Cloneable
{
public Object clone();
//Returns a copy of objects data in store.
//This method only clone the references stored in
//each node of the list. The objects that the
//list nodes point to are not cloned.

public boolean isEmptyList();
//Method to determine whether the list is empty.
//Postcondition: Returns true if the list is empty;
// false otherwise.

public void initializeList();
//Method to initialize the list to an empty state.
//Postcondition: first = null, last = null,
// count = 0

public void print();
//Method to output the data contained in each node.

public int length();
//Method to return the number of nodes in the list.
//Postcondition: The value of count is returned.

public T front();
//Method to return a reference of the object containing
//the data of the first node of the list.
//Precondition: The list must exist and must not be empty.
//Postcondition: The reference of the object that
// contains the info of the first node
// is returned.

public T back();
//Method to return a reference of object containing
//the data of the last node of the list.
//Precondition: The list must exist and must not be empty.
//Postcondition: The reference of the object that
// contains the info of the last node
// is returned.

public boolean search(T searchItem);
//Method to determine whether searchItem is in the list.
//Postcondition: Returns true if searchItem is found
// in the list; false otherwise.

public void insertFirst(T newItem);
//Method to insert newItem in the list.
//Postcondition: first points to the new list
// and newItem is inserted at the
// beginning of the list. Also,
// last points to the last node and
// count is incremented by 1.

public void insertLast(T newItem);
//Method to insert newItem at the end of the list.
//Postcondition: first points to the new list and
// newItem is inserted at the end
// of the list. Also, last points to
// the last node and
// count is incremented by 1.

public void deleteNode(T deleteItem);
//Method to delete deleteItem from the list.
//Postcondition: If found, the node containing
// deleteItem is deleted from the
// list. Also first points to the first
// node, last points to the last
// node of the updated list, and count
// is decremented by 1.
}

_____________________________________________

import java.util.NoSuchElementException;

public abstract class LinkedListClass implements LinkedListADT
{
protected class LinkedListNode implements Cloneable
{
public T info;
public LinkedListNode link;

//Default constructor
//Postcondition: info = null; link = null;
public LinkedListNode()
{
info = null;
link = null;
}

//Constructor with parameters
//Sets info point to the object elem points to
//and link is set to point to the object ptr
//points to.
//Postcondition: info = elem; link = ptr
public LinkedListNode(T elem, LinkedListNode ptr)
{
info = elem;
link = ptr;
}

//Returns a copy of objects data in store.
//This method only clone the references stored in
//the node. The objects that the nodes point to
//is not cloned.
public Object clone()
{
LinkedListNode copy = null;

try
{
copy = (LinkedListNode) super.clone();

}
catch (CloneNotSupportedException e)
{
return null;
}

return copy;
}

//Method to return the info as a string.
//Postcondition: info as a String object is
// returned.
public String toString()
{
return info.toString();
}
} //end class LinkedListNode

public class LinkedListIterator
{
protected LinkedListNode current; //variable to
//point to the
//current node in
//list
protected LinkedListNode previous; //variable to
//point to the
//node before
//current

//Default constructor
//Sets current to point to the first node in the
//list and previous to null.
//Postcondition: current = first; previous = null;
public LinkedListIterator()
{
current = (LinkedListNode) first;
previous = null;
}

//Method to reset the iterator to the first node
//in the list.
//Postcondition: current = first; previous = null;
public void reset()
{
current = (LinkedListNode) first;
previous = null;
}

//Method to return a refrence of the current node
//in the list and also advance iterator to the
//next node.
//Postcondition: previous = current;
// current = current.link;
// A refrence of the current node
// is returned.
public T next()
{
if (!hasNext())
throw new NoSuchElementException();

LinkedListNode temp = current;

previous = current;
current = current.link;

return temp.info;
}

//Method to determine whether there is a next
//element in the list.
//Postcondition: Returns true, if there is a next
// node in the list; otherwise
// returns false.
public boolean hasNext()
{
return (current != null);
}

//Method to remove the node currently pointed to
//by the iterator.
//Postcondition: If iterator is not null, then the
// nodes that the iterator point to
// is removed. Otherwise the method
// throws NoSuchElementException.
public void remove()
{
if (current == null)
throw new NoSuchElementException();

if (current == first)
{
first = first.link;
current = (LinkedListNode) first;
previous = null;

if (first == null)
last = null;
}
else
{
previous.link = current.link;

if (current == last)
{
last = first;
while (last.link != null)
last = last.link;
}

current = current.link;
}

count--;
}

//Method to return the info as a string.
//Postcondition: info as a String object is returned.
public String toString()
{
return current.info.toString();
}

} //end class LinkedListIterator

//Instance variables of the class LinkedListClass
protected LinkedListNode first; //variable to store the
//address of the first
//node of the list
protected LinkedListNode last; //variable to store the
//address of the last
//node of the list
protected int count; //variable to store the number of
//nodes in the list

//Default constructor
//Initializes the list to an empty state.
//Postcondition: first = null, last = null,
// count = 0
public LinkedListClass()
{
first = null;
last = null;
count = 0;
}

//Method to determine whether the list is empty.
//Postcondition: Returns true if the list is empty;
// false otherwise.
public boolean isEmptyList()
{
return (first == null);
}

//Method to initialize the list to an empty state.
//Postcondition: first = null, last = null,
// count = 0
public void initializeList()
{
first = null;
last = null;
count = 0;
}

//Method to output the data contained in each node.
public void print()
{
LinkedListNode current; //variable to traverse
//the list

current = first; //set current so that it points to
//the first node
while (current != null) //while more data to print
{
System.out.print(current.info + " ");
current = current.link;
}
}//end print

//Method to return the number of nodes in the list.
//Postcondition: The value of count is returned.
public int length()
{
return count;
}

//Method to return a reference of the object containing
//the data of the first node of the list.
//Precondition: The list must exist and must not be empty.
//Postcondition: The reference of the object that
// contains the info of the first node
// is returned.
public T front()
{
return first.info;
}

//Method to return a reference of object containing
//the data of the last node of the list.
//Precondition: The list must exist and must not be empty.
//Postcondition: The reference of the object that
// contains the info of the last node
// is returned.
public T back()
{
return last.info;
}

//Returns a copy of objects data in store.
//This method only clone the references stored in
//each node of the list. The objects that the
//list nodes point to are not cloned.
public Object clone()
{
LinkedListClass copy = null;

try
{
copy = (LinkedListClass) super.clone();

}
catch (CloneNotSupportedException e)
{
return null;
}

//If the list is not empty clone each node of
//the list.
if (first != null)
{
//Clone the first node
copy.first = (LinkedListNode) first.clone();
copy.last = copy.first;

LinkedListNode current;

if (first != null)
current = first.link;
else
current = null;

//Clone the remaining nodes of the list
while (current != null)
{
copy.last.link =
(LinkedListNode) current.clone();
copy.last = copy.last.link;
current = current.link;
}
}

return copy;
}

//Method to return an iterator of the list.
//Postcondition: An iterator is instantiated and
// returned.
public LinkedListIterator iterator()
{
return new LinkedListIterator();
}

//Method to determine whether searchItem is in
//the list.
//Postcondition: Returns true if searchItem is found
// in the list; false otherwise.
public abstract boolean search(T searchItem);

//Method to insert newItem in the list.
//Postcondition: first points to the new list
// and newItem is inserted at the
// beginning of the list. Also,
// last points to the last node and
// count is incremented by 1.
public abstract void insertFirst(T newItem);

//Method to insert newItem at the end of the list.
//Postcondition: first points to the new list and
// newItem is inserted at the end
// of the list. Also, last points to
// the last node and
// count is incremented by 1.
public abstract void insertLast(T newItem);

//Method to delete deleteItem from the list.
//Postcondition: If found, the node containing
// deleteItem is deleted from the
// list. Also first points to the first
// node, last points to the last
// node of the updated list, and count
// is decremented by 1.
public abstract void deleteNode(T deleteItem);
}

___________________________________________

public class LinkedStackClass extends UnorderedLinkedList
{
public LinkedStackClass()
{
super();
}

public void initializeStack()
{
initializeList();
}

public boolean isEmptyStack()
{
return isEmptyList();
}

public boolean isFullStack()
{
return false;
}

public void push(T newElement)
{
insertFirst(newElement);
} //end push

public T peek() throws StackUnderflowException
{
if (first == null)
throw new StackUnderflowException();

return front();
} //end peek

public void pop()throws StackUnderflowException
{
if (first == null)
throw new StackUnderflowException();

first = first.link;

count--;

if (first == null)
last = null;
}//end pop
}

__________________________________________

public class StackException extends RuntimeException
{
public StackException()
{
}

public StackException(String msg)
{
super(msg);
}
}

______________________________________________

public class StackOverflowException extends StackException
{
public StackOverflowException()
{
super("Stack Overflow");
}

public StackOverflowException(String msg)
{
super(msg);
}
}

____________________________________________

public class StackUnderflowException extends StackException
{
public StackUnderflowException()
{
super("Stack Underflow");
}

public StackUnderflowException(String msg)
{
super(msg);
}
}

__________________________________________

public class UnorderedLinkedList extends LinkedListClass
{
//Default constructor
public UnorderedLinkedList()
{
super();
}

//Method to determine whether searchItem is in
//the list.
//Postcondition: Returns true if searchItem is found
// in the list; false otherwise.
public boolean search(T searchItem)
{
LinkedListNode current; //variable to traverse
//the list
boolean found;

current = first; //set current to point to the first
//node in the list

found = false; //set found to false

while (current != null && !found) //search the list
if (current.info.equals(searchItem)) //item is found
found = true;
else
current = current.link; //make current point to
//the next node
return found;
}

newNode =
new LinkedListNode(newItem, first); //create and
//insert newNode before
//first

first = newNode; //make first point to the
//actual first node

if (last == null) //if the list was empty, newNode is
//also the last node in the list
last = newNode;

count++; //increment count
}

newNode =
new LinkedListNode(newItem, null); //create newNode

if (first == null) //if the list is empty, newNode is
//both the first and last node
{
first = newNode;
last = newNode;
}
else //if the list is not empty, insert
//newNode after last
{
last.link = newNode; //insert newNode after last
last = newNode; //set last to point to the
//actual last node
}

count++;
}//end insertLast

if ( first == null) //Case 1; the list is empty
System.err.println("Cannot delete from an empty "
+ "list.");
else
{
if (first.info.equals(deleteItem)) //Case 2
{
first = first.link;

if (first == null) //the list had only one node
last = null;
count--;
}
else //search the list for the given info
{
found = false;
trailCurrent = first; //set trailCurrent to
//point to the first node
current = first.link; //set current to point to
//the second node

while (current != null && !found)
{
if (current.info.equals(deleteItem))
found = true;
else
{
trailCurrent = current;
current = current.link;
}
}//end while

if (found) //Case 3; if found, delete the node
{
count--;
trailCurrent.link = current.link;

if (last == current) //node to be deleted
//was the last node
last = trailCurrent; //update the value
//of last
}
else
System.out.println("Item to be deleted is "
+ "not in the list.");
}//end else
}//end else
}//end deleteNode
}

Explanation / Answer

import java.util.Scanner;

import java.util.Stack;

public class PostfixToInfix {

/**

* Checks if the input is operator or not

* @param c input to be checked

* @return true if operator

private boolean isOperator(char c){

if(c == '+' || c == '-' || c == '*' || c =='/' || c == '^')

return true;

return false;

}

/**

* Converts any postfix to infix

* @param postfix String expression to be converted

* @return String infix expression produced

public String convert(String postfix){

Stack<String> s = new Stack<>();

for(int i = 0; i < postfix.length(); i++){

char c = postfix.charAt(i);

if(isOperator(c)){

String b = s.pop();

String a = s.pop();

s.push("("+a+c+b+")");

}

else

s.push(""+c);

}

return s.pop();

}

public static void main(String[] args) {

PostfixToInfix obj = new PostfixToInfix();

Scanner sc =new Scanner(System.in);

System.out.print("Postfix : ");

String postfix = sc.next();

System.out.println("Infix : "+obj.convert(postfix));

}

Navigate

Java Problem Create a class to hold Event data for Carly’s Catering. The class c

Java Problem Description/Purpose: Write a program to accept a String of 5 charac

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Java Problem Create a program using Java that will implement a stack object to c

Question

Explanation / Answer

Related Questions

Navigate