Below program has own implementation of Stack data structure.
import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;
public class StackApplication {
private
static final char L_PAREN = '(';
private
static final char R_PAREN = ')';
private
static final char L_BRACE = '{';
private
static final char R_BRACE = '}';
private
static final char L_BRACKET = '[';
private
static final char R_BRACKET = ']';
public
static void parenthesis(String s) {
boolean
checkParen = true;
Stack<Character>
stack = new Stack<Character>();
try
{
for
(int i = 0; i < s.length(); i++) {
if (s.charAt(i) == L_PAREN)
stack.push(L_PAREN);
else
if (s.charAt(i) == L_BRACE)
stack.push(L_BRACE);
else
if (s.charAt(i) == L_BRACKET)
stack.push(L_BRACKET);
else
if (s.charAt(i) == R_PAREN) {
if
(stack.isEmpty())
checkParen = false;
if
(stack.pop() != L_PAREN)
checkParen
= false;
}
else if (s.charAt(i) == R_BRACE) {
if
(stack.isEmpty())
checkParen
= false;
if
(stack.pop() != L_BRACE)
checkParen
= false;
}
else if (s.charAt(i) == R_BRACKET) {
if
(stack.isEmpty())
checkParen
= false;
if
(stack.pop() != L_BRACKET)
checkParen
= false;
}
}
}
catch (Exception ex) {
}
if
(checkParen) {
System.out.println(s
+ " has balanced parenthesis");
} else
{
System.out.println(s
+ " has not balanced parenthesis");
}
//
return stack.isEmpty();
}
static
void palindrome(String str) {
System.out.print(str);
String
test = str;
String
newstr = "";
//
char[] letters;
char
letters2;
// Extract
the letters.37.
char[]
letters = str.toCharArray();
//
iterate through all the char in the sentences40.
int
len = letters.length;
for
(int i = 0; i < len; i++) {
//
checks if current char is a letter and adds each char to
//
newstr43.
if
(Character.isLetter(letters[i])) {
letters2
= letters[i];
newstr
+= letters2;
}
}
// Extract the letters.50.
letters
= newstr.toCharArray();
//
System.out.print(letters);
//
Create an empty stack.53.
Stack<Character>
stack = new Stack<Character>();
//
The letters must "balance" up to the middle.56.
int
mid = letters.length / 2;
//
Push the first half.59.
for
(int i = 0; i < mid; i++) {
stack.push(letters[i]);
}
if
(letters.length % 2 > 0) {
//
Odd number => swallow middle letter.65.
mid
= mid + 1;
}
boolean
palindrom = true;
for
(int i = mid; i < letters.length; i++) {
char
ch = stack.pop();
if
(ch != letters[i]) {
//
Mismatch => not a palindrome.73.
//
return "is not a palindrome";
palindrom = false;
}
}
if
(!(palindrom))
System.out.println("
is not a palindrome");
else
System.out.println("
is a palindrome");
}
public
static void main(String[] args) throws IOException {
EquationEvaluator
eq = new EquationEvaluator();
//
Prefix Notation
System.out
.println("\n--------Postfix
Notation using Stack------------");
Scanner
in = new Scanner(new FileReader("C:\\FileTest\\postfix.txt"));
while
(in.hasNextLine()) {
postfix(in.nextLine());
//
eq.convertToPostfix(in.nextLine());
}
in.close();
//
Palindrome
System.out.println("\n--------Palindromes
using Stack------------");
FileReader
fob = new FileReader("C:\\FileTest\\palindrome.txt");
in
= new Scanner(fob);
while
(in.hasNextLine()) {
String
line = in.nextLine();
palindrome(line);
}
in.close();
fob
= new FileReader("C:\\FileTest\\paren.txt");
in
= new Scanner(fob);
//
Parenthesis
System.out
.println("\n------Balanced
Parenthesis check using Stack-----");
while
(in.hasNextLine()) {
String
line = in.nextLine();
parenthesis(line);
}
in.close();
fob
= new FileReader("C:\\FileTest\\reverse.txt");
in
= new Scanner(fob);
//
Parenthesis
System.out
.println("\n--------Reverse
a string using Stack------------");
while
(in.hasNextLine()) {
String
line = in.nextLine();
Reverse(line);
}
in.close();
}
public
static void Reverse(String line) {
//
Scanner scanner = new Scanner(System.in);
String
str = line;
Stack<String>
stack = new Stack<String>();
//
System.out.println("Enter a string to be reversed: ");
//
str = scanner.nextLine();
if
(str == null || str.equals("")) {
System.out
.println("It
seems you aren't ready as yet to enter the string, ok buhbye !!");
System.exit(0);
}
for
(int i = 0; i < str.length(); i++) {
//
Here we push all the characters in the string one by one into the
//
Stack29.
stack.push(str.substring(i,
i + 1));
}
String
strrev = "";
while
(!stack.isEmpty()) {
//
Here we pop all the elements from the Stack one by one which is
//
essentially reversing.36.
strrev
+= stack.pop();
}
System.out.println("Original
string \"" + str);
System.out.println("Reverse
string \"" + strrev);
}
public
static StringBuilder postfix(String infix_str) {
Stack<Character>
infix = null;
StringBuilder
postfix;
Stack<String>
postfix_str = null;
infix
= new Stack<Character>();
postfix
= new StringBuilder();
postfix_str
= new Stack<String>();
int
i = 0;
boolean
flag = true;
int
cheakOperatorExists = 0;
while
(!infix_str.isEmpty()) {
if
(infix_str.charAt(i) == '(') {
infix.push(infix_str.charAt(i));
infix_str
= infix_str.substring(i + 1, infix_str.length());
}
else {
if
(Character.getNumericValue(infix_str.charAt(i)) >= 0
&&
Character.getNumericValue(infix_str.charAt(i)) <= 9) {
postfix.append(infix_str.charAt(i));
postfix_str.push(String.valueOf(infix_str.charAt(i)));//
added
infix_str
= infix_str.substring(i + 1, infix_str.length());
}
else // operator
{
cheakOperatorExists
= 1;
if
(!(infix_str.charAt(i) == ')')) {
int
checkOperator = checkOperator(infix_str.charAt(i));
if
(checkOperator == 0) {
//
postfix= new StringBuilder();
//
return postfix;
}
if
(infix.isEmpty()
||
infix.peek() == '('
||
!(hasPrecedence(infix_str.charAt(i), infix
.peek())))
{
infix.push(infix_str.charAt(i));
infix_str
= infix_str.substring(i + 1, infix_str
.length());
}
else {
postfix_str.push(String.valueOf(infix.peek()));//
added
postfix.append(infix.pop());
}
}
else {
try
{
while
(infix.peek() != '(') {
postfix_str.push(String.valueOf(infix.peek()));//
added
postfix.append(infix.pop());
}
infix.pop();
infix_str
= infix_str.substring(i + 1, infix_str
.length());
}
catch (Exception EmptyStackException) {
System.out.println("Unbalanced
Parathesis");
break;
}
}
}
}
}
while
(!infix.isEmpty()) {
postfix_str.push(String.valueOf(infix.peek()));//
added
postfix.append(infix.pop());
}
System.out.println("Your
expression in postfix notation is:" + postfix);
return
postfix;
}
static
boolean hasPrecedence(char arg1, char arg2)// when to pop (true -
//
pop)
{
String
firstPreced = "^";
String
secondPreced = "*/";
String
thirdPreced = "+-";
//
EQUALS TO
if
((thirdPreced.charAt(0) == arg1 || thirdPreced.charAt(1) == arg1)
&&
(thirdPreced.charAt(0) == arg2 || thirdPreced.charAt(1) == arg2)) {
return
true;
}
if
((secondPreced.charAt(0) == arg1 || secondPreced.charAt(1) == arg1)
&&
(secondPreced.charAt(0) == arg2 || secondPreced.charAt(1) == arg2)) {
return
true;
}
if
(firstPreced.charAt(0) == arg1 && firstPreced.charAt(0) == arg2) {
return
true;
}
if
((thirdPreced.charAt(0) == arg1 || thirdPreced.charAt(1) == arg1)
&&
(secondPreced.charAt(0) == arg2 || secondPreced.charAt(1) == arg2)) {
return
true;
}
if
((thirdPreced.charAt(0) == arg1 || thirdPreced.charAt(1) == arg1)
&&
(firstPreced.charAt(0) == arg2)) {
return
true;
}
return
false;
}
public
static int checkOperator(char operator) {
if
(operator == '^')
return
3;
if
(operator == '/' || operator == '*')
return
2;
if
(operator == '+' || operator == '-')
return
1;
return
0;
}
}
Stack.java
public class Stack<E>
{
private
LinkedList<E> list; // LinkedList declaration
/*
* This constructor
initiates a generic "stack" LinkedList.
*/
public Stack() {
list = new
LinkedList<E>("stack");
}
/*
* This constructor
initiates a specific LinkedList "name."
*
* @param name passed
String which the Stack will be referenced
*/
public Stack(String
name) {
list = new
LinkedList<E>(name);
}
/*
* This method inserts an
item on the front of the Stack.
*/
public void push(E item) {
list.insertAtFront(item);
}
/*
* This method returns
the length of the Stack.
*/
public int lengthIs() {
return list.lengthIs();
}
/*
* This method returns
the item at the front of the Stack.
*/
public E peek() {
E
item;
item
= list.removeFromFront();
list.insertAtFront(item);
return item;
//
LinkedList<E> item = list.insertAtFront(list.removeFromFront ());
}
/*
* This method prints the
contents of the Stack.
*/
public void print() {
list.print();
}
/*
* This method returns a
Boolean relaying whether the Stack is empty or
* full.
*/
public boolean isEmpty() {
return list.isEmpty();
}
public E pop() {
E
obj;
int len = list.lengthIs();
obj
= peek();
list.removeFromFront();
// list.remove(len-1);
return obj;
}
}
LinkedList.java
//importing given exception
package
public class
LinkedList<T>
{
private
ListNode<T> firstNode; // first ListNode in list
private
ListNode<T> lastNode; // last ListNode in list
int numElements; // total
number of elements stored in list
String name; // string representing
LinkedList printed
/*
* This constructor sets name to
"list," firstNode and lastNode to
* null, and numElements to zero.
*/
public LinkedList()
{
name = "list";
firstNode = null;
lastNode = null;
numElements = 0;
}
/*
* This constructor sets name to a passed
String, firstNode and
* lastNode to null, and numElements to
zero.
*
* @param listName passed String to which
name is set
*/
public LinkedList( String
listName )
{
name = listName;
firstNode = null;
lastNode = null;
numElements = 0;
}
/*
* This method inserts an item on the front
of the list.
*
* @param item passed T to be added to the
front of list
*/
public void insertAtFront(
T item )
{
// selection
structure checks to see if firstNode and lastNode
// are equal
if( isEmpty() )
{
firstNode = lastNode = new
ListNode<T>( item );
numElements++;
}
else
{
firstNode = new
ListNode<T>( item, firstNode );
numElements++;
}
}
/*
* This method inserts an item on the back
of the list.
*/
public void insertAtBack( T
item )
{
// selection
structure checks to see if firstNode and lastNode
// are equal
if( isEmpty() )
{
firstNode = lastNode = new
ListNode<T>( item );
numElements++; // adding
counter to numElements
}
else
{
ListNode<T>
temp = new ListNode<T>(item);
lastNode.setNext(temp);
lastNode = temp;
numElements++; // adding
counter to numElements
}
}
/*
* This method removes the first item in
the list and returns
* the item unless the list is empty, in
which case it throws
* an exception.
*/
public T
removeFromFront() throws EmptyListException
{
// if
statement throws an exception if list is empty
if( isEmpty() )
{
throw new
EmptyListException( name );
}
T removedItem = firstNode.getData(); // retrieve
data being removed
// selection structure updates
firstNode and lastNode references
if( firstNode == lastNode )
{
firstNode = lastNode = null;
numElements--; // subtracting
a counter from numElements
}
else
{
firstNode = firstNode.getNext();
numElements--; // subtracting
a counter from numElements
}
return removedItem; // returning
item to be removed
}
/*
* This method removes the last item in the
list and returns it unless
* this list is empty, in which case it
throws an exception.
*/
public T
removeFromBack() throws EmptyListException
{
// if
statement throws an exception if list is empty
if( isEmpty() )
{
throw new
EmptyListException( name );
}
T removedItem = lastNode.getData(); // retrieve
data being removed
// selection structure updates
firstNode and lastNode references
if( firstNode == lastNode )
{
firstNode = lastNode = null;
numElements--; // subtracting
a counter from numElements
}
else
{
ListNode<T> current = firstNode;
// looping structure searches for node
that's not last
while( current.getNext()
!= lastNode )
{
current = current.getNext();
}
lastNode = current;
current.setNext(null);
numElements--; // subtracting
a counter from numElements
}
return removedItem; // returning
item to be removed
}
/*
* This method removes an element from the
list at a passed index unless
* the list is empty or the index is out of
range, in which cases
* it throws an exception
*
* @param index passed index value to be
removed
*/
public void remove( int index ) throws
EmptyListException, IndexOutOfBoundsException
{
// if
statement throws an exception if list is empty
if( isEmpty() )
{
throw new
EmptyListException( name );
}
// if
statement throws an exception if index is out of bounds
if ( index > ( numElements - 1 ) || index
< 0 )
{
throw new
IndexOutOfBoundsException();
}
// removes
item at front of the list if item to be removed
// is at the
front of the list
if( index == 0 )
{
removeFromFront();
}
// removes
item at the back of the list if index is
// for last
item in list
else if( index == ( numElements - 1 ) )
{
removeFromBack();
}
// looping
structure to determine which item to remove
// when index
is not for first or last item in list
else{
int i=0;
ListNode<T>
current = firstNode;
// search for
item in list up to lastNode
while( current != lastNode )
{
if( i != ( index -
1 ) )
{
current
= current.getNext();
i++;
}
else{
current.setNext(
current.getNext().getNext() );
current
= current.getNext();
numElements--; // subtracting
a counter from numElements
i++;
}
}
}
}
/*
* This method returns the element at the
given index unless the list is
* empty or the index is out of range, in
which case it throws an exception.
*
* @param index passed index value to be
located
*/
public T get( int index ) throws
EmptyListException, IndexOutOfBoundsException
{
// if
statement throws an exception if list is empty
if( isEmpty() )
{
throw new
EmptyListException( name );
}
// if
statement throws an exception if index is out of bounds
if( index > ( numElements - 1 ) || index
< 0 )
{
throw new
IndexOutOfBoundsException();
}
ListNode<T>
current = firstNode;
// loop
searches for index
for(int i=0; i<index
; i++ )
{
current
= current.getNext();
}
return
current.getData(); // returns found element
}
/*
* This method finds items in the list and
removes them unless
* the list is empty, in which case it
throws an exception.
*
* @param item passed item to be found and
removed
*/
public Boolean
findAndRemove( T item ) throws EmptyListException
{
// if
statement throws an exception if list is empty
if( isEmpty() )
{
throw new
EmptyListException( name );
}
// finds passed item's index
int index = findItem(item);
// if/else structure removes item from
list if it is not
// out of range and returns Boolean
with success response
if( index != -1 )
{
remove(index);
return true;
}
else
{
return false;
}
}
/*
* This method searches for an item in the
list and returns
* that item. If the item is not found it
returns -1.
*
* @param item passed item to be found
*/
public int findItem( T
item )
{
// if
statement throws an exception if list is empty
if( isEmpty() )
{
throw new
EmptyListException( name );
}
int i=0;
ListNode<T> current = firstNode;
// compares passed item to item found
next in list;
// if item is the same it returns
item's index
while(
current.getNext() != lastNode )
{
if(
current.getData() == item )
{
return i;
}
current = current.getNext();
i++;
}
return -1; // returns -1
if item is not found in list
}
/*
* This method returns the number of
elements in the list.
*/
public int lengthIs()
{
return numElements;
}
/*
* This method removes all elements from
the list.
*/
public void clear()
{
// setting
firstNode and lastNode to null
firstNode = lastNode = null;
numElements = 0; // resetting
numElements
}
/*
* This method prints Empty NAMEOFLIST if
list is empty, otherwise
* it prints the name of the list and the
list's contents
*/
public void print()
{
// if
statement prints that the list is empty if it is empty
if( isEmpty() )
{
// System.out.printf(
"Empty %s\n", name );
return;
}
ListNode<T> current = firstNode;
// Printing the name of the list if it
is not empty
//System.out.print( "The list
'"+ name +"' contains:" );
// for loop prints the elements in the
list
for( int i=0; i < numElements; i++ )
{
//System.out.printf(
" " + current.getData() );
current
= current.getNext();
}
// System.out.printf(
"\n\n" ); //spaces to make formatting correct
}
/*
* This method checks to see if the list is
empty, returning
* true if it is empty and false if it not.
*/
public Boolean
isEmpty()
{
return firstNode == null;
}
}
ListNode.java
package Jared; // package
declaration
// each class represents one
node in a list
public class
ListNode<T>
{
private T data; // data for
this node
private
ListNode<T> nextNode; // reference to the next node
/*
* This constructor sets
data to a passed value and nextNode
* to null.
*
* @param object T
instance passed to which data is set
*/
public ListNode( T
object )
{
this( object, null );
}
/*
* This constructor sets
data and nextNode to passed values.
*
* @param object T
instance passed to which data is set
* @param node passed
ListNode<T> to which nextNode is set
*/
public ListNode( T
object, ListNode<T> node )
{
data = object;
nextNode = node;
}
/*
* This method sets data
equal to a passed object.
*
* @param object passed T
reference to which data is set
*/
public void setData( T
object )
{
data = object;
}
/*
* This method returns
data reference in node.
*/
public T getData()
{
return data;
}
/*
* This method sets
nextNode to a passed reference.
*
* @param next passed
reference to which nextNode is set
*/
public void setNext(
ListNode<T> next )
{
nextNode = next;
}
/*
* This method returns
nextNode.
*/
public
ListNode<T> getNext()
{
return nextNode;
}
}
Output:
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.