RPN Calculator (using Scala, python and Java)

1. Description

One of the earliest Programming Praxis challenges is called RPN Calculator . Our task is to write a RPN module capable of evaluating simple RPN expressions and return the right result . The exact requirment:

Implement an RPN calculator that takes an expression like 19 2.14 + 4.5 2 4.3 / - * which is usually expressed as (19 + 2.14) * (4.5 - 2 / 4.3) and responds with 85.2974. The program should read expressions from standard input and print the top of the stack to standard output when a newline is encountered. The program should retain the state of the operand stack between expressions.

Programming Praxis

The natural algorithm to resolve this exercise is stack-based :

The first step is to tokenize the expression .If the expression is “19 2.14 + 4.5 2 4.3 / – *” after the tokenization the resulting structure will be an array of operands and operators, for example an array of Strings {“19”, “2.14”, “+”, “4.5”, “2”, “4.3”, “/”, “-“, “*”} .
At the second step we iterate over the array of tokens .If the token:

  • Is an operand (number, variable) – we push in onto the stack .
  • Is an operator (we apriopri know the operator takes N arguments), we pop N values from the stack, we evaluate the operator with those values as input parameters, we push the result back onto the stack .
If the RPN expression is valid, after we apply the previous steps, the stack would contain only one value, which is the result of the calculation .

2. Implementation

I will implement the solutions for this challenge using three different languages: Scala, python and Java .

2.1 Scala Solution

import scala.collection.mutable.Stack
import scala.io.Source
import java.lang.Double.parseDouble

/**
* RPN Calculator .
*
* @author Andrei Ciobanu
* @date JAN 2, 2011
**/

object RPNCalc {
  // Maps an operator to a function .
  val ops = Map("+" -> ((_:Double) + (_:Double)),
          "-" -> (-(_:Double) + (_:Double)),
          "*" -> ((_:Double) * (_:Double)),
          "/" -> (1/(_:Double) * (_:Double)))

  // Evaluate RPN expr (given as string of tokens)
  def evalTokens(tokens: Array[String]) : Double = {
    val stack = new Stack[Double]
    tokens.foreach(tok => {
      if (ops.contains(tok)) stack.push(ops(tok)(stack.pop, stack.pop))
      else stack.push(parseDouble(tok))
    })
    stack.pop
  }

  // Main  function
  def main(args: Array[String]) = {
    // Read line by line from stdin + tokenize line + evaluates line
    Source.fromInputStream(System.in).getLines.foreach(l =>
      printf("exp=%2.2fn", evalTokens(l.split(" "))))
  }
}

And if we compile and run the above code:

Fraction reduction in Scala (first contact)

After a failed attempt to grasp Haskell, but somewhat seduced by the concise and elegant ways of Functional Programming, I’ve started to look for alternatives . Knowing Java, and having an everyday interaction with the JVM the obvious choices were Clojure or Scala . I never had the chance to try Clojure, probably because right now I enjoy Scala so much (the butterflies…) . Of course I cannot say that Scala scales, or if Scala is the next Java, or Scala is the answer, but from what I’ve experienced so far, things look good and I am optimistic that some day Scala will receive the attention it deserves .

There are a lot good books on Scala, but probably the most popular is “Programming in Scala, A comprehensive step-by-step guide” by Martin Odersky (Scala’s creator), Lex Spoon, and Bill Venners .

In a chapter there, the authors give us an insight on how to create Functional Objects -> objects that are immutable . The materialization of the concept is a Rational class, that encapsulates the idea of rational numbers . It allows us to be add, subtract, multiply, compare etc. rational numbers .  At some point in the example the fraction is reduced to the lowest terms.

Reducing the fraction to its lowest terms  (also known as normalization) is probably one of the simplest programming exercises we all start with . The actual problem is to determine the greatest common divisor of the fraction’s denominator and numerator, and divide those numbers by it . Not long ago I’ve written a solution for this exercise in C, but we all know C is far from being an elegant peace of technology.

Inspired (a lot!) by the example in the book, I’ve come with this solution:

Fraction.scala

class Fraction(n: Int, d: Int) {
  // It makes no sense to have the denominator 0
  require(d != 0)

  private val g = gcd(n, d)
  val numerator : Int = n / g
  val denominator : Int = d / g

