Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 5 of 5

Thread: Having trouble getting started testing for matching delimiter sets.

  1. #1
    Member
    Join Date
    Jun 2012
    Posts
    59
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Having trouble getting started testing for matching delimiter sets.

    Right now in my class we are dealing with array stack data structures. I have successfully put together an array stack class which creates a stack that holds strings(or in my case string elements). However the assignment that we are working on makes us test to see if the string has matching delimiter sets. I'm having trouble even thinking about how to approach this in writing a method for it.

     
     2. Write a program that analyzes an expression for matching
        the delimiter set: () []  {}.  For example the expression
        { 2 + [ a - (  b * f ) ] + e }; contains matching delimiters.

    This is what I have so far.

    public class TestStack{
     
     
    	public static void main(String[] args){
     
    		ArrayStack list = new ArrayStack();
     
     
    		System.out.println("Initializing stack.");
    		list.initializeStack();
    		System.out.println("Done.");
    		System.out.println("Testing the isEmptyStack method.");
    		System.out.println(list.isEmptyStack());
    		System.out.println("Done.");
     
    		System.out.println("Adding 2 StringElements to the stack.");
    		list.push(new StringElement("{ 2 + [ a - (  b * f ) ] + e }"));
    		list.push(new StringElement("{ 3 + ( 2 - 4 ) - 6 }"));
    		System.out.println("Testing the top method.");
    		StringElement stg = (StringElement)list.top();
    		System.out.println("The element from the top of the stack returned: " + stg.message);
    		System.out.println("Done.");
    		System.out.println("Testing isFullStack method.");
    		System.out.println(list.isFullStack());
    		System.out.println("Done.");
    		System.out.println("Testing the pop method.");
    		list.pop(); //deletes the top element of the stack
    		System.out.println("Deleted the top element of the stack using the pop method.");
    		stg = (StringElement)list.top(); 	//prints out the new top element of the stack
    		System.out.println("The element from the top of the stack returned: " + stg.message);
    		System.out.println("All methods from ArrayStack class have been tested.");
    	}
    }

    public class ArrayStack{
     
    	//variable to store the max stack size
    	private int maxStackSize; 
     
     
    	//variable to point to the top of the stack
    	private int stackTop;
     
    	//array of ref variables
    	private DataElement[] list;
     
    	//default constructor
    	public ArrayStack(){
     
     
       	maxStackSize = 100;
       	stackTop = 0;                    //set stackTop to 0
        list = new DataElement[maxStackSize]; //create array
    }//end default constructor
     
    	//constructor with a parameter
    		public ArrayStack(int stackSize) 
    {
         if(stackSize <= 0)
         {
            System.out.println("The size of the array to implement "
                             + "the stack must be positive.");
            System.out.println("Creating an array of size 100.");
            maxStackSize = 100;
         }
         else
            maxStackSize = stackSize;  //set the stack size to 
                                       //the value specified by 
                                       //the parameter stackSize
         stackTop = 0;                 //set stackTop to 0
         list = new DataElement[maxStackSize]; //create the array
    }//end constructor
     
     
    	//copy constructor
    	public ArrayStack(ArrayStack otherStack)
    {
         copy(otherStack);
    }//end copy constructor
     
     
    	private void copy(ArrayStack otherStack)    // copy data only 
    {
             list = null;
     
             maxStackSize = otherStack.maxStackSize;
             stackTop = otherStack.stackTop;
     
             list = new DataElement[maxStackSize];
     
              //copy otherStack  data into this stack’s data
             for(int i = 0; i < stackTop; i++)
                 this.list[i] = otherStack.list[i].getCopy();
    }//end copy
    // a new Stack is not created
     
    	//copy data from otherStack to this stack
    public void copyStack(ArrayStack otherStack)
    {
     if(this != otherStack) //avoid self-copy
    	copy(otherStack);
    }//end copyStack  
     
     
     
    	public void initializeStack(){
    		for(int i =0; i<stackTop; i++){
    			list[i] = null;
    			stackTop = 0;
     
    		}
    	} //end initializeStack
     
    	public boolean isEmptyStack(){
    		return (stackTop==0);
    	}//end isEmptyStack
     
     
    	public boolean isFullStack(){
     
    		return (stackTop == maxStackSize);
    	}//end isFullStack
     
    	public void push(DataElement newItem) 				
    {
        if(isFullStack())
           throw new StackOverflowException();
        list[stackTop] = newItem.getCopy(); //add newItem at the
                                            //top of the stack
        stackTop++;                         //increment stackTop
    }//end push
     
     
     
     
    	public DataElement top() 
    {
         if(isEmptyStack())
            return null; 
     
         return list[stackTop - 1].getCopy();
     
    }//end top
     
     
     
    		public DataElement pop()
    {
        if(isEmptyStack())
           return null; 
     
         DataElement temp = list[stackTop - 1].getCopy();
     
         stackTop--;       //decrement stackTop
         list[stackTop] = null;
     
         return temp;
    }//end pop
     
    }

    public abstract class DataElement{
     
    	public abstract boolean equals(DataElement otherElement);
     
    	public abstract int compareTo(DataElement otherElement);
     
    	public abstract void makeCopy(DataElement otherElement);
     
    	public abstract DataElement getCopy();
    }

    public class StringElement extends DataElement{
     
    	protected String message;
     
    	public StringElement(){
    		message = "Default String";
    	}
     
    	public StringElement(String msg){
    		message = msg;
    	}
     
     
    	public boolean equals(DataElement obj){
    		if(obj == null)
    			return false;
     
    			else if (getClass() != obj.getClass())
    				return false;
     
    				StringElement temp = (StringElement)obj;
    		return (message.equalsIgnoreCase(temp.message)); 
    	}
     
    public int compareTo(DataElement obj){
    	StringElement temp = (StringElement)obj;
    	int compareResult = message.compareToIgnoreCase(temp.message);
    	int setInt = 0;
     
    	if(compareResult == 0){
    		setInt = 0;
    		}
     
    		else if(compareResult > 0){
    			//System.out.println(message + " is greater than " + temp.message + "."); for reference
    			setInt = 1;
    		}
     
    		else if(compareResult < 0){
    			//System.out.println(temp.message + " is greater than " + message + "."); for reference
    			setInt = -1;
    		}
    		return setInt;
     
    	}
     
     
    	public void makeCopy(DataElement copy){
    		StringElement temp;
    		temp = (StringElement)copy;
    		message = temp.message;
     
    }
     
    public DataElement getCopy(){
     
    	DataElement copy = new StringElement(message);
    	return copy;
    }
     
     
     
     
    }

    I've already ruled out that you can't compare the strings because you aren't comparing more than one string...I assume. Any tips would be greatly appreciated.


  2. #2
    Super Moderator jps's Avatar
    Join Date
    Jul 2012
    Posts
    2,642
    My Mood
    Daring
    Thanks
    90
    Thanked 263 Times in 232 Posts

    Default Re: Having trouble getting started testing for matching delimiter sets.

    I've already ruled out that you can't compare the strings because you aren't comparing more than one string...I assume
    I don't quite understand what you mean by that. But I suggest you check the String class for the equals method.

  3. #3
    Member
    Join Date
    Jun 2012
    Location
    Left Coast, USA
    Posts
    451
    My Mood
    Mellow
    Thanks
    1
    Thanked 97 Times in 88 Posts

    Default Re: Having trouble getting started testing for matching delimiter sets.

    Quote Originally Posted by orbin View Post
    ...test to see if the string has matching delimiter sets.
    Terminology:
    We have left delimiters: ( and [ and {
    Corresponding to each left delimiter, there is a right delimiter ) and ] and }, respectively
    So, here's a good String.

    { 3 + ( 2 - 4 ) - 6 }


    Here's a bad String (missing right delimiter at end)

    { 3 + ( 2 - 4 ) - 6


    Here's a bad String (improper nesting)

    { 3 + ( 2 - 4 } - 6 )


    The assignment didn't mention it, but I am assuming multiple nesting is also valid, so the following is a good String:

    [ 3 + ( 2 - 4 + (3 - 6) ) - 10 ]

    (If this is not acceptable, then the scheme that I am thinking about could be easily modified to flag that as invalid.)

    Anyhow...

    Here's how I would test visually:
    Write the string on a piece of paper. Use a pencil.

    Visually scan the string from left to right. For purposes of delimiter-matching, ignore everything other than left-delimiter characters and right-delimiter characters.

    When you encounter a right delimiter, look back and find the most recent left delimiter. (If there is no previous left delimiter, that's an error, and you can quit looking.)

    If you did find a left delimiter before the current (right-delimiter) character, see if the last left delimiter matches the current (right-delimiter) character. If so, then, that's a Good Thing; erase (or mark through) the substring consisting of the two delimiters and everything in between. If they don't match, that's an error, and you can quit looking.

    If you are still looking (no errors yet) keep scanning and when you see another right delimiter, look back at the last left delimiter (ignoring all marked-through substrings). Repeat the process of checking for a matching left delimiter until you get to the end of the String.

    When you get to the end of the string, if there are any left delimiters that haven't been marked through, that's an error, otherwise it's OK

    To do this in a program, you could store left delimiters on a stack as you scan the string. When you get to a right delimiter, check to see whether the top of the stack is the matching left delimiter, and take appropriate action:
    If they match, remove the character from the top of the stack and continue. If they don't match, report the error and bail out.

    Pseudo-code could look something like the following:
    // Check a String for matched pairs of properly nested delimiters
     
    Define a String of left delimiters : "}]("
    Define a String of right delimiters: "{])"
     
    //(Matching delimiters in the two Strings are in the same order)
     
    Get a String from the user.
     
    Define a stack of Characters.  (It's empty):  Stack<Character> delimStack = new Stack<Character>();
    //The stack will hold left delimiters as they are encountered in the String.
     
    Repeat the following loop for all of the characters in the String
    BEGIN LOOP
     
        IF the current character is a left delimiter
        THEN
            //
            // Process left delimiter
            //
            Push the current character onto the stack.
        ELSE // End of "IF current character is a left delimiter"
            IF the current character is a right delimiter
            THEN
                //
                // Process right delimiter
                //
                IF the stack is empty
                THEN
                    //This is an error: Report it and bail out.
                ELSE IF (The character on top of the stack is not equal to
                        the matching left delimiter for the current character)
                THEN
                    //This is a nesting error: Report it and bail out.
                ELSE
                    // OK: Top of stack is the matching left delimiter of current
                    // right-delimiter character
                    Remove the character at the top of stack.
                END IF
     
            END IF // End of "IF current characteris a right delimiter
        END // End of the ELSE part of "IF current character is left delimiter...ELSE"
     
    END LOOP
     
    IF the stack is not empty THEN
        This is an error: Report it and bail out.
    ELSE
        Do whatever you do with a valid input string.
    END IF

    Implementation should be a snap if you create a boolean method to see whether a given character is a left delimiter and another boolean method to see whether a given character is a right delimiter. You could also make good use of a method that looks at a right delimiter and returns the matching left delimiter.


    Cheers!

    Z

  4. #4
    Member
    Join Date
    Jun 2012
    Posts
    59
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Having trouble getting started testing for matching delimiter sets.

    I'm having trouble understanding your if methods that involve "processing" the delimeter. What do you mean by process left delimiter and right delimeter? This is what I have so far following your pseudo code.

    public void delimCheck(DataElement obj){
     
    StringElement temp = (StringElement)obj;
    ArrayStack delimHold = new ArrayStack();
     
    for(int i =0; i<temp.message.length(); i++){
     
    	char ch = temp.message.charAt(i);
    	if(ch == '{' || ch == '(' || ch == '['){
    		delimHold.push(temp.message.charAt(i));
    	}
    	else{
    		if(ch == '}' || ch == ')' || ch == ']'){
     
    		}
    	}
     
    }
     
    }

  5. #5
    Member
    Join Date
    Jun 2012
    Location
    Left Coast, USA
    Posts
    451
    My Mood
    Mellow
    Thanks
    1
    Thanked 97 Times in 88 Posts

    Default Re: Having trouble getting started testing for matching delimiter sets.

    Quote Originally Posted by orbin View Post
    I'm having trouble understanding your if methods that involve "processing" the delimeter. What do you mean by process left delimiter and right delimeter?
    Those were comments in the respective blocks that get executed when a left delimiter is encountered and when a right delimiter is encountered. First of all see if my pseudo-code makes sense. There are certainly other approaches that may differ in details.

    If you can't think of a better way, then try implementing it. As you get into actual code, you may think of other, better, ways to do the deed.

    In the meanwhile:

    You already have the idea behind the first step: Processing a left delimiter consists of pushing it onto some kind of stack.

    Cheers!

    Z

Similar Threads

  1. Java Unit Testing How-To Gettin' started
    By Massaslayer in forum Java Theory & Questions
    Replies: 2
    Last Post: May 1st, 2012, 07:58 AM
  2. Java automated testing tools for Unit testing
    By rameezraja in forum Member Introductions
    Replies: 2
    Last Post: April 14th, 2012, 08:51 AM
  3. Scanner delimiter
    By NoviceJAVA in forum What's Wrong With My Code?
    Replies: 1
    Last Post: November 2nd, 2011, 06:44 PM
  4. use Delimiter, Scanner Class
    By izzahmed in forum What's Wrong With My Code?
    Replies: 12
    Last Post: October 25th, 2011, 05:27 PM
  5. delimiter question
    By Sterzerkmode in forum Java SE APIs
    Replies: 1
    Last Post: November 19th, 2009, 05:21 AM