• December 10th, 2012, 02:13 PM
billyjthorton
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:
Code :

```  /* * 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:
Code :

```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!
• December 10th, 2012, 02:53 PM
Norm
Is this the logic: if false return false
• December 10th, 2012, 03:09 PM
billyjthorton
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....
• December 10th, 2012, 03:29 PM
Norm
Quote:

Here's the code I made so far:
I'm confused. If you wrote the code what are you asking here:
Quote:

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
• December 10th, 2012, 03:50 PM
billyjthorton
Here is the missing class:

Code :

```/* * 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....
• December 10th, 2012, 03:59 PM
Norm
Quote:

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.
Code :

``` // scan tracks for (int i = 1; i <= numberOfTracks; i++) <<<<<< MISSING { HERE if (!track[i].empty())```
• December 10th, 2012, 04:17 PM
billyjthorton
Yea, that makes sense, but what about the original question and what's happening on that line...
• December 10th, 2012, 04:18 PM
Norm
Quote:

what's happening on that line...
That line calls a method and tests what the method returns.
• December 10th, 2012, 04:30 PM
billyjthorton
So when the method returns true, it converts it to false?
• December 10th, 2012, 04:35 PM
Norm
Please show the code and explain the problem you are having.

Code :

```if (!putInHoldingTrack(inputOrder[i])) return false;```
If the called method returns false, the current executing method returns false.
• December 10th, 2012, 08:37 PM
billyjthorton