Expression Evaluation

Infix, Postfix and Prefix notations are three different but equivalent ways of writing expressions. It is easiest to demonstrate the differences by looking at examples of operators that take two operands.


Infix notation: X + Y

Operators are written in-between their operands. This is the usual way we write expressions. An expression such as A * ( B + C ) / D is usually taken to mean something like: "First add B and C together, then multiply the result by A, then divide by D to give the final answer."

Infix notation needs extra information to make the order of evaluation of the operators clear: rules built into the language about operator precedence and associativity, and brackets ( ) to allow users to override these rules. For example, the usual rules for associativity say that we perform operations from left to right, so the multiplication by A is assumed to come before the division by D. Similarly, the usual rules for precedence say that we perform multiplication and division before we perform addition and subtraction

Postfix notation (also known as "Reverse Polish notation"): X Y +

Operators are written after their operands. The infix expression given above is equivalent to A B C + * D /
The order of evaluation of operators is always left-to-right, and brackets cannot be used to change this order. Because the "+" is to the left of the "*" in the example above, the addition must be performed before the multiplication.

Operators act on values immediately to the left of them. For example, the "+" above uses the "B" and "C". We can add (totally unnecessary) brackets to make this explicit:
( (A (B C +) *) D /)

Thus, the "*" uses the two values immediately preceding: "A", and the result of the addition. Similarly, the "/" uses the result of the multiplication and the "D".

Prefix notation (also known as "Polish notation"): + X Y

Operators are written before their operands. The expressions given above are equivalent to / * A + B C D
As for Postfix, operators are evaluated left-to-right and brackets are superfluous. Operators act on the two nearest values on the right. I have again added (totally unnecessary) brackets to make this clear:
(/ (* A (+ B C) ) D)

Examples

Infix	Postfix	Prefix	Notes
A * B + C / D	A B * C D / +	+ * A B / C D	multiply A and B, divide C by D, add the results
A * (B + C) / D	A B C + * D /	/ * A + B C D	add B and C, multiply by A, divide by D
A * (B + C / D)	A B C D / + *	* A + B / C D	divide C by D, add B, multiply by A

Converting between these notations

The most straightforward method is to start by inserting all the implicit brackets that show the order of evaluation e.g.:

Infix	Postfix	Prefix
( (A * B) + (C / D) )	( (A B *) (C D /) +)	(+ (* A B) (/ C D) )
((A * (B + C) ) / D)	( (A (B C +) *) D /)	(/ (* A (+ B C) ) D)
(A * (B + (C / D) ) )	(A (B (C D /) +) *)	(* A (+ B (/ C D) ) )

You can convert directly between these bracketed forms simply by moving the operator within the brackets e.g. (X + Y) or (X Y +) or (+ X Y). Repeat this for all the operators in an expression, and finally remove any superfluous brackets.

Infix to postfix

Suppose we have expression: 3 + 4 * 5 / 6

Element	Stack	Output
3		3
+	+	3
4	+	34
*	+*	34
5	+*	345
/	+/	345*
6	+/	345*6
	+	345*6/
		345*6/+

Code to convert infix to postfix:



Output:


Infix: (4+8)*(6-5)/((3-2)*(2+2))
Postfix: 48+65-*32-22+*/


Postfix Evaluator

Median of Medians Algorithm

Performance of quick sort depends on how we choose the pivot. If we choose the pivot as the median of the array then quick sort can run in O(n*logn) time.
In median of medians algorithm, we try to get something close to the median.

Median-of-medians algorithm:

• Line up elements in groups of five (this number 5 is not important, it could be e.g. 7 without changing the algorithm much). Call each group S[i], with i ranging from 1 to n/5.
• Find the median of each group. (Call this x[i]). This takes 6 comparisons per group, so 6n/5 total (it is linear time because we are taking medians of very small subsets).
• Find the median of the x[i], using a recursive call to the algorithm. If we write a recurrence in which T(n) is the time to run the algorithm on a list of n items, this step takes time T(n/5). Let M be this median of medians.
• Use M to partition the input and call the algorithm recursively on one of the partitions, just like in quickselect.

Code

// selects the median of medians in an array
int select(int *a, int s, int e, int k){
    // if the partition length is less than or equal to 5
    // we can sort and find the kth element of it
    // this way we can find the median of n/5 partitions
    if(e-s+1 <= 5){
        sort(a+s, a+e);
        return s+k-1;
    }
    
    // if array is bigger 
    // we partition the array in subarrays of size 5
    // no. of partitions = n/5 = (e+1)/5
    // iterate through each partition
    // and recursively calculate the median of all of them
    // and keep putting the medians in the starting of the array
    for(int i=0; i<(e+1)/5; i++){
        int left = 5*i;
        int right = left + 4;
        if(right > e) right = e;
        int median = select(a, 5*i, 5*i+4, 3);
        swap(a[median], a[i]);
    }
    
    // now we have array 
    // a[0] = median of 1st 5 sized partition
    // a[1] = median of 2nd 5 sized partition
    // and so on till n/5
    // to find out the median of these n/5 medians
    // we need to select the n/10th element of this set (i.e. middle of it)
    return select(a, 0, (e+1)/5, (e+1)/10);
}