  // Determines the greatest common divisor of two numbers
  private def gcd(a: Int, b: Int) : Int =
    if (b == 0) a else gcd(b, a % b)

  override def toString =
    numerator + "/" + denominator
}

MainObject.scala

// Singleton Object
object MainObject {
  def main(args: Array[String]) = {
    val f = new Fraction(25, 100)
    println(f)
  }
}

To compile and run the above we can use scalac (the equivalent of javac) as:

Insertion Sort Algorithm

1. Algorithm Description

Insertion Sort is one of the simplest, but less effective, sorting algorithms . It works very similar to the way (us humans) sort a hard of playing cards:

1. At first none of our cards are sorted . So we start with an “empty” space in our hand were we are going to insert cards one at a time .
2. We take a card from our hand and we put it in the “special place” were we planned to keep our cards sorted . We do this for every card in our initial hand, until we finish them off .
3. Finding the right position for the insertion is not hard . At this point we can apply two tactics :

  • We compare the card we are planning to insert with all the cards that are already in sorted state O(n);
  • We use binary search to determine the right position (O(logn)) .

In our case that “special place” were we are going to insert cards one at a time, is not an additional array, but the array itself . We know for sure that an array of size 1 is always sorted, so we consider that first sorted sub-array, is the block composed by the first element .

For example, we want to sort the following array (with bold, are the elements already sorted):

8 0 3 11 5 -1 14 10 1 1 -2 Array is unsorted .
8 0 3 11 5 -1 14 10 1 1 -2 The first sorted block is {8} .
0 8 3 11 5 -1 14 10 1 1 -2 We compare {0} with {8} we move {0} at the new position, we shift {8} .
0 3 8 11 5 -1 14 10 1 1 -2 We compare {3} with {8}, {0}, we move {3} at the new position, we shift {8} .
0 3 8 11 5 -1 14 10 1 1 -2 We compare {11} with {8}, {11} remains at the same position .
0 3 5 8 11 -1 14 10 1 1 -2 We compare {5} with {11}, {8} and {3}, we move {5} at the new position, we shift {8}, {11} .
-1 0 3 5 8 11 14 10 1 1 -2 We compare {-1} with {11}, {8}, …, {0}, we move {-1} at the new position, we shift {0}, {3}, … {11} .
-1 0 3 5 8 11 14 10 1 1 -2 We compare {14} with {11}, we move {11} at the new position .
-1 0 3 5 8 10 11 14 1 1 -2 We compare {10} with {14}, {11}, {8}, we move {10} at the new position, we shift {11}, {14}.
-1 0 1 3 5 8 10 11 14 1 -2 We compare {1} with {14}, {11}, …, {0}, we move {1} at the new position, we shift {3}, {5}, …, {14} .
-1 0 1 1 3 5 8 10 11 14 -2 We compare {1} with {14}, {11}, …, {1}, we move {1} at the new position, we shift {3}, {5}, …, {14} .
-2 -1 0 1 1 3 5 8 10 11 14 We compare {-2} with {14}, {11}, …, {-1}, we move {-2} at the new position, we shift {-1}, {0}, …, {14} .

The pseudo-code for the algorithm can be easily written as follows:

FUNCTION SORT(A, length)
  // The array is 0-indexed
  FOR i:=1 TO length DO
    key := A[i]
    j := i - 1

    // COMPARE
    WHILE j >= 0 AND A[j] > key DO
      // SHIFT
      A[j+1] := A[j]
      j := j - 1

    // MOVE
    A[j+1] = key

2. Algorithm Implemenation in Java

The Java implementation of the algorithm is pretty straight-forward (follow the comments):

Bottom-up Merge Sort (non-recursive)

1. Algorithm Description

In the last article I’ve described a recursive version of the Merge Sort Algorithm . Of course every recursive algorithm can be written in an iterative manner . So today I am going to present the bottom-up version of the same algorithm, written in a non-recursive fashion .

The main idea of the bottom-up merge sort is to sort the array in a sequence of passes . During each pass the array is divided into smaller sub-arrays of a pseudo-fixed size (step) . Initially step is 1, but the value increases with every pass, as every adjacent sub-arrays are merged, thus step doubles .

Example.:

