1. Member
Join Date
Apr 2012
Posts
7
Rep Power
0

I have two questions that I cannot figure out how to code the method for. I understand what the question is asking for and the entire process from beginning to end along with how stack and queue works. My problem is that I do not know that actual code well. I am a beginner to java, if someone could please help me with the physical code and maybe put a side note like this line of code does this or that. I would really appreciate it, it would help me learn the code itself.

Thank you!

First question, that I cannot figure out the method for is:

In the lectures we use the data structures “ArrayStack” and “ArrayQueue” to write a Java program to decide if an input string is a palindrome. We also use the data structures “LinkedStack” and “LinkedQueue” to write a Java program to decide if an input string is a palindrome. You are asked to use the data structures “ArrayStack” and “LinkedQueue” to write a Java program testing if an input string is a palindrome.

I understand how ArrayStack and LinkedQueue work, just not the code to solve this problem.

Second Question, that I cannot figure out the method for is:

Using either “ArrayStack” or “LinkedStack”, write a Java program to decide if an input string containing the character ‘\$’ exactly once is in the following set.

L = {An\$Bn: where An = AA … A (there are n copies of A), Bn = BB … B (there are n copies of B, and n ≥ 0. When n = 0, both An and Bn are empty strings}.

Acceptable answers are \$, A\$B, AA\$BB, AAA\$BBB, and so on
Unacceptable answers are A\$BB, AA\$B, a\$b, and so on

If you can possibly help me I would really appreciate it. Thank you for your time.

2. Senior Member
Join Date
Feb 2012
Posts
219
Rep Power
5

can you post the code?

3. Member
Join Date
Apr 2012
Posts
7
Rep Power
0

Originally Posted by Wnt2bsleepin
can you post the code?
That is what I dont have. I dont know how program the methods to solve this problem. All I have right is the code for the interfaces of ArrayStack, ArrayQueue, LinkedStack, and LinkedQueue, and some other basic functions that are not the ones that I need. If you would Like I can still post the that code, but I dont know if it will help. Ill go get it.

4. Member
Join Date
Apr 2012
Posts
7
Rep Power
0

Originally Posted by Wnt2bsleepin
can you post the code?
This is the backbone that I am using.

Java Code:
```import javax.swing.JOptionPane;

public class TestArrayStackArrayQueue
{
public static void main(String args[])
{
System.out.println("Creating a stack of size 3");

ArrayStack s1 = new ArrayStack(3);

System.out.println("Is empty " + s1.isEmpty());

System.out.println("Is full " + s1.isFull());

System.out.println();
System.out.println();

String cmd;

cmd = JOptionPane.showInputDialog(
"a for pop; b for top; c for push strings; d for push any instance of objects; "
+ "e for displaying in reversal order; " + " p for checking palindrome." +
" pp for cheching palindrome (ArrayQueue1); " +
" ppp for cheching palindrome (ArrayQueue2); ");

if(cmd.equals("a"))
s1.pop();

if (cmd.equals("b"))
System.out.println(s1.top());

if (cmd.equals("c"))
{
String cmd1;
cmd1 = JOptionPane.showInputDialog(
"2 for entering two stings; 3 for entering three strings");

if (cmd1.equals("2"))
{for(int i = 1; i<= 2; i++)
{String str1 = JOptionPane.showInputDialog(
"enter the string" + i + " and push it on the stack");
s1.push(str1);
}

System.out.println("Is empty " + s1.isEmpty());

System.out.println("Is full " + s1.isFull());

System.out.println("The top element is " + s1.top());

s1.pop();
System.out.print("After one pop, the top element is ");
System.out.println(s1.top());
}
if (cmd1.equals("3"))
{for(int i = 1; i<= 3; i++)
{String str2 = JOptionPane.showInputDialog(
"enter the string" + i + " and push it on the stack");
s1.push(str2);
}

System.out.println("Is empty " + s1.isEmpty());

System.out.println("Is full " + s1.isFull());

System.out.println("The top element is " + s1.top());

String item = JOptionPane.showInputDialog(
"entering a string to be pushed onto the stack");
s1.push(item);
}
}

if (cmd.equals("d"))
{

System.out.println("Create another stack of size 10");
ArrayStack s = new ArrayStack(10);

System.out.println("enter instance <10> of Integer on the stack");

Integer Int1 = new Integer(10);
s.push(Int1);

System.out.println("enter instance <20.0> of Double on the stack");

Double double1 = new Double(20.0);
s.push(double1);

System.out.println("enter instance <\$> of Character on the stack");

Character char1 = new Character('\$');
s.push(char1);

System.out.println("enter instance <Yao, 226> of NBA Star on the stack");

Star star1 = new Star ("Yao", 226);
s.push(star1);

System.out.println("enter instance of Circle on the stack");

Circle cir1 = new Circle(10.0, 4.0, 7.0);
s.push(cir1);

System.out.println("top and pop the elements on the stack");

System.out.println("The first one is a circle");
Circle c1 = (Circle)(s.top());

System.out.println("X coordinate " + c1.centerX);
System.out.println("Y coordinate " + c1.centerY);

System.out.println("Area " + c1.findArea());
s.pop();

System.out.println("The second one is a NBA star");
Star st1 = (Star)(s.top());

System.out.println("Name " + st1.Name);
System.out.println("Height " + st1.height);
s.pop();

System.out.println("The third one is a character");
Character ch1 = (Character)(s.top());
System.out.println("The character is " + ch1.charValue());
s.pop();

System.out.println("The 4th one is a double number");
Double d1 = (Double)(s.top());
System.out.println("The double number is " + d1.doubleValue());
s.pop();

System.out.println("The 5th one is an integer number");
Integer i1 = (Integer)(s.top());
System.out.println("The integer number is " + i1.intValue());
s.pop();

}

if (cmd.equals("e"))
{
String str10 = JOptionPane.showInputDialog(
"enter a string and I will use the stack to display it in "
+ "reversal order");

ArrayStack s10 = new ArrayStack(200);
for (int k = 0; k < str10.length(); k++)
s10.push(new Character (str10.charAt(k)));

while(!s10.isEmpty())
{
Character ch10 = (Character)(s10.top());
System.out.println(ch10.charValue());
s10.pop();

}
}

if (cmd.equals("p"))
{
String str20 = JOptionPane.showInputDialog(
"enter a string and I will use the stack to check if it "
+ "is a palindrome");

ArrayStack s20 = new ArrayStack(200);

for (int k = 0; k < str20.length(); k++)
s20.push(new Character (str20.charAt(k)));

boolean bb = true;

for (int u = 0; u < str20.length(); u++)
{

Character ch20 = (Character)(s20.top());
s20.pop();

if (ch20.charValue() != str20.charAt(u))
{
bb = false;
break;
}

}

System.out.println(str20 + " is a palindrome: " + bb);
}

if (cmd.equals("pp"))
{
String str20 = JOptionPane.showInputDialog(
"enter a string and I will use the stack and queue1 to check if it "
+ "is a palindrome");

ArrayStack s20 = new ArrayStack(200);
ArrayQueue1 q20 = new ArrayQueue1(200);

for (int k = 0; k < str20.length(); k++)
{ s20.push(new Character (str20.charAt(k)));
q20.enqueue(new Character (str20.charAt(k)));
}

boolean bb = true;

for (int u = 0; u < str20.length(); u++)
{

Character ch20 = (Character)(s20.top());
s20.pop();
Character qq20 = (Character)(q20.dequeue());

if (ch20.charValue() != qq20.charValue())
{
bb = false;
break;
}

}

System.out.println(str20 + " is a palindrome: " + bb);
}

if (cmd.equals("ppp"))
{
String str20 = JOptionPane.showInputDialog(
"enter a string and I will use the stack and queue2 to check if it "
+ "is a palindrome");

ArrayStack s20 = new ArrayStack(200);
ArrayQueue2 q20 = new ArrayQueue2(200);

for (int k = 0; k < str20.length(); k++)
{ s20.push(new Character (str20.charAt(k)));
q20.enqueue(new Character (str20.charAt(k)));
}

boolean bb = true;

for (int u = 0; u < str20.length(); u++)
{

Character ch20 = (Character)(s20.top());
s20.pop();
Character qq20 = (Character)(q20.dequeue());

if (ch20.charValue() != qq20.charValue())
{
bb = false;
break;
}

}

System.out.println(str20 + " is a palindrome: " + bb);
}

}

}

class Star

{
String Name;
int height;

Star (String name, int h)
{
Name = new String(name);
height = h;
}
}

class Circle {
double centerX;
double centerY;

Circle(double r, double x, double y)
{
centerX = x;
centerY = y;
}

/** Return the area of this circle */
double findArea() {
}
}

interface StackInterface

{
public void push(Object item) throws StackOverflowException;
// Effect:         Adds item to the top of this stack.
// Postcondition:  If (this stack is full)
//                    an unchecked exception that communicates
//                    'push on stack full' is thrown
//                 else
//                    item is at the top of this stack.

public void pop() throws StackUnderflowException;
// Effect:         Removes top item from this stack
// Postconditions: If (this stack is empty)
//                   an unchecked exception that communicates
//                   'pop on stack empty' is thrown
//                 else
//                   top element has been removed from this stack.

public Object top() throws StackUnderflowException;
// Effect:         Returns a reference to the element on top of this stack
// Postconditions: If (this stack is empty)
//                    an unchecked exception that communicates
//                   'top on stack empty' is thrown
//                 else
//                   return value = (top element of this stack).

public boolean isEmpty();
// Effect:         Determines whether this stack is empty.
// Postcondition:  Return value = (this stack is empty)

public boolean isFull();
// Effect:         Determines whether this stack is full.
// Postcondition:  Return value = (stack is full)
}

//public
class StackOverflowException extends RuntimeException
{
public StackOverflowException()
{
}

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

//public
class StackUnderflowException extends RuntimeException
{
public StackUnderflowException()
{
}

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

class ArrayStack implements StackInterface
{
private Object[] stack;           // Array that holds stack elements
private int topIndex = -1;        // index of top element in stack

// Constructors
public ArrayStack()
{
stack = new Object[100];
}

public ArrayStack(int maxSize)
{
stack = new Object[maxSize];
}

public void push(Object item)
// Adds an element to the top of this stack
{
if (!isFull())
{
topIndex++;
stack[topIndex] = item;
}
else
throw new StackOverflowException("Push attempted on a full stack.");
}

public void pop()
// Removes an element from the top of this stack
{
if (!isEmpty())
{
stack[topIndex] = null;
topIndex--;
}
else
throw new StackUnderflowException("Pop attempted on an empty stack.");
}

public Object top()
// Returns the element on top of this stack
{
Object topOfStack = null;
if (!isEmpty())
topOfStack = stack[topIndex];
else
throw new StackUnderflowException("Top attempted on an empty stack.");
}

public boolean isEmpty()
// Checks if this stack is empty
{
if (topIndex == -1)
return true;
else
return false;
}

public boolean isFull()
// Checks if this stack is full
{
if (topIndex == (stack.length - 1))
return true;
else
return false;
}
}

interface QueueInterface

{
public void enqueue(Object item);
// Effect:         Adds item to the rear of this queue.
// Precondition:   This queue is not full.
// Postcondition:  item is at the rear of this queue.

public Object dequeue();
// Effect:         Removes front element from this queue and returns it.
// Precondition:   This queue is not empty.
// Postconditions: Front element has been removed from this queue.
//                 Return value = (the removed element)

public boolean isEmpty();
// Effect:         Determines whether this queue is empty.
// Postcondition:  Return value = (this queue is empty)

public boolean isFull();
// Effect:         Determines whether this queue is full.
// Postcondition:  Return value = (queue is full)
}

class ArrayQueue1 implements QueueInterface
{
private Object[] queue;           // Array that holds queue elements
private int capacity;             // size of the array (capacity of the queue)
private int numItems = 0;         // number of items on the queue
// private int front = -1;           // index of front of queue
// private int rear = 0;             // index of rear of queue

// Constructors
public ArrayQueue1()
{
queue = new Object[100];
capacity = 100;
}

public ArrayQueue1(int maxSize)
{
queue = new Object[maxSize];
capacity = maxSize;
}

public void enqueue(Object item)
// Adds an element to the front of this queue
{

if(!isFull())
{ queue[numItems] = item;
numItems = numItems + 1;
}
}

public Object dequeue()
// Removes an element from the rear of this queue
{
Object toReturn = null;
if(!isEmpty())
{
toReturn = queue[0];
for(int i = 0; i <= numItems - 2; i++)
queue[i] = queue[i + 1];

queue[numItems - 1] = null;

numItems = numItems - 1;

}
}

public boolean isEmpty()
// Checks if this queue is empty
{
return (numItems == 0);
}

public boolean isFull()
// Checks if this queue is full
{
return (numItems == capacity);
}
}

//public
class ArrayQueue2 implements QueueInterface
{
private Object[] queue;           // Array that holds queue elements
private int capacity;             // size of the array (capacity of the queue)
private int numItems = 0;         // number of items on the queue
private int front = -1;           // index of front of queue
private int rear = 0;             // index of rear of queue

// Constructors
public ArrayQueue2()
{
queue = new Object[100];
capacity = 100;
}

public ArrayQueue2(int maxSize)
{
queue = new Object[maxSize];
capacity = maxSize;
}

public void enqueue(Object item)
// Adds an element to the rear of this queue
{
if (!isFull())
{
if (numItems == 0)
{
front = front + 1;
queue[rear] = item;
numItems = numItems + 1;
}
else
{
if (rear == (capacity - 1))
{
rear = 0;
queue[rear] = item;
numItems = numItems + 1;
}
else
{
rear = rear + 1;
queue[rear] = item;
numItems = numItems + 1;
}
}
}
}

public Object dequeue()
// Removes an element from the front of this queue
{

if (isEmpty())
return null;

else

{

if (numItems == 1)
{
Object toReturn = queue[front];
queue[front] = null;

front = -1;
rear = 0;
numItems = 0;

}
else
{
if (front == (capacity - 1))
{
Object toReturn = queue[front];
queue[front] = null;

front = 0;
numItems = numItems - 1;

}

else
{
Object toReturn = queue[front];
queue[front] = null;

front = front + 1;
numItems = numItems - 1;

}

}

}
}

public boolean isEmpty()
// Checks if this queue is empty
{
return (numItems == 0);
}

public boolean isFull()
// Checks if this queue is full
{
return (numItems == capacity);
}
}```
Last edited by DigitalBullets; 04-29-2012 at 04:56 AM.

5. Senior Member
Join Date
Feb 2012
Posts
219
Rep Power
5

Please put those in [code][/ code] tags

6. Member
Join Date
Apr 2012
Posts
7
Rep Power
0

Originally Posted by Wnt2bsleepin
Please put those in [code][/ code] tags
sorry I've never used a forum like this before, I edited the post and typed [code] at the beginning and [/ code] at the end but I dont see what it did other than put it there in the post? Im sure I did something wrong

7. Senior Member
Join Date
Feb 2012
Posts
219
Rep Power
5

Originally Posted by DigitalBullets
sorry I've never used a forum like this before, I edited the post and typed [code] at the beginning and [/ code] at the end but I dont see what it did other than put it there in the post? Im sure I did something wrong
You need to remove the space on between the / and Code on the second bracket. I left it in there so it would show.

9. Member
Join Date
Apr 2012
Posts
7
Rep Power
0

Originally Posted by DarrylBurke
Sorry about the title, and missing the [CODE/CODE] I will make sure not to make that mistake again. Is there a way to delete the thread and re-post it with those fixes? I think it would probably help anything looking at the post answer my questions. Thanks!

10. Senior Member
Join Date
Feb 2012
Posts
219
Rep Power
5

Why is there a Circle object in there?

[code]
class Circle
[/object]

may have some relevance, but it's not related to your question.

Just a question. Is this an assignment for a class. You're dealing with data structures, implemented as an Array and as a Linked List. I have some literature I can post here to show you how to do it.

11. Member
Join Date
Apr 2012
Posts
7
Rep Power
0

Originally Posted by Wnt2bsleepin
Why is there a Circle object in there?

[code]
class Circle
[/object]

may have some relevance, but it's not related to your question.

Just a question. Is this an assignment for a class. You're dealing with data structures, implemented as an Array and as a Linked List. I have some literature I can post here to show you how to do it.
Yes this was an example used in class. The circle class was just a something we went over in class. For the question I only need to write a method, so all that code that was posted isnt really needed as far as I know but it was asked for.

12. Senior Member
Join Date
Feb 2012
Posts
219
Rep Power
5

Well, he gave you the code to put stuff into a Queue and a Stack. Do you know what those are, as well as their implementations as an array or linked list? For future reference, I find it easier to post the individual .class files in their own [code] brackets. Makes it easier to discern between them.