int main(){
    int a[] = {6,7,8,1,2,3,4,5,9,10};
    int n = 10;
    
    int mom = select(a, 0, n-1, n/2);
    cout<<"Median of Medians: " << a[mom] << endl;
    return 0;
}

Hash Tables

A hash table is a data structure that provides very fast insertion and searching. No matter how many data items are insertion and searching can take close to constant time O(1).
One important concept is how a range of key values is transformed into a range of array index values. In a hash table, this is accomplished using hash function.


Key can be anything:

If keys are index numbers

Simple! store them in an array A[key] location.

What if keys are strings?
In this case, we can try converting words into integers using ASCII numbers.
1. We can add the digit values?
For example: cats = c(=3) + a(=1) + t(=20) + s(=19) = 43.
Thus in the hash table, the word cat would be stored at 43rd index.

How well this would work?
Suppose we have 10 letters word zzzzzzzzzz, then the value it would obtain is 26*10 = 260 That means total range of word indexes is from 1 to 260. But we have a million words in the dictionary.

Hashing

We need to compress the huge range of numbers into a range that matches a reasonably sized array.
We can do it using mod function:

smallRangeIndex = largeRangeIndex % smallRangeMax;

This would compress any number into (0 - smallRangeMax) range.

Collision We pay the price of squeezing the large numbers into a small range. Now multiple numbers can point to one index in the smaller range. This is called collision.

We have different methods to resolve collisions:

Open Addressing

In open addressing, when a data item can't be placed at an index calculated by hash function (because the place is already occupied!) another location in array is sought.
There are three methods to explore the new location:

1. Linear Probing
   

   When we have collision at ith index, increase the i by 1 and check (i+1)th location, if that is also occupied check at (i+2)th location and so on until you find an empty space.

   
   
2. Quadratic Probing
   

   Instead of increasing i by 1 every time, increase in power of two:
   First hit : increase by 1^2
   Second hit : increase by 2^2
   Third hit : increase by 3^3
   and so on

Code for linear probing

int search(int key)
{
    // calculate the hash value of the key
    int hash = hashfunction(key);
    while(hashtable[hash] != NULL){
 // if we find a key at "hash" index, return the stored value
 if(hashtable[hash] == key)
     return hashtable[hash];
 
 // otherwise, increase the hash linearly 
 hash++;
    }
    
    // return -1 if we do not find any such key in the hashtable.
    return -1;
}

void insert(int key)
{
    // calculate hash value of the key
    int hash = hashfunction(key);
    
    // if the location is already occupied increase the hash
    while(hashtable[hash] != NULL) {
 hash++;
    }
    
    hashtable[hash] = key;
}

Longest Common Substring

Given two strings s1 and s2. Find out the longest common substring.
Lets solve this problem using Dynamic Programming.
We assume a 2D matrix such that m[i][j] is the maximum length of LCS in substring s1[0..i] and s2[0..j].

Recursive formula to get the length of LCS:

m[i][j]  = 0 if(i==0, j==0)
         = m[i-1][j-1] + 1 if(s1[i] == s2[j])
         = max( m[i][j-1], m[i-1][j] ) if(s1[i] != s2[j])

Using this recursive formula m[s1.size()][s2.size()] will give the maximum length of the common substring.

Code to get the LCS matrix:

 int **getLCSMatrix(string s1, string s2) {
  int r = s1.size() + 1, c = s2.size() + 1;
  int **m = (int**) malloc(r * sizeof(int *));
  for (int i = 0; i < c; i++)
   m[i] = (int *) malloc(c * sizeof(int));

  for (int i = 0; i < r; i++)
   m[i][0] = 0;

  for (int i = 0; i < c; i++)
   m[0][i] = 0;

  for (int i = 1; i < r; i++) {
   for (int j = 1; j < c; j++) {
    if (s1[i - 1] == s2[j - 1]) {
     m[i][j] = m[i - 1][j - 1] + 1;
    } else {
     m[i][j] = max(m[i - 1][j], m[i][j - 1]);
    }
   }
  }
  return m;
 }

Now, we can easily use this matrix to get the maximum length.
Output:

LCS length: 3

Reading out an LCS:

