6 Replies - 702 Views - Last Post: 04 June 2014 - 07:25 PM Rate Topic: -----

#1 mattmattmatt  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 17-April 14

Assignment HELP! (Using Stacks)

Posted 03 June 2014 - 08:11 PM

I have a programming assignment I'm stuck on. The assignment is to create a SmartString class that implements a SmartStringInterface class (created by professor) and implements a few methods. We are basically taking a string and then taking various substrings and inserting, deleting them and undoing changes as well. Here are the methods in the interface to use along with the parameters.

 public interface SmartStringInterface { 
 public void insert(int pos, String sstring); 
 public void delete(int pos, int count); 
 public void undo(); 
 public String toString(); 



The Undo is supposed to be able to be called multiple times (to be tested using a driver program that we must create) but the part that's got me is that the changes are only supposed to be stored. Currently, I am storing the "new" string after each change onto a stack, so that undo can just pop off the stack and it will revert to the previous string. Professor said that was wrong, so I don't know how to do it. Here is what I have so far (some of the code we have is using default StackADT stuff from our book, so if you need that I can post as well. You can see in the undo method where I currently save the string. We can use multiple stacks if needed, but the less the better. Must use at least 1. The exception code is already coded for us in another file also. I am only having to code these methods and the driver to test.

    import java.util.Arrays;


    public class ArrayStack<T> implements StackADT<T>
    {
    private final static int DEFAULT_CAPACITY = 100;

    private int top;  
    private T[] stack;
      
    public ArrayStack()
    {
        this(DEFAULT_CAPACITY);
    }
    
    public ArrayStack(int initialCapacity)
    {
        top = 0;
        stack = (T[])(new Object[initialCapacity]);
    }
    
    public void push(T element)
    {
        if (size() == stack.length) 
            expandCapacity();

        stack[top] = element;
        top++;
    }
    
    private void expandCapacity()
    {
        stack = Arrays.copyOf(stack, stack.length * 2);   
    }
    
    public T pop() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("stack");

        top--;
        T result = stack[top];
        stack[top] = null; 

        return result;
    }
   
    public T peek() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("stack");

        return stack[top-1];
    }

    public boolean isEmpty()
    {
        if (top == 0)
        	return true;
        else
        	return false;
    }
     
    public int size()
    {
        int size = top;
        return size;
    }

    public String toString()
    {
       String s = "";
    	for (int i = 0; i < stack.length; i++)
       {
    	   s += stack[i];
       }
    	
    	return s;
    }
    }



Is This A Good Question/Topic? 0
  • +

Replies To: Assignment HELP! (Using Stacks)

#2 x68zeppelin80x  Icon User is offline

  • D.I.C Addict

Reputation: 130
  • View blog
  • Posts: 576
  • Joined: 07-March 09

Re: Assignment HELP! (Using Stacks)

Posted 04 June 2014 - 03:23 AM

View Postmattmattmatt, on 03 June 2014 - 11:11 PM, said:

Currently, I am storing the "new" string after each change onto a stack, so that undo can just pop off the stack and it will revert to the previous string.

Do you want to uses Strings? They are immutable. Probably better to use a char[] or List<Character>.

View Postmattmattmatt, on 03 June 2014 - 11:11 PM, said:

You can see in the undo method where I currently save the string.

What does undo() look like?

This post has been edited by x68zeppelin80x: 04 June 2014 - 03:23 AM

Was This Post Helpful? 0
  • +
  • -

#3 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5899
  • View blog
  • Posts: 12,803
  • Joined: 16-October 07

Re: Assignment HELP! (Using Stacks)

Posted 04 June 2014 - 04:46 AM

This looks interesting. The stack thing is odd, but doable.

I'd start with something like:
class SmartString implements SmartStringInterface { 
    private interface Operation {
        String doOp(String state);
    }
    private StackADT<Operation> ops;
    public SmartString() { ops = new ArrayStack<>(); }

