Dynamic Data Structures

1. Gain some experience using dynamic data structures, which can grow and shrink at execution time.
2. In this lab, you will use Stacks, and Maps.
3. Learn to iterate through a dynamic data structures

Set up your directory:

$ mkdir -p ~/cs180/lab14
$ cd ~/cs180/lab14
$ drjava &

• Reverse Polish notation (RPN) is a mathematical notation in which every operator follows all of its operands, in contrast to Polish notation, which puts the operator in the prefix position.
• It is also known as postfix notation and is parenthesis-free as long as operator arities are fixed. The description “Polish” refers to the nationality of logician Jan Łukasiewicz, who invented (prefix) Polish notation in the 1920s.

• In reverse Polish notation the operators follow their operands; for instance, to add 3 and 4, one would write 3 4 + rather than 3 + 4. If there are multiple operations, the operator is given immediately after its second operand; so the expression written 3 − 4 + 5 in conventional notation would be written 3 4 − 5 + in RPN: 4 is first subtracted from 3, then 5 added to it.

• An advantage of RPN is that it obviates the need for parentheses that are required by infix notation. While 3 − 4 × 5 can also be written 3 − (4 × 5), that means something quite different from (3 − 4) × 5. In postfix, the former could be written 3 4 5 × −, which unambiguously means 3 (4 5 ×) − which reduces to 3 20 −; the latter could be written 3 4 − 5 × (or 5 3 4 − ×, if keeping similar formatting), which unambiguously means(3 4 −) 5 ×.

• Despite the name, reverse Polish notation is not exactly the reverse of Polish notation, for the operands of non-commutative operations are still written in the conventional order (e.g. ÷ 6 3 in Polish notation and 6 3 ÷ in reverse Polish both evaluate to 2, whereas 3 6 ÷; in reverse Polish notation would evaluate to ½).

The infix expression

5 + ((1 + 2) × 4) − 3

can be written down like this in RPN:

5 1 2 + 4 × + 3 −

• The expression is evaluated left-to-right, with the inputs interpreted as shown in the following table (the Stack is the list of values the algorithm is “keeping track of” after the Operation given in the middle column has taken place):

• Now that we have explained the working of an RPN Calculator, it is time to make one ourselves.
• We will do that by using the Stack data structure, which is already implemented in the Java libraries.
• Use the push and pop functions as well as the constructor.
• Implement a class Evaluator with a static class method evaluate that takes a String argument comprising an RPN expression and returns the int result.
• Make sure to test your evaluator — pass a String argument to calls to evaluate to check the results.

• In computing, a hash table (such as a Java HashMap) is a data structure used to implement an associative structure that maps keys to values.
• A hash table uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found.
• In a well-dimensioned hash table, the average cost (number of instructions) for each lookup is independent of the number of elements stored in the table.
• Many hash table designs also allow arbitrary insertions and deletions of key-value pairs, at constant average cost per operation.
• In some situations, hash tables turn out to be more efficient than search trees or any other table lookup structure. For this reason, they are widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches, and sets.
• Here is the Java documentation for HashMap: http://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html

• To Create a HashMap in java, we first need to import the required header files:

  import java.util.HashMap;
  import java.util.Map;

• To Create a HashMap in java, we use the HashMap constructor. HashMap is a generic class, which means that we must indicate the types of the keys and values it will use. For a map from String to Integer we use the constructor as follows:

  Map<String,Integer> map = new HashMap<String,Integer>();

• The basic working of a HashMap used to track integer counts is:
  1. Check if the element is present in the map.
  2. If the element is present, increment its corresponding count.
  3. If the element is not present, add the word to the map with its corresponding count.
• To look for an element in the map, use the method: get()
• For example, if we are looking for the word “the”:

  Map<String,Integer> map = new HashMap<String,Integer>();
  String word = "the";
  Integer count = map.get(word);

• If the count in the above example is null, it simply means that the word doesn’t exist in the map.
• To add an element to the map, use the library function: put():

  map.put(word, count);

• The arguments passed to the function put are the word (String) and count (int) which is the total number of times the number is seen. To fetch the count of a given word, use the get() function.

You work for an esteemed sports news website. The big story is that the NBA is having a special all star league, in which teams are assigned randomly before each game. The winner(s) of the competition are the players who are in the most winning teams. Your team has developed a way to organize a file so that your reports come in faster than any other website.

Input file 
The file is formatted as follows in which each line represents one game: The first token is an integer that can be either 1 or 0. It is 1 if the first team won and it is 0 if the second team won.

This token is followed by exactly five tokens representing the player names of the first team (separated by spaces). After that, the token vs token follows and finally five tokens for the player names of the second team.

For example, this line means the second team with players Prelich Murphy Wilkes Gall Greenberg has won :

0 Chan Stine Neilson Curtis Kennedy vs Prelich Murphy Wilkes Gall Greenberg

1. Implement a class Stats with a static class method wins that reads lines of input from a BufferedReader and computes winner statistics for each of the players mentioned in the input, by constructing a HashMapmapping the names of the players (String) to the number of wins (Integer) that player has accumulated, and returns the resulting HashMap.
2. Now, implement a static class method winner that iterates through a HashMap, such as returned by wins, returning the name of the player with the most wins (in the case of a tie, return any such player).
3. Make sure to test your methods.