0. We consider an array with size <= 1 sorted .
1. The array that needs to be sorted is A = { 5, 2, 1, 12, 2, 10, 4, 13, 5} . At this point step = 1 .
2. At the first iteration array A is divided into blocks of size step = 1 . The resulting blocks (sub-arrays) are {5}, {2}, {1}, {12}, {2}, {10}, {4}, {13}, {5} .
3. step *= 2, thus step is now 2 . At this point we have a collection of sorted sub-arrays (because their size is = 1) . We will group the sub-arrays one-by-one and we will start merging them . After the merge, the resulting sub-arrays are: {2, 5}, {1,12}, {2,10}, {4, 13} and {5} . {5} remains unpaired as the array size is an odd number . We will take care of this block later .
4. step *= 2, thus step is now 4 . Now we have a collection of 4 blocks of size two and one block of size one . We will start to merge again the adjacent blocks, so the sub-arrays collection becomes: {1, 2, 5, 12}, {2, 4, 10, 13} and {5} .
5. step *= 2, thus step is now 8 . Now we have a collection of 2 blocks with size 4 and one block with size 1 . We will merge the adjacent blocks so the sub-arrays collection becomes {1, 2, 2, 4, 5, 10, 12, 13} and {5} .
6. We now have two blocks one of size 8 and one of size 1 . We will merge those blocks and obtain the resulting sorted array: {1, 2, 2, 4, 5, 5, 10, 12, 13} .

The pseudo code for the algorithm can be written as follows . We will start by writing the merge function . This is responsible with the merging of two already sorted blocks (sub-arrays) from a given array . The input parameters for this function are : the array itself, and the interval headers (stop, start) for the two already sorted blocks . The sentinel is a concept that simplifies the code . In our case we consider SENTINEL infinity (no value from the array is bigger or equal to the Sentinel) .

FUNCTION MERGE(A, startL, stopL, startR, stopR)
    /* The leftArray is defined as containing all the elements from
    startL to stopL of A + a sentinel value */
    LEFTL := [[A[llim]..A[mlim]) + SENTINEL]

    /* The right array is defined as containing all the elements from
    startR to stopR A + a sentinel value */
    RIGHTL := [[A[mlim]..A[rlim]) + SENTINEL]

    i := 0
    j := 0
    FOR k:=llim TO rlim DO
        IF LEFTL[i] <= RIGHTL[j] THEN
            A[k] = LEFTL[i]
            i := i + 1
        ELSE
            A[k] = RIGHTL[j]
            j := j + 1

And the actual function responsible with the actual merge can be written as follows:

FUNCTION MERGESORT(A, length)
  IF length < 2 THEN
    //RETURN - THE ARRAY IS ALREADY SORTED
    RETURN
  step := 1
  WHILE step < length DO
    startL := 0
    startR := step
    WHILE startR + step <= length DO
      MERGE(A, startL, startL + step, startR startR + step)
      startL := startR + step
      startR := startL + step
    IF startR < length THEN
      MERGE(A, startL, startL + step, startR, length)
    step := step * 2

Where A is the unsorted-but-soon-to-be-sorted array, length represents the size of A, step is the current size of the block, startL and startR represent the starting indexes of the sorted blocks that are going to be merged .

2. Algorithm implementation in Java

The merge sort algorithm (implementation in Java)

1. Description

In computer science many algorithms are recursive by nature and they usually follow an approach called divide-and-conquer . In this particular case dividing-and-conquering a problems means to break it into smaller identical sub-problems, resolve the smaller sub-problems recursively (by dividing the smaller sub-problems into even smaller problems), and eventually combine all their results to determine the solution for the initial problem .

The Merge Sort algorithm is based on this technique :

1. The merge sort algorithm works on arrays (or lists). If the array has its size <= 1, then we consider the array already sorted and no change is done . This is considered to be the limit condition of this recursive approach . [Limit Condition]
2. If size of the array (or list) > 1, then we divide the array into two equally-sized sub-arrays . [Divide] – O(1)
3. At this point we recursively sort both of the two arrays . [Conquer] 2*T*(n/2)
4. We merge the two sorted sub-arrays into one sorted array . [Merge] O(n)

