2: Do programming project 9 from Chapter 6 of the textbook. Name your program ComputeInfix.java. Your program should prompt the user to enter an arithmetic expression and output the value of the expression. Assume that the input contains integers (no variables), operations +, -, *, /, and parenthesis ( and ). No other characters should be in the input string. The integers are all non-negative. You may assume that input expression always has correct syntax (balanced parentheses, etc.) Your program does not have to detect syntactic errors in the expression. Integers may have more than one digit in them, e.g. 25, 143, etc. To extract integers from a strings you may use the following method: How to extract an integer from a string Dialog with the user may look like the following: Please enter an expression: 6+(2+3*4)/2 The expression evaluates to 13

***********************************************************************************************

Hints:

Pseudocode to evaluate an infix expression without full parentheses is the following:

1. Initialize two stacks: a numbers stack and an operators stack.

2. do if (the next input is a left parenthesis) Read the left parenthesis and push it onto the operators stack else if (the next input is a number) Read the number and push it onto the numbers stack else if (the next input is one of the operation symbols) { while (1) the operators stack is not empty, and (2) the top symbol on the operators stack is NOT a left parenthesis, and (3) the top symbol on the operators stack is NOT an operation with lower precedence than the next input do the following: pop an operation off the operators stack and use that operation by popping two numbers off the numbers stack, applying the operation to the two numbers, and pushing the answer back on the numbers stack After finishing the while loop read the next input (operation) and push it onto the operators stack } else { Read and discard the next input symbol (which should be a right parenthesis). while the top symbol on operators stack is NOT a left parenthesis and the operators stack is not empty do the following: pop operation off the operators stack and use that operation by popping two numbers off the numbers stack, applying the operation to the two numbers, and pushing the answer back on the numbers stack If no left parenthesis is encountered in the operators stack, then print an error message indicating unbalanced parentheses and halt. Pop and discard the left parentheses from the operators stack. } while (there is more of the expression to read)

3. while the operators stack is not empty do the following: pop operation off the operators stack and use that operation by popping two numbers off the numbers stack, applying the operation to the two numbers, and pushing the answer back on the numbers stack (There should be no remaining left parentheses; otherwise, the input expression did not have balanced parentheses.) __________________________________

If the infix expression has correct syntax (balanced parentheses, etc.), then after execution of the pseudocode, the operators stack will be empty and the numbers stack will contain one number which is the value of the expression.

Class LinkedStack:

// File: LinkedStack.java from the package edu.colorado.collections

// Complete documentation is available from the LinkedStack link in:

// http://www.cs.colorado.edu/~main/docs/

// package edu.colorado.collections;

import java.util.EmptyStackException;

// import edu.colorado.nodes.Node;

/*************************************************************************

*****

* A LinkedStack is a stack of references to

* Eobjects.

*

*

Limitations:

* Beyond Int.MAX_VALUE items, size is wrong.

*

*

*

Java Source Code for this class:

*

* http://www.cs.colorado.edu/~main/edu/colorado/collections/LinkedStack.j

ava

*

*

* @author Michael Main

* (main@colorado.edu)

*

* @version

* Jul 21, 2005

*

* @see ArrayStack

**************************************************************************

****/

public class LinkedStack implements Cloneable

