## Friday, December 4, 2015

### Minimum edits required to generate reverse polish notation

http://www.careercup.com/question?id=5762415492857856

Imagine x is an operand and * is a binary operator. We say a string of x and * follows Reverse Polish notation if it is a postfix notation.

For example strings xx*, x, and xx*xx** follow Reverse Polish notation.

Given a string of x and *, how many insert, delete, and replace operations are needed to make the string follow the RPN.

For example, xx* need 0 operation to follow RPN since it already follows RPN.
x*x needs two operations to become xx* which follows RPN.
*xx* needs one operation to become xx* which follows RPN.

Your algorithm should work for a string of size up to 100.
public class MinimumEditForReversePolishNotation {

public int minimum(char input[]){
return minimum(input,0,0);
}

private int minimum(char input[],int pos,int countXs){
if(pos == input.length){
//we should be always be left with 1 x otherwise notation is incomplete
if(countXs > 1){
return Integer.MAX_VALUE;
}
return 0;
}
//if input is x we can have x as it is or delete it or convert it to *.
//So basically we try all those options below
//If input is * we can take 2 xs and conver it to one x. If we dont have
//2xs then we can either delete this * or convert it to x.
//Remember adding anything does not make any sense since deleting things
//can achieve same things unless cost of adding is different from deleting
if(input[pos] == 'x'){
int v1 = minimum(input,pos+1,countXs+1);
int v2 = Integer.MAX_VALUE;
if(countXs > 1){
v2 = minimum(input,pos+1,countXs-1);
v2 =( v2 != Integer.MAX_VALUE ? v2 + 1 : Integer.MAX_VALUE);
}
int v3 = minimum(input,pos+1,countXs);
v3 =( v3 != Integer.MAX_VALUE ? v3 + 1 : Integer.MAX_VALUE);
return Math.min(Math.min(v1,v2),v3);
}else{
if(countXs >= 2){
return minimum(input,pos+1,countXs-1);
}else{
int v1 = minimum(input,pos+1,countXs);
v1 = (v1 != Integer.MAX_VALUE ? v1 + 1 : Integer.MAX_VALUE);
int v2 = minimum(input,pos+1,countXs+1);
v2 =( v2 != Integer.MAX_VALUE ? v2 + 1 : Integer.MAX_VALUE);
return Math.min(v1, v2);
}
}
}
public static void main(String args[]){
MinimumEditForReversePolishNotation mef = new MinimumEditForReversePolishNotation();
System.out.println(mef.minimum("xxxx*x*x*".toCharArray()));
}
}