We will start by defining the MERGE function . This is function is responsible with the merging of two sorted arrays. The resulting array (in our case portion of the initial array composed by the two merged sub-arrays) will be also sorted :

FUNCTION MERGE(L, llim, mlim, rlim)
  /* The leftArray is defined as containing all the elements from
  llim to mlim of L + a sentinel value */
  LEFTL := [[L[llim]..L[mlim]) + SENTINEL]

  /* The right array is defined as containing all the elements from
  mlim to rlim of L + a sentinel value */
  RIGHTL := [[L[mlim]..L[rlim]) + SENTINEL]

  i := 0
  j := 0
  FOR k:=llim TO rlim DO
    IF LEFTL[i] <= RIGHTL[j] THEN
      L[k] = LEFTL[i]
      i := i + 1
    ELSE
      L[k] = RIGHTL[j]
      j := j + 1

Where:

L The initial unsorted array .
llim The starting index of the left sub-array;
mlim The stopping index for right sub-array, and the starting index for the right sub-array;
rlim The stopping index for the right sub-array;
LEFTL, RIGHTL Additional helper arrays .
SENTINEL A value to simplify our code, there’s nothing “bigger” than the Sentinel .

After we define the MERGE function, the actual MERGE-SORT function can be written as:

MERGESORT(L, start, stop)
  IF start < stop THEN
    middle := (start + stop) / 2
    MERGESORT(L, start, middle)
    MERGESORT(L, middle + 1, stop)
    MERGE(L, start, middle, stop)

2. Java implementation

Sieve of Eratosthenes (finding all prime numbers up to a specific integer)

1. Algorithm Description

Sieve of Eratosthenes is an ancient algorithm in mathematics that allows us to find all prime numbers up to a specific integer value . It works well on small inputs (the maximum value of the interval is 10.000.000 – 20.000.000 ) .

I am not going to enter into too many details, as the algorithm itself is not very complicated and there are plenty resources on the web describing the concept of a sieve in general and the Eratosthenes Sieve in particular . Still I will implement this algorithm, for the sake of having a “complete” (far from the truth) reference on algorithms and data-structures .

The algorithm is based on the following technique:

1. Create an array S of integers with size N (the maximum value of the interval). Mark all positions in the array as possible primes .
2. Start iterating the array from position 2 (the first prime number), and mark every multiple of 2 as non-prime: S[2*2], S[2*3], …
3. Find the next non-prime number (that wasn’t previously marked), in our case 3, and continue to mark as non-prime all its multiples: S[3*2], S[3*3], …
4. Find the next non-prime number (that wasn’t previously marked), in our case 5, and continue to mark as non-prime all its multiples: S[5*2], S[5*3], …
5. Repeat the logic, and stop when the next non-prime number, k, satisfies the following relationship k*k > p .

Sieve of Eratosthenes pseudo-code:

FUNCTION SIEVE(max)
  sieve := ARRAY[2..max]
  FOR elem IN sieve
    elem := PRIME
  i := 2
  WHILE i * i < max DO
    IF sieve[i] = PRIME THEN
      j := 2
      WHILE j * i < max DO
        sieve[i * j] := NON-PRIME
          j := j + 1
    i := i + 1
  RETURN sieve

2. Algorithm Implementation

Serialize java objects using GZip streams (GZIPInputStream and GZIPOutputStream)

The process of converting an object into an associated sequence of bits, so that we can store it in a file, a memory buffer or share it across a network, with the sole purpose of later resurrecting it, is called Serialization Wikipedia offers a nice insight of what serialization is, so if you have time, please check this article . If this is the first time you hear about this concept you can check the official java documentation on this topic .

Recently I had to write a Serialization mechanism for a hobby application of mine . I had some very big objects (graphs represented as matrices) that had to be somehow stored as files for later usage . Serialization is not hard in Java, but the results are not always satisfactory . For example every graph object was using around 100M of my free and precious hdd space … and space is always an issue on my “workspace” partition (probably because I start so many “projects” and I never finish them) .

The work-around for this issue is relatively simple, instead of using a simple FileOutputStream / FileInputStream in conjunction with an ObjectOutputStream / ObjectInputStream we would better “wrap” the initial streams through a GZIPOutputStream / GZIPInputStream, and serialize the big objects as gzip files . The results are better than I expected, as the space consumption was reduced dramatically (3 or 4 times less space) . In my case the additional runtime for zipping / unzipping the objects before reading / writing them is not a problem, but note that because of the additional stream encapsulation (the GZIP streams), a time penalty appears .