{

// Invariant of the LinkedStack class:

// 1. The items in the stack are stored in a linked list, with the

top of

// the stack stored at the head node, down to the bottom of the

stack

// at the final node.

// 2. The instance variable top is the head reference of the linked

list

// of items.

private Node top;

/**

* Initialize an empty stack.

* @param - none

*

Postcondition:

* This stack is empty.

**/

public LinkedStack( )

{

top = null;

}

/**

* Generate a copy of this stack.

* @param - none

* @return

* The return value is a copy of this stack. Subsequent changes to the

* copy will not affect the original, nor vice versa.

* @exception OutOfMemoryError

* Indicates insufficient memory for creating the clone.

**/

public LinkedStack clone( )

{ // Clone a LinkedStack.

LinkedStack answer;

try

{

answer = (LinkedStack) super.clone( );

}

catch (CloneNotSupportedException e)

{

// This exception should not occur. But if it does, it would

probably indicate a

// programming error that made super.clone unavailable. The most

comon error

// The most common error would be forgetting the "Implements

Cloneable"

// clause at the start of this class.

throw new RuntimeException

("This class does not implement Cloneable");

}

// The generic listCopy method gets the type of E from top.

answer.top = Node.listCopy(top);

return answer;

}

/**

* Determine whether this stack is empty.

* @param - none

* @return

* true if this stack is empty;

* false otherwise.

**/

public boolean isEmpty( )

{

return (top == null);

}

/**

* Get the top item of this stack, without removing the item.

* @param - none

*

Precondition:

* This stack is not empty.

* @return

* the top item of the stack

* @exception EmptyStackException

* Indicates that this stack is empty.

**/

public E peek( )

{

if (top == null)

// EmptyStackException is from java.util and its constructor has

no argument.

throw new EmptyStackException( );

return top.getData( );

}

/**

* Get the top item, removing it from this stack.

* @param - none

*

Precondition:

* This stack is not empty.

*

Postcondition:

* The return value is the top item of this stack, and the item has

* been removed.

* @exception EmptyStackException

* Indicates that this stack is empty.

**/

public E pop( )

{

E answer;

if (top == null)

// EmptyStackException is from java.util and its constructor has

no argument.

throw new EmptyStackException( );

answer = top.getData( );

top = top.getLink( );

return answer;

}

/**

* Push a new item onto this stack. The new item may be the null

* reference.

* @param item

* the item to be pushed onto this stack

*

Postcondition:

* The item has been pushed onto this stack.

* @exception OutOfMemoryError

* Indicates insufficient memory for increasing the stack's capacity.

**/

public void push(E item)

{

top = new Node(item, top);

}

/**

* Accessor method to determine the number of items in this stack.

* @param - none

* @return

* the number of items in this stack

**/

public int size( )

{

// The generic listLength method gets the type of E from top.

return Node.listLength(top);

}

/**

* Return a string representation of this stack. The string

* returned by this method will show the stack with top on the left

* and bottom on the right, elements separated by '|'

*

* @return a string representation of this stack.

**/

public String toString()

{

if (top != null)

{

String answer = "";

Node current = top;

while (current != null)

{

answer = answer + current.getData() + "|";

current = current.getLink();

}

return answer;

}

else return "|";

}

}

Class Node.java:

// File: Node.java from the package edu.colorado.nodes

// Complete documentation is available from the Node link in:

// http://www.cs.colorado.edu/~main/docs

// package edu.colorado.nodes;

/*************************************************************************

*****

* A Node provides a generic node for a linked list. Each node

* contains a piece of data (which is a reference to an E object) and a

link

* (which is a reference to the next node of the list). The reference

stored

* in a node can be null.

*

* @note

* Lists of nodes can be made of any length, limited only by the amount of

* free memory in the heap. But beyond Integer.MAX_VALUE (2,147,483,647),

* the answer from listLength is incorrect because of arithmetic

* overflow.

* @see

*

* Java Source Code for this class

* (www.cs.colorado.edu/~main/edu/colorado/nodes/Node.java)

*

* @author Michael Main

* (main@colorado.edu)

*

* @version

* Jul 17, 2005

*

* @see BooleanNode

* @see ByteNode

* @see CharNode

* @see DoubleNode

* @see FloatNode

* @see IntNode

* @see LongNode

* @see ShortNode

**************************************************************************

****/

public class Node

