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 12 of 12

Thread: Help please!

  1. #1
    Junior Member
    Join Date
    Sep 2012
    Posts
    13
    Thanks
    1
    Thanked 1 Time in 1 Post

    Exclamation Help please!

    Hello all,

    I was creating a program for a homework assignment and I came across a problem. The assignment is a simulation of a train track. It gives you an array of train cars and using stacks, you put them in order. So for example, if I have the array of train cars [4,5,7,8,2,1,9,3], the program using stacks with make it [1,2,3,4,5,7,8,9]. In essence its taking cars from an input track onto holding tracks and then onto an output track.

    Here's the code I made so far:
     
    /*
     * To change this template, choose Tools | Templates
     * and open the template in the editor.
     */
    package railroadwithstacks;
     
    /** railroad car rearrangement using stacks */
     
     
    public class RailroadWithStacks
    {
       // data members
       private static ArrayStack [] track; // array of holding tracks
       private static int numberOfCars;
       private static int numberOfTracks;
       private static int smallestCar; // smallest car in any holding track
       private static int itsTrack;    // holding track with car smallestCar
     
       /** output the smallest car from the holding tracks */
       private static void outputFromHoldingTrack()
       {
          // remove smallestCar from itsTrack
          track[itsTrack].pop();
          System.out.println("Move car " + smallestCar + " from holding "
                             + "track " + itsTrack + " to output track");
     
          // find new smallestCar and itsTrack by checking top of all stacks
          smallestCar = numberOfCars + 2;
          for (int i = 1; i <= numberOfTracks; i++)
             if (!track[i].empty() &&
                 ((Integer) track[i].peek()).intValue() < smallestCar)
             {
                smallestCar = ((Integer) track[i].peek()).intValue();
                itsTrack = i;
             }
       }
     
      /** put car c into a holding track
        * @return false iff there is no feasible holding track for this car */
       private static boolean putInHoldingTrack(int c)
       {
          // find best holding track for car c
          // initialize
          int bestTrack = 0,               // best track so far
              bestTop = numberOfCars + 1;  // top car in bestTrack
     
          // scan tracks
          for (int i = 1; i <= numberOfTracks; i++)
             if (!track[i].empty())
             {// track i not empty
                 int topCar = ((Integer) track[i].peek()).intValue();
                 if (c < topCar && topCar < bestTop)
                 {
                    // track i has smaller car at top
                    bestTop = topCar;
                    bestTrack = i;
                 }
             }
             else // track i empty
                if (bestTrack == 0) bestTrack = i;
     
          if (bestTrack == 0) return false; // no feasible track
     
          // add c to bestTrack
          track[bestTrack].push(new Integer(c));
          System.out.println("Move car " + c + " from input track "
                             + "to holding track " + bestTrack);
     
          // update smallestCar and itsTrack if needed
          if (c < smallestCar)
          {
              smallestCar = c;
              itsTrack = bestTrack;
          }
     
          return true;
       }
     
      /** rearrange railroad cars beginning with the initial order
        * inputOrder[1:theNumberOfCars]
        * @return true if successful, false if impossible. */
       public static boolean railroad(int [] inputOrder,
                             int theNumberOfCars, int theNumberOfTracks)
       {
          numberOfCars = theNumberOfCars;
          numberOfTracks = theNumberOfTracks;
     
          // create stacks track[1:numberOfTracks] for use as holding tracks
          track = new ArrayStack [numberOfTracks + 1];
          for (int i = 1; i <= numberOfTracks; i++)
             track[i] = new ArrayStack();
     
          int nextCarToOutput = 1;
          smallestCar = numberOfCars + 1;  // no car in holding tracks
     
          // rearrange cars
          for (int i = 1; i <= numberOfCars; i++)
             if (inputOrder[i] == nextCarToOutput)
             {// send car inputOrder[i] straight out
                 System.out.println("Move car " + inputOrder[i]
                                    + " from input track to output track");
                 nextCarToOutput++;
     
                 // output from holding tracks
                 while (smallestCar == nextCarToOutput)
                 {
                    outputFromHoldingTrack();
                    nextCarToOutput++;
                 }
             }
             else
             // put car inputOrder[i] in a holding track
                if (!putInHoldingTrack(inputOrder[i]))
                   return false;
     
          return true;
       }
     
       /** test program */
       public static void main(String [] args)
       {
          // int [] p = {0, 5, 8, 1, 7, 4, 2, 9, 6, 3};
          int [] p = {0, 3, 6, 9, 2, 4, 7, 1, 8, 5};
          System.out.println("Input permutation is 369247185");
          railroad(p, 9, 3);
       }
    }

    My question comes from the line:
    if (!putInHoldingTrack(inputOrder[i]))
        return false;

    Why does it only work with the not ("!") operator in front of it. Why will it not just put it into the holding tracks without it? (thats the goal of the statement)

    Thanks in advance for your help in explanation of this. It will really help me!
    If you don't understand something, feel free to ask!

  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    18,661
    Thanks
    45
    Thanked 1,960 Times in 1,934 Posts

    Default Re: Help please!

    Is this the logic: if false return false
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Junior Member
    Join Date
    Sep 2012
    Posts
    13
    Thanks
    1
    Thanked 1 Time in 1 Post

    Default Re: Help please!

    but how does it know to move something to the holding track? All it is is checking that statement's Boolean value (if its true or false) and doesn't actually do the operation....

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    18,661
    Thanks
    45
    Thanked 1,960 Times in 1,934 Posts

    Default Re: Help please!

    Here's the code I made so far:
    I'm confused. If you wrote the code what are you asking here:
    how does it know to move something to the holding track?

    The posted code does not compile. It has a Missing class.
    There is no way to test it.

    The posted code uses a VERY POOR technique:
    It does NOT use {}s around LARGE blocks of code inside of
    for loops. This leaves a trap for anyone trying to read and to change the code.
    You should ALWAYS enclose the code in a for loop inside {}s
    If you don't understand my answer, don't ignore it, ask a question.

  5. #5
    Junior Member
    Join Date
    Sep 2012
    Posts
    13
    Thanks
    1
    Thanked 1 Time in 1 Post

    Default Re: Help please!

    Here is the missing class:

    /*
     * To change this template, choose Tools | Templates
     * and open the template in the editor.
     */
    package railroadwithstacks;
     
    /** a stack class that uses a one-dimensional array */
     
     
    import java.util.EmptyStackException;
    import java.util.*;
     
    public class ArrayStack
    {
       // data members
       int top;          // current top of stack
       Object [] stack;  // element array
     
       // constructors
       /** create a stack with the given initial capacity
         * @throws IllegalArgumentException when initialCapacity < 1 */
       public ArrayStack(int initialCapacity)
       {
          if (initialCapacity < 1)
             throw new IllegalArgumentException
                   ("initialCapacity must be >= 1");
          stack = new Object [initialCapacity];
          top = -1;
       }
     
       /** create a stack with initial capacity 10 */
       public ArrayStack()
          {this(10);}
     
       // methods
       /** @return true iff stack is empty */
       public boolean empty()
          {return top == -1;}
     
     
       /** @return top element of stack
         * @throws EmptyStackException when the stack is empty */
       public Object peek()
       {
          if (empty())
             throw new EmptyStackException();
          return stack[top];
       }
     
       /** add theElement to the top of the stack */
       public void push(Object theElement)
       {
          // increase array size if necessary
          //if (top == stack.length - 1)
             //stack = ChangeArrayLength.changeLength1D(stack, 2 * stack.length);
     
          // put theElement at the top of the stack
          stack[++top] = theElement;
       }
     
       /** remove top element of stack and return it
         * @throws EmptyStackException when the stack is empty */
       public Object pop()
       {
          if (empty())
             throw new EmptyStackException();
          Object topElement = stack[top];
          stack[top--] = null;   // enable garbage collection
          return topElement;
       }
     
       /** test program */
       public static void main(String [] args)
       {  
          int x;
          ArrayStack s = new ArrayStack(3);
          // add a few elements
          s.push(new Integer(1));
          s.push(new Integer(2));
          s.push(new Integer(3));
          s.push(new Integer(4));
     
     
          // delete all elements
          while (!s.empty())
          {
             System.out.println("Top element is " + s.peek());
             System.out.println("Removed the element " + s.pop());
          }
       }  
    }

    I'm not sure what your talking about when you say I do not use {} around LARGE blocks of code....

  6. #6
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    18,661
    Thanks
    45
    Thanked 1,960 Times in 1,934 Posts

    Default Re: Help please!

    I'm not sure what your talking about when you say I do not use {}
    Most of the for statements are missing {}s for the code inside the loop. These all must be fixed.
    If You try to add a statement at the beginning of the loop, all the code currently in the loop will be pushed out of the loop. It is not possible to add a statement at the end of the loop.
       // scan tracks
          for (int i = 1; i <= numberOfTracks; i++)  <<<<<< MISSING { HERE
             if (!track[i].empty())
    If you don't understand my answer, don't ignore it, ask a question.

  7. The Following User Says Thank You to Norm For This Useful Post:

    billyjthorton (December 10th, 2012)

  8. #7
    Junior Member
    Join Date
    Sep 2012
    Posts
    13
    Thanks
    1
    Thanked 1 Time in 1 Post

    Default Re: Help please!

    Yea, that makes sense, but what about the original question and what's happening on that line...

  9. #8
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    18,661
    Thanks
    45
    Thanked 1,960 Times in 1,934 Posts

    Default Re: Help please!

    what's happening on that line...
    That line calls a method and tests what the method returns.
    If you don't understand my answer, don't ignore it, ask a question.

  10. #9
    Junior Member
    Join Date
    Sep 2012
    Posts
    13
    Thanks
    1
    Thanked 1 Time in 1 Post

    Default Re: Help please!

    So when the method returns true, it converts it to false?

  11. #10
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    18,661
    Thanks
    45
    Thanked 1,960 Times in 1,934 Posts

    Default Re: Help please!

    Please show the code and explain the problem you are having.

    if (!putInHoldingTrack(inputOrder[i]))
        return false;
    If the called method returns false, the current executing method returns false.
    If you don't understand my answer, don't ignore it, ask a question.

  12. #11
    Junior Member
    Join Date
    Sep 2012
    Posts
    13
    Thanks
    1
    Thanked 1 Time in 1 Post

    Default Re: Help please!

    So then what is the purpose of the not operator in that same method call? (I'm referring to the lines you have quoted)

  13. #12
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    18,661
    Thanks
    45
    Thanked 1,960 Times in 1,934 Posts

    Default Re: Help please!

    the purpose of the not operator
    When false is returned by the method, the not operator makes the expression true: !false = true
    When the expression is true, the statement following the if is executed:
    return false;
    If you don't understand my answer, don't ignore it, ask a question.