To better demonstrate what I was saying I will start by designing a class that generates “very large objects” . The objects must support serialization, so our class implements java.io.Serializable . This is a “marker interface” and does not contain any methods that need to be implemented .

import java.io.Serializable;

/**
* A dumb class that is generating  not very large, but decently
* large java objects .
*
* @author Andrei Ciobanu
* @date 3 DEC, 2010
*/
public class VeryLargeObject implements Serializable {
  public static final int SIZE = 1 << 12;

  public String tag;
  public int[][] bigOne = new int[SIZE][SIZE];

  {
    // Initialize bigOne
    for(int i = 0; i < SIZE ; ++i) {
      for(int j = 0; j < SIZE; ++j) {
        bigOne[i][j] = (int) (Math.random() * 100);
      }
    }
  }

  public VeryLargeObject(String tag) {
    this.tag = tag;
  }
}

The VeryLargeObject class (not a recommended name for a class) encapsulates a bi-dimensional array of size [1 << 12][1 << 12] . That means the array has 4096 * 4096 elements = 1 << 24 elements = 16777216 elements (I believe it consumes enough memory to prove the concept) . The second step is to build an util class that contains the functions necessary for serialization / de serialization . For comparing the two strategies, I had to write two pair of functions [saveObject(…), loadObject(…)] and [saveGZipObject(…), loadGZipObject(…)] . The big difference between the two pairs is that the second use additional

Binary GCD (Stein’s Algorithm) in C

1. Algorithm Description

Binary GCD also known as Stein’s Algorithm is an algorithm that computes the greatest common divisor of two (positive) numbers . Discovered in 1967 by the Israeli programmer Josef Stein, it’s an alternative to the classical Euclid’s Algorithm, and is considered to be more efficient than this as it’s replacing divisions and multiplications with bitwise operations . The algorithm is recursive by nature, but loops can be used instead of recursion .

The algorithm can be described by the following rules (here and here) . Note that by B_GCD we will refer to a function that returns the greatest common divisor of two positive numbers .

1. B_GCD(0, 0) is not defined, but for convenience we will consider it 0 (zero), so B_GCD(0,0) = 0 ;
2. B_GCD(num1, 0) = num1 and B_GCD(0, num2) = num2 . The reason for this is beacuse zero is divided by everything ;
3. If num1 and num2 are even, B_GCD(num1, num2) = 2 * B_GCD(num1/2, num2/2), as 2 is a common divisor .
4. If num1 is even and num2 is odd, B_GCD(num1, num2) = B_GCD(num1 /2, num2), as 2 is not a common divisor . The steps are the same if num1 is odd and num2 is even : B_GCD(num1, num2) = B_GCD(num1, num2/2) .
5. If both num1 and num2 are odd, then if num1 >= num2 the B_GCD(num1, num2) = B_GCD((num1-num2)/2, num2), else B_GCD(num1, num2) = B_GCD((num2-num1)/2, num1) .
6. Step 4 and 5 are repeated until num1 = num2, or num1 = 0 .

We can also use pseudo code to describe the above algorithm .

Recursive Version of Binary GCD (Stein Algorithm)

FUNCTION  B_GCD(num1, num2)
  IF num1 = num2 THEN
    RETURN num1
  IF num1 = 0 AND num2 = 0 THEN
    RETURN 0
  IF num1 = 0 THEN
    RETURN num2
  IF num2 = 0 THEN
    RETURN num1
  IF num1 IS EVEN AND num2 IS EVEN THEN
    RETURN (B_GCD(num1/2, num2/2) * 2)
  IF num1 IS EVEN AND num2 IS ODD THEN
    RETURN B_GCD(num1/2, num2)
  IF num1 IS ODD AND num2 IS EVEN THEN
    RETURN B_GCD(num1, num2/2)
  IF num1 IS ODD AND num2 IS ODD THEN
    IF num1 >= num2 THEN
      RETURN B_GCD((num1-num2)/2, num2)
    ELSE
      RETURN B_GCD((num2-num1)/2, num1)

