The program needs to read in characters and push them into the stack calledstartStack.

Two classes already provided:

Main.java(No need to modify)

CharacterOrganizer.java (Need to modify in order to get the program running)

A user can specify how many characters will be entered, and these characters will be distinct, and they are 'a', 'b', 'c', 'd', 'e', ... up to some alphabet character in lower cases.

For instance, if a user specifies that 7 characters will be entered, then the characters to be inserted into the startStack will be: 'a', 'b', 'c', 'd', 'e', 'f', 'g', but they might not be in any sorted order, for instance, 'c', 'f', 'd', 'g', 'a', 'b', 'e'.

Then your program should remove each element from the startStack from its top one by one, and the objective to insert all characters into the stack calledfinalStackin the alphabetical order.

If the top character of the startStack is 'a', then you can push 'a' into the finalStack. However, if it is some other larger character, then it needs to wait to be pushed into the finalStack until all characters that are smaller than it are already pushed into the finalStack.

Here, we will be using other stacks calledsupportingStacks. The number of such supporting stacks will be specified by a user as well and it will be an array of Stack objects.

If there is a character larger than 'a', then you need to push it onto one of the supporting stacks, but here is the condition:

-Check if characters in each supporting stack are in alphabetical order, if one is empty or the character to be pushed is smaller than the top element of the supporting stack, then you can push the character onto such supporting stack. This supporting stack is calledchosenStackfor the character.

-If you cannot find such supporting stack, then it means that you cannot run this organization task. It should stop and return false.

Once the character 'a' is stored in the finalStack, then you need to keep checking if the top character of the startStack is 'b', or the top of any supporting stack is 'b'. If the top character of the startStack is 'b', then you can push it onto the finalStack. If the top of any supporting stack is 'b', then pop it, and push it onto the finalStack.

After this, you need to keep looking for the next character 'c', and so on until the largest character is pushed onto the finalStack.

Here is an example. Suppose that you are given the following sequence of characters:

'g' 'i' 'a' 'b' 'e' 'f' 'h' 'd' 'c'

with three supporting stacks #0, #1, and #2.

The top of the startStack is 'c', if you pushed all characters from left to right onto the startStack. Since it is not the smallest, you need to push 'c' onto the supporting stack, say, #0.

The next character of the startStack is 'd'. It cannot be pushed onto the supporting stack #0 because it is larger than the top of the supporting stack #0, which is 'c'. So we can push 'd' onto another supporting stack, say #1.

Similarly, 'h' will be pushed onto the supporting stack #2.

Now, the next character 'f' can be pushed only onto the supporting stack #2 because that is the only stack whose top is larger than 'f'. Remember, the content of each supporting stack needs to be increasing order.

After pushing 'c', 'd', 'h', 'f', 'e', 'b' onto supporting stacks, the content of supporting stacks will be:

Supporting stack 0: [c, b]

Supporting stack 1: [d]

Supporting stack 2: [h, f, e]

The next character from the startStack is 'a', so this is pushed directly onto the finalStack.

At this point, the next smallest character 'b' is at the top of the supporting stack #0. So we pop it and push it onto the finalStack. Then we will do the same for the character 'c'. We continue to pop from the supporting stacks as long as the next smallest character is at the top of one of the supporting stacks.

After popping 'b', 'c', 'd', 'e', and 'f', we have:

Supporting stack 0: []

Supporting stack 1: []

Supporting stack 2: [h]

The next smallest character 'g' is not in the supporting stacks, so we need to re-start popping characters from the startStack which still contains: ['g', 'i'].

Instruction:Main class

This class displays a menu for the Character Organization. If a user enters "C", then it asks to enter a size of the startStack and also a number of supporting stacks, then it will display a result for the problem. This class is given by the instructor.

CharacterOrganizer class

The CharacterOrganizer class contains a constructor to set up an initial configuration.

It also contains methods to print out stacks as well as to reorganize stack content. You need to complete the methods in CharacterOrganizer class by following its instructions. Those methods are organizeCharacters(), fromSupportingStackToFinalStack(), putInSupportingStack().