The following code backtracks the choices taken when computing the LCS matrix. If the last characters in the prefixes are equal, they must be in an LCS. If not, check what gave the largest LCS of keeping s1[i] and s2[j], and make the same choice. Just choose one if they were equally long. Call the function with i=s1.size() and j=s2.size().

 string getLCS(int **m, int i, int j, string s1, string s2) {
  if (i == 0 || j == 0)
   return "";
  if (s1[i - 1] == s2[j - 1])
   return getLCS(m, i - 1, j - 1, s1, s2) + s1[i - 1];
  else if (m[i - 1][j] < m[i][j - 1])
   return getLCS(m, i, j - 1, s1, s2);
  else
   return getLCS(m, i - 1, j, s1, s2);
 }

Reading out all the LCS:

 set getAllLCS(int **m, int i, int j, string s1, string s2,
   string s) {
  set v;
  if (i == 0 || j == 0) {
   v.insert(s);
   return v;
  }

  if (s1[i - 1] == s2[j - 1]) {
   set v1 = getAllLCS(m, i - 1, j - 1, s1, s2, s1[i - 1] + s);
   v.insert(v1.begin(), v1.end());
  } else if (m[i - 1][j] == m[i][j - 1]) {
   set v1 = getAllLCS(m, i - 1, j, s1, s2, s);
   set v2 = getAllLCS(m, i, j - 1, s1, s2, s);
   v.insert(v1.begin(), v1.end());
   v.insert(v2.begin(), v2.end());
  } else if (m[i - 1][j] < m[i][j - 1]) {
   set v1 = getAllLCS(m, i, j - 1, s1, s2, s);
   v.insert(v1.begin(), v1.end());
  } else {
   set v1 = getAllLCS(m, i - 1, j, s1, s2, s);
   v.insert(v1.begin(), v1.end());
  }
  return v;
 }

You can find the complete source code on my github page: Here

Maximum Sub Matrix Sum

Given a matrix of both +ve and -ve numbers, find out the maximum sum sub matrix. First of all we will calculate the sum matrix where s[i][j] = sum of all the elements from [0,0] to [i,j]

int s[ROW][COL];
 void computeSumMatrix(int a[][COL], int r, int c) {
  for (int i = 0; i < r; i++)
   if (i == 0)
    s[i][0] = a[i][0];
   else
    s[i][0] = s[i - 1][0] + a[i][0];

  for (int j = 0; j < c; j++)
   if (j == 0)
    s[0][j] = a[0][j];
   else
    s[0][j] = s[0][j - 1] + a[0][j];

  for (int i = 1; i < r; i++) {
   for (int j = 1; j < c; j++) {
    s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
   }
  }
 }

Now we will write a method to get the sum of a sub matrix given upper-left (r1,c1) indexes and lower-bottom (r2,c2) indexes

int getSubmatSum(int r1, int c1, int r2, int c2) {
  if (r1 == 0 && c1 == 0)
   return s[r2][c2];
  if (r1 == 0)
   return s[r2][c2] - s[r2][c1 - 1];
  if (c1 == 0)
   return s[r2][c2] - s[r1 - 1][c2];
  return s[r2][c2] - s[r1 - 1][c2] - s[r2][c1 - 1] + s[r1 - 1][c1 - 1];
 }

Using both these methods, we can iterate through all the possible sub matrices and get their sum in O(1). To iterate though all the possible sub-matrices would take O(n^4).

int getMaxSubmatSum(int a[][COL], int r, int c) {
  int maxsum = 0;
  for (int r1 = 0; r1 < r; r1++) {
   for (int c1 = 0; c1 < c; c1++) {
    for (int r2 = r1; r2 < r; r2++) {
     for (int c2 = c1; c2 < c; c2++) {
      int sum = getSubmatSum(r1, c1, r2, c2);
      maxsum = max(sum, maxsum);
     }
    }
   }
  }
  return maxsum;
 }

Now, we are going to optimize this solution to O(n^3). The trick is to apply Kadane's algorithm on a 2D matrix. We will consider all the possible 2D matrices which are starting from 0th column and treat them as 1D arrays.

int getMaxSubmatSum2(int a[][COL], int r, int c) {
  int globalmax = 0;

  for (int i = 0; i < r; i++)
   for (int j = i; j < r; j++) {
    int localmax = 0;
    for (int k = 0; k < c; k++) {
     localmax = max(localmax + getSubmatSum(i, k, j, k), 0);
     globalmax = max(localmax, globalmax);
    }
   }

  return globalmax;
 }

Test Cases
Given Matrix:
1 1 1
1 1 1
1 1 1
Maximum Sum : 9 (because all numbers are positive, we will output complete matrix)

Given Matrix:
-1 -2 -3 -4
-5 -6 -7 -8
-9 -10 -11 -12
-13 -14 -15 -16
Maximum Sum : 0 ( we take nothing, as all numbers are negative)

Given Matrix:
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

Maximum Sum: 15
Output Matrix :
9 2
-4 1
-1 8

You can find the full source code of both these algorithms on my github page: Here