• API
• FAQ
• Tools
• Trends
• Archive
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.
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--){
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;
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);
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