{

// Invariant of the Node class:

// 1. Each node has one reference to an E Object, stored in the

instance

// variable data.

// 2. For the final node of a list, the link part is null.

// Otherwise, the link part is a reference to the

// next node of the list.

private E data;

private Node link;

/**

* Initialize a node with a specified initial data and link to the next

* node. Note that the initialLink may be the null reference,

* which indicates that the new node has nothing after it.

* @param initialData

* the initial data of this new node

* @param initialLink

* a reference to the node after this new node--this reference may be

null

* to indicate that there is no node after this new node.

* @postcondition

* This node contains the specified data and link to the next node.

**/

public Node(E initialData, Node initialLink)

{

data = initialData;

link = initialLink;

}

/**

* Modification method to add a new node after this node.

* @param element

* the data to place in the new node

* @postcondition

* A new node has been created and placed after this node.

* The data for the new node is element. Any other nodes

* that used to be after this node are now after the new node.

* @exception OutOfMemoryError

* Indicates that there is insufficient memory for a new

* Node.

**/

public void addNodeAfter(E element)

{

link = new Node(element, link);

}

/**

* Accessor method to get the data from this node.

* @param - none

* @return

* the data from this node

**/

public E getData( )

{

return data;

}

/**

* Accessor method to get a reference to the next node after this node.

* @param - none

* @return

* a reference to the node after this node (or the null reference if

there

* is nothing after this node)

**/

public Node getLink( )

{

return link;

}

/**

* Copy a list.

* @param source

* the head of a linked list that will be copied (which may be

* an empty list in where source is null)

* @return

* The method has made a copy of the linked list starting at

* source. The return value is the head reference for the

* copy.

* @exception OutOfMemoryError

* Indicates that there is insufficient memory for the new list.

**/

public static Node listCopy(Node source)

{

Node copyHead;

Node copyTail;

// Handle the special case of the empty list.

if (source == null)

return null;

// Make the first node for the newly created list.

copyHead = new Node(source.data, null);

copyTail = copyHead;

// Make the rest of the nodes for the newly created list.

while (source.link != null)

{

source = source.link;

copyTail.addNodeAfter(source.data);

copyTail = copyTail.link;

}

// Return the head reference for the new list.

return copyHead;

}

/**

* Copy a list, returning both a head and tail reference for the copy.

* @param source

* the head of a linked list that will be copied (which may be

* an empty list in where source is null)

* @return

* The method has made a copy of the linked list starting at

* source. The return value is an

* array where the [0] element is a head reference for the copy and the

[1]

* element is a tail reference for the copy.

* @exception OutOfMemoryError

* Indicates that there is insufficient memory for the new list.

**/

public static Node[ ] listCopyWithTail(Node source)

{

Node copyHead;

Node copyTail;

Node[ ] answer = (Node[]) new Object[2];

// Handle the special case of the empty list.

if (source == null)

return answer; // The answer has two null references .

// Make the first node for the newly created list.

copyHead = new Node(source.data, null);

copyTail = copyHead;

// Make the rest of the nodes for the newly created list.

while (source.link != null)

{

source = source.link;

copyTail.addNodeAfter(source.data);

copyTail = copyTail.link;

}

// Return the head and tail references.

answer[0] = copyHead;

answer[1] = copyTail;

return answer;

}

/**

* Compute the number of nodes in a linked list.

* @param head

* the head reference for a linked list (which may be an empty list

* with a null head)

* @return

* the number of nodes in the list with the given head

* @note

* A wrong answer occurs for lists longer than Int.MAX_VALUE.

**/

public static int listLength(Node head)

{

Node cursor;

int answer;

answer = 0;

for (cursor = head; cursor != null; cursor = cursor.link)

answer++;

return answer;

}

/**

* Copy part of a list, providing a head and tail reference for the new

copy.

* @param start/end

* references to two nodes of a linked list

* @param copyHead/copyTail

* the method sets these to refer to the head and tail node of the new

* list that is created

* @precondition

* start and end are non-null references to nodes

* on the same linked list,

* with the start node at or before the end node.

* @return

* The method has made a copy of the part of a linked list, from the

* specified start node to the specified end node. The return value is

an

* array where the [0] component is a head reference for the copy and

the

* [1] component is a tail reference for the copy.

* @exception IllegalArgumentException

* Indicates that start and end do not satisfy

* the precondition.

* @exception OutOfMemoryError

* Indicates that there is insufficient memory for the new list.

**/

public static Node[ ] listPart(Node start, Node end)

{

Node copyHead;

Node copyTail;

Node cursor;

Node[ ] answer = (Node[]) new Object[2];

// Check for illegal null at start or end.

if (start == null)

throw new IllegalArgumentException("start is null");

if (end == null)

throw new IllegalArgumentException("end is null");

// Make the first node for the newly created list.

copyHead = new Node(start.data, null);

copyTail = copyHead;

cursor = start;

// Make the rest of the nodes for the newly created list.

while (cursor != end)

{

cursor = cursor.link;

if (cursor == null)

throw new IllegalArgumentException

("end node was not found on the list");

copyTail.addNodeAfter(cursor.data);

copyTail = copyTail.link;

}

// Return the head and tail references

answer[0] = copyHead;

answer[1] = copyTail;

return answer;

}

/**

* Find a node at a specified position in a linked list.

* @param head

* the head reference for a linked list (which may be an empty list in

* which case the head is null)

* @param position

* a node number

* @precondition

* position > 0.

* @return

* The return value is a reference to the node at the specified

position in

* the list. (The head node is position 1, the next node is position 2,

and

* so on.) If there is no such position (because the list is too

short),

* then the null reference is returned.

* @exception IllegalArgumentException

* Indicates that position is zero.

**/

public static Node listPosition(Node head, int position)

{

Node cursor;

int i;

if (position == 0)

throw new IllegalArgumentException("position is zero");

cursor = head;

for (i = 1; (i < position) && (cursor != null); i++)

cursor = cursor.link;

return cursor;

}

/**

* Search for a particular piece of data in a linked list.

* @param head

* the head reference for a linked list (which may be an empty list in

* which case the head is null)

* @param target

* a target to search for

* @return

* The return value is a reference to the first node that contains the

* specified target. If the target is non-null, then the

* target.equals method is used to find such a node.

* The target may also be null, in which case the return value is a

* reference to the first node that contains a null reference for its

* data. If there is no node that contains the target, then the null

* reference is returned.

**/

public static Node listSearch(Node head, E target)

{

Node cursor;

if (target == null)

{ // Search for a node in which the data is the null reference.

for (cursor = head; cursor != null; cursor = cursor.link)

if (cursor.data == null)

return cursor;

}

else

{ // Search for a node that contains the non-null target.

for (cursor = head; cursor != null; cursor = cursor.link)

if (target.equals(cursor.data))

return cursor;

}

return null;

}

/**

* Modification method to remove the node after this node.

* @param - none

* @precondition

* This node must not be the tail node of the list.

* @postcondition

* The node after this node has been removed from the linked list.

* If there were further nodes after that one, they are still

* present on the list.

* @exception NullPointerException

* Indicates that this was the tail node of the list, so there is

nothing

* after it to remove.

**/

public void removeNodeAfter( )

{

link = link.link;

}

/**

* Modification method to set the data in this node.

* @param newData

* the new data to place in this node

* @postcondition

* The data of this node has been set to newData.

* This data is allowed to be null.

**/

public void setData(E newData)

{

data = newData;

}

/**

* Modification method to set the link to the next node after this

node.

* @param newLink

* a reference to the node that should appear after this node in the

linked

* list (or the null reference if there is no node after this node)

* @postcondition

* The link to the node after this node has been set to newLink.

* Any other node (that used to be in this link) is no longer connected

to

* this node.

**/

public void setLink(Node newLink)

{

link = newLink;

}

}

Thank you!