    public void insert(int pos, String sstring) { ops.push(getInsertOp(pos, sstring)); }
    public void delete(int pos, int count) { ops.push(getDeleteOp(pos, count)); }
    public void undo() { if (!ops.isEmpty()) { ops.pop(); } }
    public String toString() { return rebuildString(); }

    private String rebuildString() { /* your code here */ }
    private Operation getInsertOp(final int pos, final String s) { /* your code here */ }
    private Operation getDeleteOp(final int pos, final int count) { /* your code here */ }
}



Basically, every call toString, you apply all the current changes. This means you have to unwind the stack to get to the first operation. Recursion would be helpful for this. Don't forget to rewind the stack. Yes, a stack is a crappy choice for this. Your instructor is torturing you and clearly has some very specific process in mind.

Hope this helps.
Was This Post Helpful? 0
  • +
  • -

#4 mattmattmatt  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 17-April 14

Re: Assignment HELP! (Using Stacks)

Posted 04 June 2014 - 04:52 AM

My undo method just has changes.pop() everytime its called but that was wrong.

The operation word in your methods, not sure what that means..havent talked about that yet.
Was This Post Helpful? 0
  • +
  • -

#5 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5899
  • View blog
  • Posts: 12,803
  • Joined: 16-October 07

Re: Assignment HELP! (Using Stacks)

Posted 04 June 2014 - 06:26 AM

View Postmattmattmatt, on 04 June 2014 - 07:52 AM, said:

The operation word in your methods, not sure what that means


It's an interface. I just made it up. ;) Since you're writing your own implementation of interfaces, this shouldn't be that new.

The idea is that you implement the interface to preform actions, like your two actions that change your string.

Here's a quick example:
class MathStuff {
    // a simple interface defined
    // this will take a value and return a value
    private interface Operation {
        int applyFunc(int state);
    }
   
    // a class that implements the interface
    private class Add implements Operation {
        private final int value; 
        public Add(int value) { this.value = value; }
        public int applyFunc(int n) { return n + value; }
    }

    // helper function, shows operations
    private int doAndShow(String name, int n, Operation op) {
        int result = op.applyFunc(n);
        System.out.println(name + " " + n + " -> " + result);
        return result;
    }

    public void test() {
        System.out.println("Math Test");
        int n = 2;
        n = doAndShow("add 3", n, new Add(3)); // pass instance of Add
        n = doAndShow("sub 1", n, new Add(-1)); // pass instance of Add
        // here, we create an anonymous implementation of Operation interface
        n = doAndShow("mult 3", n, new Operation() {
            public int applyFunc(int x) { return x * 3; }
        });
    }

}



Results:
add 3 2 -> 5
sub 1 5 -> 4
mult 3 4 -> 12



This is just one way to deal with the problem. Alternately, you could simply push a value on the stack that described the operation you want to do. You'll still want a class to help you out.

class MyStringOp {
    public int pos;
    public boolean isInsert;
    public String sstring;
    public int count;
}



Using that you could reasonably describe your operations and apply them accordingly.
Was This Post Helpful? 1
  • +
  • -

#6 mattmattmatt  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 17-April 14

Re: Assignment HELP! (Using Stacks)

Posted 04 June 2014 - 06:54 AM

Yeah that is where I am stuck though. I am completely lost on how to code the changes. Like I understand what it is supposed to do, just have zero idea on how to code it.
Was This Post Helpful? 0
  • +
  • -

#7 mattmattmatt  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 17-April 14

Re: Assignment HELP! (Using Stacks)

Posted 04 June 2014 - 07:25 PM

Here is my insert and delete methods:

public void insert(int pos, String sstring)
	{
		string.insert(pos, sstring);
		//changes.push(string.toString());
	}

	public void delete(int pos, int count) 
	{
		string.delete(pos, count);
		//changes.push(string.toString());
	}



Ignore the changes part since that is how I was previously storing the changes with the resulting string into the stack, but that's the part the professor said was wrong, so that's where I'm completely list is the undo and storing the actual changes. If I know how to store the changes, I think the undo will be a bit easier. Looking at your example confused me, as I don't understand part of it nor how I can apply that to mine
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1