Java Homework
elpsy69
Devoir1.zipex1/tryStack2.java
ex1/tryStack2.java
class
tryStack2
{
public
static
void
main
(
String
[]
args
)
{
Integer
[]
arr
=
new
Integer
[
50
];
for
(
int
i
=
0
;
i
<
50
;
i
++
)
{
arr
[
i
]
=
new
Integer
(
i
*
2
);
}
printA
(
arr
);
arr
=
reverse
(
arr
);
printA
(
arr
);
}
/* main */
public
static
Integer
[]
reverse
(
Integer
[]
a
)
{
NodeStack
S
=
new
NodeStack
();
Integer
[]
b
=
new
Integer
[
a
.
length
];
for
(
int
i
=
0
;
i
<
a
.
length
;
i
++
)
{
S
.
push
(
a
[
i
]
);
}
for
(
int
i
=
0
;
i
<
a
.
length
;
i
++
)
{
b
[
i
]
=
(
Integer
)
(
S
.
pop
()
);
}
return
b
;
}
/* reverse */
public
static
void
printA
(
Integer
[]
a
)
{
System
.
out
.
println
();
for
(
int
i
=
0
;
i
<
50
;
i
++
)
{
System
.
out
.
print
(
a
[
i
].
intValue
()
+
"\t"
);
}
System
.
out
.
println
();
}
/* printA */
}
ex1/tryStack1.java
ex1/tryStack1.java
class
tryStack1
{
public
static
void
main
(
String
[]
args
)
{
Integer
[]
arr
=
new
Integer
[
50
];
for
(
int
i
=
0
;
i
<
50
;
i
++
)
{
arr
[
i
]
=
new
Integer
(
i
*
2
);
}
printA
(
arr
);
arr
=
reverse
(
arr
);
printA
(
arr
);
}
/* main */
public
static
Integer
[]
reverse
(
Integer
[]
a
)
{
ArrayStack
S
=
new
ArrayStack
(
a
.
length
);
Integer
[]
b
=
new
Integer
[
a
.
length
];
for
(
int
i
=
0
;
i
<
a
.
length
;
i
++
)
{
S
.
push
(
a
[
i
]
);
}
for
(
int
i
=
0
;
i
<
a
.
length
;
i
++
)
{
b
[
i
]
=
(
Integer
)
(
S
.
pop
()
);
}
return
b
;
}
/* reverse */
public
static
void
printA
(
Integer
[]
a
)
{
System
.
out
.
println
();
for
(
int
i
=
0
;
i
<
50
;
i
++
)
{
System
.
out
.
print
(
a
[
i
].
intValue
()
+
"\t"
);
}
System
.
out
.
println
();
}
/* printA */
}
ex1/Stack.java
ex1/Stack.java
/**
* Interface for a stack: a collection of objects that are inserted
* and removed according to the last-in first-out principle.
*
*
@author
Roberto Tamassia
*
@author
Michael Goodrich
*
@see
EmptyStackException
*/
public
interface
Stack
{
/**
* Return the number of elements in the stack.
*
@return
number of elements in the stack.
*/
public
int
size
();
/**
* Return whether the stack is empty.
*
@return
true if the stack is empty, false otherwise.
*/
public
boolean
isEmpty
();
/**
* Inspect the element at the top of the stack.
*
@return
top element in the stack.
*
@exception
EmptyStackException if the stack is empty.
*/
public
Object
top
()
throws
EmptyStackException
;
/**
* Insert an element at the top of the stack.
*
@param
element element to be inserted.
*/
public
void
push
(
Object
element
);
/**
* Remove the top element from the stack.
*
@return
element removed.
*
@exception
EmptyStackException if the stack is empty.
*/
public
Object
pop
()
throws
EmptyStackException
;
}
ex1/NodeStack.java
ex1/NodeStack.java
/**
* Implementation of Stack interface, based on Node class (dynamic).
*/
public
class
NodeStack
implements
Stack
{
// reference to the head node
protected
Node
top
;
// number of elements in the stack
protected
int
size
;
/**
* Constructor fo NodeStack class.
*
@return
an empty stack
*/
public
NodeStack
()
{
top
=
null
;
size
=
0
;
}
public
int
size
()
{
return
size
;
}
/* size */
public
boolean
isEmpty
()
{
if
(
top
==
null
)
return
true
;
return
false
;
}
/* isEmpty */
public
Object
top
()
throws
EmptyStackException
{
if
(
isEmpty
()
)
throw
new
EmptyStackException
(
"Stack is empty."
);
return
top
.
getElement
();
}
/* top */
public
void
push
(
Object
elem
)
{
// create and link-in a new node
Node
v
=
new
Node
(
elem
,
top
);
top
=
v
;
size
++
;
}
/* push */
public
Object
pop
()
throws
EmptyStackException
{
if
(
isEmpty
()
)
throw
new
EmptyStackException
(
"Stack is empty."
);
Object
temp
=
top
.
getElement
();
// link-out the former top node
top
=
top
.
getNext
();
size
--
;
return
temp
;
}
/* pop */
}
ex1/Node.java
ex1/Node.java
/**
* Node used for chained data structures.
* This class is used to create a single element in such chains (simple chained).
*/
public
class
Node
{
// Element in the node.
private
Object
element
;
// Next element after this node.
private
Node
next
;
/**
* Node class constructor without parameters.
*
@return
a node with null reference to its element and next node.
*/
public
Node
()
{
this
(
null
,
null
);
}
/**
* Node class constructor given an object and next node.
*
@param
Object e element to store in the node
*
@param
Node n next node
*
@return
created node with element e and next node n
*/
public
Node
(
Object
e
,
Node
n
)
{
element
=
e
;
next
=
n
;
}
/** Getters */
public
Object
getElement
()
{
return
element
;
}
/* getElement */
public
Node
getNext
()
{
return
next
;
}
/* getNext */
/** Setters */
public
void
setElement
(
Object
newElem
)
{
element
=
newElem
;
}
/* setElement */
public
void
setNext
(
Node
newNext
)
{
next
=
newNext
;
}
/* setNext */
}
ex1/FullStackException.java
ex1/FullStackException.java
/**
* Runtime exception thrown when one tries to perform operation push
* on a full stack.
*/
public
class
FullStackException
extends
RuntimeException
{
public
FullStackException
(
String
err
)
{
super
(
err
);
}
}
ex1/EmptyStackException.java
ex1/EmptyStackException.java
/**
* Runtime exception thrown when one tries to perform operation top or
* pop on an empty stack.
*/
public
class
EmptyStackException
extends
RuntimeException
{
public
EmptyStackException
(
String
err
)
{
super
(
err
);
}
}
ex1/ArrayStack.java
ex1/ArrayStack.java
/**
* Implementation of the Stack interface using a fixed-length array.
* An exception is thrown if a push operation is attempted when the
* size of the stack is equal to the length of the array.
*
*
@author
Natasha Gelfand
*
@author
Roberto Tamassia
*
@see
FullStackException
*/
public
class
ArrayStack
implements
Stack
{
// Default length of the array used to implement the stack.
public
static
final
int
CAPACITY
=
1000
;
// Length of the array used to implement the stack.
protected
int
capacity
;
// Array used to implement the stack.
protected
Object
S
[];
// Index of the top element of the stack in the array.
protected
int
top
=
-
1
;
/**
* ArrayStack class constructor, with no parameter.
* Default length used for the array is CAPACITY.
*/
public
ArrayStack
()
{
this
(
CAPACITY
);
}
/**
* ArrayStack class constructor.
*
@param
cap length of the array.
*/
public
ArrayStack
(
int
cap
)
{
capacity
=
cap
;
S
=
new
Object
[
capacity
];
}
public
int
size
()
{
return
(
top
+
1
);
}
/* size */
public
boolean
isEmpty
()
{
return
(
top
<
0
);
}
/* isEmpty */
public
Object
top
()
throws
EmptyStackException
{
if
(
isEmpty
()
)
throw
new
EmptyStackException
(
"Stack is empty."
);
return
S
[
top
];
}
/* top */
/**
* Be careful here, this implementation may throw an exception.
*
@exception
FullStackException if the array is full.
*/
public
void
push
(
Object
obj
)
throws
FullStackException
{
if
(
size
()
==
capacity
)
throw
new
FullStackException
(
"Stack overflow."
);
S
[
++
top
]
=
obj
;
}
/* push */
public
Object
pop
()
throws
EmptyStackException
{
if
(
isEmpty
()
)
throw
new
EmptyStackException
(
"Stack is Empty."
);
Object
elem
=
S
[
top
];
// dereference S[top] for garbage collection.
S
[
top
--
]
=
null
;
return
elem
;
}
/* pop */
}
ex2/TestDLinkedList.java
ex2/TestDLinkedList.java
/**
* Class to test doubly linked list
*
@author
Jeff Souza
*/
class
TestDLinkedList
{
public
static
void
main
(
String
[]
args
)
{
// Create a new node, with data = 1
ListNode
nNode
=
new
ListNode
();
nNode
.
data
=
1
;
// Create a new doubl- linked list with the node
DLinkedList
list
=
new
DLinkedList
();
list
.
firstNode
=
nNode
;
list
.
lastNode
=
nNode
;
// Add items to linked list (2, 3, 4, 5, 6, 7 , 8, 9 and 10)
for
(
int
i
=
2
;
i
<
11
;
i
++
)
{
nNode
=
new
ListNode
();
nNode
.
data
=
i
;
list
.
AppendNode
(
nNode
);
}
// Print the content of the list
System
.
out
.
println
();
list
.
print
();
// Remove items from linked list (2 first elements and the last one)
System
.
out
.
println
(
"items removed."
);
list
.
RemoveNode
(
list
.
firstNode
);
list
.
RemoveNode
(
list
.
firstNode
);
list
.
RemoveNode
(
list
.
lastNode
);
// Print the content of the list
list
.
print
();
}
/* main */
}
ex2/ListNode.java
ex2/ListNode.java
/**
* Class node of a doubly linked list.
*
@author
Jeff Souza
*/
class
ListNode
{
// Node data
int
data
;
// Next node
ListNode
next
;
// Previous node
ListNode
previous
;
}
ex2/DLinkedList.java
ex2/DLinkedList.java
/**
* Class doubly linked list.
*
@author
Jeff Souza
*/
class
DLinkedList
{
// First node of the list.
ListNode
firstNode
;
// Last node of the list.
ListNode
lastNode
;
/**
* Appends a node to the end of the list.
*
@param
ListNode nNode Node to append.
*/
void
AppendNode
(
ListNode
nNode
)
{
InsertNode
(
nNode
,
lastNode
);
}
/* AppendNode */
/**
* Inserts a node into the list after pAfter node.
*
@param
ListNode nNode Node to insert.
*
@param
ListNode pAfter Node after which the insertion is done.
*/
void
InsertNode
(
ListNode
nNode
,
ListNode
pAfter
)
{
// INSERT YOUR CODE HERE
}
/* InsertNode */
/**
* Removes the specified node from the list.
*
@param
ListNode nNode Node to remove.
*/
void
RemoveNode
(
ListNode
nNode
)
{
// INSERT YOUR CODE HERE
}
/* RemoveNode */
/**
* Prints the content of the list.
*/
void
print
()
{
ListNode
nNode
=
null
;
System
.
out
.
print
(
"Current list: "
);
for
(
nNode
=
firstNode
;
nNode
!=
null
;
nNode
=
nNode
.
next
)
{
System
.
out
.
print
(
nNode
.
data
+
" "
);
}
System
.
out
.
println
(
""
);
}
/* print */
}
ex3/FullStackException.java
ex3/FullStackException.java
/**
* Runtime exception thrown when one tries to perform operation push
* on a full stack.
*/
public
class
FullStackException
extends
RuntimeException
{
public
FullStackException
(
String
err
)
{
super
(
err
);
}
}
ex3/EmptyStackException.java
ex3/EmptyStackException.java
/**
* Runtime exception thrown when one tries to perform operation top or
* pop on an empty stack.
*/
public
class
EmptyStackException
extends
RuntimeException
{
public
EmptyStackException
(
String
err
)
{
super
(
err
);
}
}
ex3/Stack.java
ex3/Stack.java
/**
* Interface for a stack: a collection of objects that are inserted
* and removed according to the last-in first-out principle.
*
*
@see
EmptyStackException, FullStackException
*/
public
interface
Stack
{
/**
* Return the number of elements in the stack.
*
@return
number of elements in the stack.
*/
public
int
size
();
/**
* Return whether the stack is empty.
*
@return
true if the stack is empty, false otherwise.
*/
public
boolean
isEmpty
();
/**
* Inspect the element at the top of the stack.
*
@return
top element in the stack.
*
@exception
EmptyStackException if the stack is empty.
*/
public
Object
top
()
throws
EmptyStackException
;
/**
* Insert an element at the top of the stack.
*
@param
element element to be inserted.
*
@throws
FullStackException if the array to handle stack is full
*/
public
void
push
(
Object
element
)
throws
FullStackException
;
/**
* Remove the top element from the stack.
*
@return
element removed.
*
@exception
EmptyStackException if the stack is empty.
*/
public
Object
pop
()
throws
EmptyStackException
;
}
ex3/bracketsBalance.java
ex3/bracketsBalance.java
/* CSI2114 Lab 3 - lab3.java
*
* Class to check balanced brackets in math expressions
*
* Usage: java bracketsBalance <exp>
*
* by Jeff Souza
*
*/
class
bracketsBalance
{
private
boolean
bBalance
(
String
exp
)
{
// INSERT YOUR CODE HERE
return
false
;
}
/* bBalance */
public
static
void
main
(
String
[]
args
)
{
bracketsBalance b
=
new
bracketsBalance
();
boolean
result
=
b
.
bBalance
(
args
[
0
]
);
if
(
result
)
System
.
out
.
println
(
"The expression is balanced."
);
else
System
.
out
.
println
(
"The expression is NOT balanced."
);
}
/* main */
}
ex3/ArrayStack.java
ex3/ArrayStack.java
/**
* Implementation of the Stack interface using a fixed-length array.
* An exception is thrown if a push operation is attempted when the
* size of the stack is equal to the length of the array.
*/
public
class
ArrayStack
implements
Stack
{
// Default length of the array used to implement the stack.
public
static
final
int
CAPACITY
=
1000
;
// Length of the array used to implement the stack.
protected
int
capacity
;
// Array used to implement the stack.
protected
Object
S
[];
// Index of the top element of the stack in the array.
protected
int
top
=
-
1
;
/**
* ArrayStack class constructor, with no parameter.
* Default length used for the array is CAPACITY.
*/
public
ArrayStack
()
{
this
(
CAPACITY
);
}
/**
* ArrayStack class constructor.
*
@param
cap length of the array.
*/
public
ArrayStack
(
int
cap
)
{
capacity
=
cap
;
S
=
new
Object
[
capacity
];
}
public
int
size
()
{
return
(
top
+
1
);
}
/* size */
public
boolean
isEmpty
()
{
return
(
top
<
0
);
}
/* isEmpty */
public
Object
top
()
throws
EmptyStackException
{
if
(
isEmpty
()
)
throw
new
EmptyStackException
(
"Stack is empty."
);
return
S
[
top
];
}
/* top */
/**
* Be careful here, this implementation may throw an exception.
*
@exception
FullStackException if the array is full.
*/
public
void
push
(
Object
obj
)
throws
FullStackException
{
if
(
size
()
==
capacity
)
throw
new
FullStackException
(
"Stack overflow."
);
S
[
++
top
]
=
obj
;
}
/* push */
public
Object
pop
()
throws
EmptyStackException
{
if
(
isEmpty
()
)
throw
new
EmptyStackException
(
"Stack is Empty."
);
Object
elem
=
S
[
top
];
// dereference S[top] for garbage collection.
S
[
top
--
]
=
null
;
return
elem
;
}
/* pop */
}