Main class:

import java.io.*; public class Main { public static void main (String[] args) throws IOException { char input1; String line = new String(); printMenu(); InputStreamReader isr = new InputStreamReader(System.in); BufferedReader stdin = new BufferedReader(isr); do // will ask for user input { System.out.println("What action would you like to perform?"); line = stdin.readLine(); input1 = line.charAt(0); input1 = Character.toUpperCase(input1); if (line.length() == 1) { // matches one of the case statements switch (input1) { case 'C': //Specify Problem parameters try { System.out.print("Please specify how many characters will be used (the maximum is 26): "); int stackSize = Integer.parseInt(stdin.readLine().trim()); System.out.print("Please specify how many supporting stacks to use: "); int numberOfSupportingStacks = Integer.parseInt(stdin.readLine().trim()); if (stackSize > 0 && stackSize <= 26 && numberOfSupportingStacks > 0) { //Create an organizer object CharacterOrganizer organizer = new CharacterOrganizer(stackSize, numberOfSupportingStacks); //Read-in characters and add them to the stack for (int i = 0; i < stackSize; i++) { System.out.print("Please enter a character: "); char character1 = stdin.readLine().trim().charAt(0); organizer.addCharacterToStack(character1); } //sort the elements using stacks boolean success = organizer.organizeCharacters(); if (success == true) { System.out.print(" organization completed "); } else { System.out.print(" organization not completed "); } } else { System.out.print("Please enter a valid integer "); } } catch(NumberFormatException ex) { System.out.print("Please enter a valid number "); } break; case 'Q': //Quit break; case '?': //Display Menu printMenu(); break; default: System.out.print("Unknown action "); break; } } else { System.out.print("Unknown action "); } } while (input1 != 'Q' || line.length() != 1); } /** The method printMenu displays the menu to a user**/ public static void printMenu() { System.out.print("Choice\t\tAction " + "------\t\t------ " + "C\t\tSpecify Problem Parameters " + "Q\t\tQuit " + "?\t\tDisplay Help "); } } 

CharacterOrganizer class:

import java.util.Stack; public class CharacterOrganizer { private Stack startStack; //stack contains characters in an order specified by a user private Stack finalStack; //stack to have characters in sorted order after running this algorithm private Stack[] supportingStacks; //stacks to hold some characters that are not in either start or final stack private int sizeOfStartStack; //the start stack size private int numberOfSupportingStacks; //number of supporting stacks, specified by a user private char smallestCharacter; //current smallest character that can be moved to the final stack private int stackWithNextSmallest; //the index of supporting stack that contains the next smallest character private final int ASCII_FOR_a = ((int) 'a'); //ASCII number for a, we can use it to keep track of smallest/largest characters //Constructor to initialize member variables public CharacterOrganizer(int sizeOfStartStack, int numOfSupportingStacks) { startStack = new Stack(); finalStack = new Stack(); this.sizeOfStartStack = sizeOfStartStack; this.numberOfSupportingStacks = numOfSupportingStacks; supportingStacks = new Stack[numberOfSupportingStacks]; for (int i=0; i< numberOfSupportingStacks; i++) { supportingStacks[i] = new Stack(); } smallestCharacter = (char) (sizeOfStartStack+1-ASCII_FOR_a); //itinialize to a large character stackWithNextSmallest = -1; //index of supporting stack containing the next smallest is unknown } //The addCharacterToStack adds the parameter character //to the start stack public void addCharacterToStack(char character1) { startStack.push(character1); } //The printSupportingStacks prints out the content //of the supporting stacks public void printSupportingStacks() { System.out.println("Supporting Stack Contents: "); for (int i = 0; i < numberOfSupportingStacks; i++) { System.out.println("Supporting Stack " + i + ": " + supportingStacks[i].toString()); } System.out.println(); } //The organizeCharacters method reorganizes the characters in the start stack //into a sorted order in the final stack public boolean organizeCharacters() { boolean success = true; //the next character that should move to final stack is initially 'a' char nextCharacterToFinalStack = 'a'; //Print out the start stack content System.out.println("Start Stack Content: " + startStack.toString()); while(startStack.empty() == false) { //get the next character to move char nextCharacter; //get(pop) the next character to move from the start stack //and assign it to "nextCharacter" /****1. ADD Your Code Here ****/ if (nextCharacter == nextCharacterToFinalStack) { //if it is the next smallest character, //then push it onto the final stack /***2. ADD Your Code Here ****/ System.out.println("Move character " + nextCharacter + " from start stack to final stack"); //nextCharacterToOutputStack should be incremented now //to loop for the next smallest character. nextCharacterToFinalStack++; //As long as the smallest character among all supporting stacks //is same as the next character to move to final stack, //process the following: while (smallestCharacter == nextCharacterToFinalStack) { //look for the next smallest character among supporting stacks //This will compute the smallest character and which supporting stack it belongs fromSupportingStackToFinalStack(); nextCharacterToFinalStack++; } } else { //put the next character into one of the supporting stack if (putInSupportingStack(nextCharacter) == false) { success = false; return success; } } } System.out.println("Final Stack Content: " + finalStack.toString()); return success; } //The fromSupportingStackToFinalStack moves the smallest element among //all supporting stacks into the final stack. //It also keeps track of the next smallest character and the supporting stack //that contains in it. public void fromSupportingStackToFinalStack() { if (stackWithNextSmallest >= 0 && supportingStacks[stackWithNextSmallest].isEmpty() == false) { //remove(pop) the smallest character from its supporting stack //and move(push) to the final stack /****3. ADD Your Code Here ****/ System.out.println("Move character " + smallestCharacter + " from supporting stack#" + stackWithNextSmallest + " to final stack"); printSupportingStacks(); } //Find the next smallest character and the supporting stack that contains it //by checking the top of all supporting stacks smallestCharacter = (char) (sizeOfStartStack + 1 - ASCII_FOR_a); for (int i = 0; i < numberOfSupportingStacks; i++) { if (supportingStacks[i].isEmpty() == false && (supportingStacks[i].peek()).charValue() < smallestCharacter) { smallestCharacter = supportingStacks[i].peek().charValue(); stackWithNextSmallest = i; } } //After the above loop, the variable "stackWithNextSmallest" should have an index //of the holding stack contains the next smallest character //AND the variable "smallestCharacter" should have the next smallestCharacter //to move to the final stack. } //The putInSupportingStack tries to push the parameter character //into the chosen stack, i.e., the one with the top element larger //than the parameter character and also with the top element smallest among //such supporting stacks. //If it cannot find such supporting stack, it returns false. public boolean putInSupportingStack(char character2) { int chosenStackIndex = -1; //initialize to a stack index that does not exists char bestTop = (char) (sizeOfStartStack + 1 + ASCII_FOR_a); //initialize a larger character for (int i = 0; i < numberOfSupportingStacks; i++) { //look for a non-empty stack that contains its top character which is larger than //the parameter character to push into. //The index of the supporting stack with smallest top should be the chosenStackIndex //If the stack that you check is empty, go ahead and pick that supporting //stack's index as the chosenStackIndex if the chosenStackIndex was not //selected yet. /****4. ADD Your Code Here ****/ } //The process cannot be completed //since all supporting stacks have its top character being smaller than //the character to be inserted. if (chosenStackIndex == -1) return false; //The process can continue, by pushing the parameter "character2" //into the supporting stack of the chosenStackIndex /****5. ADD Your Code Here ****/ System.out.println("Move the character " + character2 + " from start stack " + "to supporting stack#" + chosenStackIndex); printSupportingStacks(); //update the variable "smallestCharacter" to the parameter character2 //and the variable "stackWithNextSmallest" to "chosenStackIndex" //if character2 is smaller than "smallestCharacter" /****6. ADD Your Code Here ****/ return true; } }