Learning Objectives
Gain some experience using dynamic data structures, which can grow and shrink at execution time.
In this lab, you will use Stacks, and Maps.
Learn to iterate through a dynamic data structures
Introduction
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 Lukasiewicz, 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 ½).Your Task
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.
Stats
Introduction
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
Scenario
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.
Your Task
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.
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).
Make sure to test your methods.