The loop-version of the Binary GCD Algorithm

FUNCTION B_GCD(num1, num2)
  power_of_two := 0
  IF (num1 = 0 OR num2 = 0) THEN
    RETURN num1 | num2
  WHILE ((num1 IS EVEN) AND (num2 IS EVEN))
    num1 := num1 / 2
    num2 := num2 / 2
    power_of_two := power_of_two + 1
  DO
    WHILE(num1 IS EVEN)
      num1 := num1 / 2
    WHILE(num2 IS EVEN)
      num2 := num2 / 2
    IF (num1 >= num2) THEN
      num1 := (num1 - num2) / 2
    ELSE
      tmp  := num1
      num1 := (num2 - num1) / 2
      num2 := tmp
  WHILE NOT ((num1 = num2) OR (num1 = 0))
  RETURN num2 * power_of_two

Euclid’s Algorithm: Reducing fraction to lowest terms

In the last article I’ve described Euclid’s algorithm for finding the greatest common divisor of two given numbers .A simple programming exercise I found in the book called “Algorithms in C” (Sedgewick) asks us to reduce a given fraction to lowest terms, using the Euclid’s Algorithm .

Eg.
Fraction = 36 / 120
Fraction = Reduce(Fraction) = 3 / 12

1. C Implementation

Step 1:

We will start by defining the data-structure we will use for encapsulating the fraction information (numerator and denominator):

/**
* Fraction data-structure:
* f = numerator / denominator
*/
typedef struct s_fraction {
  int numerator;
  int denominator;
} Fraction;

Step 2:

Usually when we play with C structures we should have two functions, for allocating and de-allocating memory associated with a structure (if you have an object-oriented background, this step will be equivalent with writing a constructor / destructor pair ) .

/**
* Allocates memory for a fraction structure .
* Initialize fraction structure .
* @param numerator
* @param denominator
* @return A pointer to the fraction structure on heap . (memmory should
be de-allocated manually)
*/
Fraction *fraction_new(int numerator, int denominator)
{
  Fraction *f = NULL;
  if (!denominator) {
    fprintf(stderr, "Invalid fraction. Denominator cannot be 0 (zero).n");
    return (f);
  }
  f = malloc(sizeof(*f));
  if (!f) {
    MALLOC_FAIL;
  }
  f->numerator = numerator;
  f->denominator = denominator;
  return (f);
}

/**
* De-allocates the memory associated with a given fraction .
* @param f The fraction to be free'd .
*/
void fraction_delete(Fraction *f)
{
  if (f) {
    free(f);
  }
}

An important aspect is that the fraction_new() function fails if a 0 (zero) denominator is given .

Step 3:

On this step we will write a function that reduces the fraction to lowest terms . For this we will also need to determine the greatest common divisor of the fraction’s denominator and numerator in order to divide the fraction

Euclid’s Algorithm

Recently I’ve started to implement (or reimplement) the most common algorithms a software developer should know . One of the nicest books I found on this topic is Algorithms in C (Robert Sedgewick) . Of course, there is this and this, but lately I am more interested on the “implementation” side of things than on maths and theory .

1. Algorithm Description

Euclid’s Algorithm is an efficient method for calculating the greatest common divisor of two numbers (aka GCD) . The  GCD of two numbers is considered the largest number that divides both of them (without leaving a reminder) .

Euclid’s algorithm is based on the principle that given two numbers a and b, if a is greater than b than the greatest common divisor of a and b is the same with the common divisor of b and (b – a) . If we transform the above property into “code” (actually pseudo-code) the algorithm looks like this:

FUNCTION GCD(num1, num2)
  WHILE num1 > 0
    IF num1 < num2
      SWAP (num1, num2)
    num1 := num1 - num2
  RETURN num2

The above pseudo-code is called the subtraction-variant . We can of course replace the repetitive subtractions with one division . The division-based version looks like this (in pseudo-code):

FUNCTION GCD(num1, num2)
  WHILE num1 > 0
    tmp  := num1
    num1 := num2 MOD num1
    num2 := tmp
  RETURN num2

There is also a recursive version of the algorithm:

FUNCTION GCD(num1, num2)
  IF num1 <> 0 THEN
    RETURN GCD(num2 MOD num1, num1)
  RETURN num2