SHARE
TWEET

Untitled

a guest Feb 17th, 2017 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2. import java.util.*;
  3. import java.text.*;
  4. import java.math.*;
  5. import java.util.regex.*;
  6.  
  7. public class Solution {
  8.     public static void main(String args[] ) throws Exception {
  9.  
  10.        Scanner in = new Scanner(System.in);
  11.        
  12.        //System.out.print("Enter your sentence: ");
  13.        String sentence = in.nextLine();
  14.        String binaryString="";      //this stores the string of binary code
  15.        
  16.        
  17.        for(int i=0; i < sentence.length(); i++){        //go through the sentence
  18.            int decimalValue = (int)sentence.charAt(i);      //convert to decimal
  19.            String binaryValue = Integer.toBinaryString(decimalValue);      //convert to binary
  20.            for(int j=7;j>binaryValue.length();j--){
  21.                binaryString+="0";           //this loop adds in those pesky leading zeroes
  22.             }
  23.            binaryString += binaryValue+" "; //add to the string of binary
  24.        }
  25.        //System.out.println(binaryString);    //print out the binary
  26.        
  27.              
  28.        int[] array = new int[256];      //an array to store all the frequencies
  29.        
  30.        for(int i=0; i < sentence.length(); i++){    //go through the sentence
  31.            array[(int)sentence.charAt(i)]++;    //increment the appropriate frequencies
  32.            
  33.        }
  34.        
  35.        
  36.        PriorityQueue < Tree >  PQ = new PriorityQueue < Tree >() ;  //make a priority queue to hold the forest of trees    
  37.        
  38.        
  39.        for(int i=0; i<array.length; i++){ //go through frequency array
  40.            if(array[i]>0){ //print out non-zero frequencies - cast to a char
  41.                 //System.out.println("'"+(char)i+"' appeared "+array[i]+((array[i] == 1) ? " time" : " times"));
  42.      
  43.                //FILL THIS IN:
  44.  
  45.                        Tree Tr = new Tree();
  46.                        Tr.root = new Node();
  47.                        Tr.root.letter = (char)i;
  48.                        Tr.frequency = array[i];
  49.                        Tr.alphabet=i;
  50.                        PQ.add(Tr);
  51.                    }
  52.                }
  53.                //MAKE THE FOREST OF TREES AND ADD THEM TO THE PQ
  54.                
  55.                //create a new Tree
  56.                //set the cumulative frequency of that Tree
  57.                //insert the letter as the root node
  58.                //add the Tree into the PQ
  59.  
  60.        
  61.        
  62.         while(PQ.size()>1){             //while there are two or more Trees left in the forest
  63.            
  64.             //FILL THIS IN:
  65.            
  66.             Tree tr1=PQ.poll();
  67.             Tree tr2=PQ.poll();
  68.             Tree combo= new Tree();
  69.             combo.frequency=tr1.frequency+tr2.frequency;
  70.             combo.root=new Node();
  71.             combo.root.leftChild=tr1.root;
  72.             combo.root.rightChild=tr2.root;
  73.             combo.alphabet=Math.min(tr1.alphabet,tr2.alphabet);
  74.             PQ.add(combo);
  75.  
  76.            
  77.            
  78.             //IMPLEMENT THE HUFFMAN ALGORITHM
  79.            
  80.             //when you're making the new combined tree, don't forget to assign a default root node (or else you'll get a null pointer exception)
  81.             //if you like, to check if everything is working so far, try printing out the letter of the roots of the two trees you're combining
  82.         }
  83.  
  84.         Tree HuffmanTree = PQ.poll();   //now there's only one tree left - get its codes
  85.        
  86.        
  87.         //FILL THIS IN:
  88.         for(int j=0; j<sentence.length(); j++)
  89.             {
  90.                 System.out.print(HuffmanTree.getCode(sentence.charAt(j)));
  91.             }
  92.         }
  93.         //get all the codes for the letters and print them out
  94.         //call the getCode() method on the HuffmanTree Tree object for each letter in the sentence
  95.  
  96.         //print out all the info
  97.     }
  98.  
  99.  
  100. class Node
  101.    {
  102.    
  103.    public char letter='@';            //stores letter
  104.    
  105.    public Node leftChild;         // this node's left child
  106.    public Node rightChild;        // this node's right child
  107.    
  108.    
  109. }  // end class Node
  110.  
  111. ////////////////////////////////////////////////////////////////
  112. class Tree implements Comparable<Tree>
  113.    {
  114.    public Node root;             // first node of tree
  115.    public int frequency=0;
  116.    public int alphabet=0;
  117. // -------------------------------------------------------------
  118.    public Tree()                  // constructor
  119.       {   root = null; }            // no nodes in tree yet
  120. // -------------------------------------------------------------
  121.  
  122. //the PriorityQueue needs to be able to somehow rank the objects in it
  123. //thus, the objects in the PriorityQueue must implement an interface called Comparable
  124. //the interface requires you to write a compareTo() method so here it is:
  125.  
  126.    public int compareTo(Tree object){ //
  127.        if(frequency-object.frequency>0){ //compare the cumulative frequencies of the tree
  128.            return 1;
  129.         }else if(frequency-object.frequency<0){
  130.            return -1;   //return 1 or -1 depending on whether these frequencies are bigger or smaller
  131.         }else if(alphabet-object.alphabet<0)
  132.          {  
  133.            return -1;
  134.         }
  135.        else if(alphabet-object.alphabet>0)
  136.            {
  137.            return 1;
  138.        }
  139.        else{
  140.            return 0;
  141.        }
  142.    }
  143.    
  144.    
  145. // -------------------------------------------------------------
  146.  
  147.    String path="error";     //this variable will track the path to the letter we're looking for
  148.  
  149.    public String getCode(char letter){  //we want the code for this letter
  150.  
  151.        inOrder(root, letter, "");    //call an inOrder traversal, starting at the root, looking for this letter
  152.        return path;     //return the path that results
  153.            
  154.    }
  155.  
  156. // -------------------------------------------------------------
  157.    private void inOrder(Node localRoot, char letter, String path){ //the path variable tracks the current search path
  158.       if(localRoot != null){ //if root is null we've gone off the edge of the tree - back up
  159.           if(localRoot.letter==letter){
  160.             this.path=path;     //if we've found the letter, note the path - final path = current search path
  161.           }else{
  162.             inOrder(localRoot.leftChild, letter, path+"0"); //go left and add "0" to the current search path
  163.             inOrder(localRoot.rightChild, letter, path+"1");    //go right and add "1" to the current search path
  164.          }
  165.       }
  166.       return; //quit searching this branch of the tree
  167.    }
  168. // -------------------------------------------------------------
  169. }  // end class Tree
  170. ////////////////////////////////////////////////////////////////
RAW Paste Data
Top