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

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