CareerCup

Here is my solution. I didn't find any case which is not covered by the below solution.
Will be waiting to get some testcases where this approach fails.
Below one is the perfect java code, you can place it in main and change the input string to the testcase and can be executed.

String input = "xxxxx";
		int xs = 0;
		int noOfReplaces = 0;
		int noOfdeletes = 0;
		int noOfInserts = 0;
		for (int i = 0; i < input.length(); i++) {
			if (input.charAt(i) == 'x')
				xs++;
			else {
				if (xs > 1) {
					xs--;
				} else if (xs == 1) {
					if (noOfdeletes > 0) {
						noOfReplaces++;
						noOfdeletes--;
					} else {
						// If this is last {
						if (i == input.length() - 1) {
							// Add one x at first
							noOfInserts++;
						} else {
							noOfdeletes++;
						}
					}
				} else {
					if (noOfdeletes > 1) {
						// As the 2 deletes can be replcaced with xs
						noOfdeletes = noOfdeletes - 2;
						noOfReplaces = noOfReplaces + 2;
					} else {
						noOfdeletes++;
					}
				}
			}

		}
		while (xs > 1) {
			if (xs > 2) {
				// Replace one x with *
				noOfReplaces++;
				xs = xs - 2;
			}
			if (xs == 2) {
				// Add one * at last
				noOfInserts++;
				xs--;
			}

		}
		
		System.out.println("deletes:" + noOfdeletes);
		System.out.println("insersts:" + noOfInserts);
		System.out.println("replaces:" + noOfReplaces);
		System.out.println("total:" + (noOfdeletes+ noOfReplaces + noOfInserts));

int FixExpressionOpCount(string expression)
{
    // Check for null and emptu
    if (expression == null || expression == '') return 0;

    // If the expression contains only one operand, there is nothing to fix
    if (expression.length <= 1) return 0;
    
    // Reudce a valid subexpression to an operand
    string reducedExpression = expression.replace('xx*', 'x');
    
    // if there was a valid sub-expression, this would have got reduced.
    if (reducedExpression.length < expression.length)
        return FixExpressionOpCount(reducedExpression);

    // If no reduction happened, get the number of times the operator '*' appears.
    // Each of these operators will need to be deleted and inserted to the end (i.e. 2 operations).
    return getCharCount(expression, '*') * 2;
}

int getCharCount(string str, char toFind)
{
    int count = 0;
    foreach (c in str)
        if (c == toFind) count++;

    return count;
}

This seems to work. An evaluation stack is sufficient.

import java.util.Scanner;

class RPN {
	public static void main(String[] args) {
		RPN rpn = new RPN();
		Scanner scanner = new Scanner(System.in);
		int numLines = scanner.nextInt();
		for(int i = 0; i < numLines; ++i) {
			System.out.println(rpn.processExpression(scanner.next()));
		}
	}

	private int processExpression(String expression) {
		int length = expression.length();
		if(length == 0) {
			return 0;
		}
		int change = 0;
		int stackOperandCount = 0;
		for(int i = 0; i < length; ++i) {
			if(expression.charAt(i) == 'x') {
				stackOperandCount = stackOperandCount + 1;
			} else {
				if(stackOperandCount > 1) {
					stackOperandCount = stackOperandCount - 1;
				} else {
					change = change + 1;
				}
			}
		}
		if(stackOperandCount != 0) {
			change = change + stackOperandCount - 1;
		}
		return change;
	}
}

I just remember binary tree, using different traverse method. But can't remember the detail

A binary tree having the leaves as the numerical value and the nodes as the binary operation, traversing such a tree in post order traversal results in a RPN expression.
For the given question, the number of operations would be the number of times, a value cannot be entered into the tree, and is inserted later, i.e 2 operations for every such value.
The value can or cannot be inserted is based on if the value is an operand then it should be added at the node, else it should be added at the leaf. If there end result is not a binary tree then the input sequence cannot be converted to RPN.

This is similar to the famous edit distance problem..

My suggestion: Simply go through the string and count x's and stars. When 'x' found, simply increase x-count. When star found, then: if there are at least 2 x's on the stack, decrease x count by one (because two x's and one star produced one x), otherwise inc error count by one (there might be two cases: x = 0 or x = 1, both solved by one operation: when no x, delete the star; when 1 x, add another and together with star we're ok).
Finally, add to errors all stars (needed to be deleted) and x's/2 (for each 2 x's one star insert).

Long story short (C#):
private int PolishErrors(string s)
{
int x = 0;
int o = 0;
int err = 0;

foreach(char c in s)
{
if (c == 'x') ++x;
else
{
if (x >= 2)
{
x-=1;
}
else
{
err++;
}
}

}

err += x/2 + o;

return err;
}

import java.io.*;
    
public class Solution {

    public static void main(String[] args) throws IOException {
        int step = test("xxx*");
        System.out.println(step);
    }
    
    public static int test(String s) {
        int step = 0;
        int operands = 0;
        
        while(s.indexOf("xx*") == 0 || s.indexOf("*x*") == 0 ||
        		s.indexOf("x**") == 0 || s.indexOf("*xx") == 0 ||
        		s.indexOf("**x") == 0 || s.indexOf("x*x") == 0 
        		|| s.indexOf("***") == 0) {
        
	        if (s.indexOf("xx*") == 0) {
	        	s = s.replaceFirst("xx\\*", "x");
	        	continue;
	        }
	        
	        if (s.indexOf("*x*") == 0) {
	        	s = s.replaceFirst("\\*x\\*", "x");
	        	step++;
	        	continue;
	        }
	        
	        if (s.indexOf("x**") == 0) {
	        	s = s.replaceFirst("x\\*\\*", "x");
	        	step++;
	        	continue;
	        }
	        
	        if (s.indexOf("x*x") == 0) {
	        	s = s.replaceFirst("x\\*x", "xx");
	        	step+=1;
	        	continue;
	        }
	        
	        if (s.indexOf("*xx") == 0) {
	        	s = s.replaceFirst("\\*xx", "xx");
	        	step+=1;
	        	continue;
	        }
	        
	        if (s.indexOf("**x") == 0) {
	        	s = s.replaceFirst("\\*\\*x", "x");
	        	step+=2;
	        	continue;
	        }
	        
	        if (s.indexOf("***") == 0) {
	        	s = s.replaceFirst("\\*\\*\\*", "x");
	        	step+=2;
	        	continue;
	        }
        }
        
        for(int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            if (c != 'x') {
            	if (operands == 0) {
            		step ++; //delete
            	} else if (operands == 1) {
            		step ++; //delete
            	} else {
            		operands--;
            	}
            } else {
                operands++;
            }
        }
        
        if (operands >= 2) {
            step += (operands - 2 > 0) ? (operands - 2) : 1;
        }
        
        return step;
    }
}

import java.io.*;
    
public class Solution {

    public static void main(String[] args) throws IOException {
        int step = test("xxx*");
        System.out.println(step);
    }
    
    public static int test(String s) {
        int step = 0;
        int operands = 0;
        
        while(s.indexOf("xx*") == 0 || s.indexOf("*x*") == 0 ||
        		s.indexOf("x**") == 0 || s.indexOf("*xx") == 0 ||
        		s.indexOf("**x") == 0 || s.indexOf("x*x") == 0 
        		|| s.indexOf("***") == 0) {
        
	        if (s.indexOf("xx*") == 0) {
	        	s = s.replaceFirst("xx\\*", "x");
	        	continue;
	        }
	        
	        if (s.indexOf("*x*") == 0) {
	        	s = s.replaceFirst("\\*x\\*", "x");
	        	step++;
	        	continue;
	        }
	        
	        if (s.indexOf("x**") == 0) {
	        	s = s.replaceFirst("x\\*\\*", "x");
	        	step++;
	        	continue;
	        }
	        
	        if (s.indexOf("x*x") == 0) {
	        	s = s.replaceFirst("x\\*x", "xx");
	        	step+=1;
	        	continue;
	        }
	        
	        if (s.indexOf("*xx") == 0) {
	        	s = s.replaceFirst("\\*xx", "xx");
	        	step+=1;
	        	continue;
	        }
	        
	        if (s.indexOf("**x") == 0) {
	        	s = s.replaceFirst("\\*\\*x", "x");
	        	step+=2;
	        	continue;
	        }
	        
	        if (s.indexOf("***") == 0) {
	        	s = s.replaceFirst("\\*\\*\\*", "x");
	        	step+=2;
	        	continue;
	        }
        }
        
        for(int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            if (c != 'x') {
            	if (operands == 0) {
            		step ++; //delete
            	} else if (operands == 1) {
            		step ++; //delete
            	} else {
            		operands--;
            	}
            } else {
                operands++;
            }
        }
        
        if (operands >= 2) {
            step += (operands - 2 > 0) ? (operands - 2) : 1;
        }
        
        return step;
    }
}

#define MAX 100

int validRPN(char *s)
{
    int n=strlen(s),i,res=0,counter=0;
    for(i=0;i<n;i++)
        if(s[i]=='x')
            counter++;
        else
        {
            if(counter>1)
                counter--;
            else
                res++;
        }
    while(counter>1)
    {
        res++;
        counter--;
    }
    return res;
}

void RPN()
{
    char s[MAX];
    gets(s);
    int t=atoi(s);
    while(t>0)
    {
        gets(s);
        printf("%d\n",validRPN(s));
        t--;
    }
}

a valid RPN should have n operands with n-1 operators, and at every postion i of the RPN, Num of operands from the 0 to i should always be larger than num of operators from 0 to i.
So we can first count the number of operands and operators, if num(operands) < num(operators) +1, start from the beginning flip num(operators) +1 - num(operands) of operators to operands. else if num(operands) > num(operators) +1, start from the end flip num(operands) -1 - num(operators) of operands to operators.

Then start validate the RPN, loop from beginning to end, at every step validate if num(operands) == num(operators) +1. If not, fix by flipping(between operand and operator), while maintain num(operands) == num(operators) +1.

this should be able to generate a valid RPN, but may not be least steps

public class RPN {
	
	public static boolean isValidRPN(String expr){
		
		char arr[] = expr.toCharArray();
		int x = 0;
		
		for(char c: arr){
			
			if ( c == 'x'){
				x++;
			}
			else if ( c == '*'){
				
				if ( x >= 2){
					x--;
				}
				else {
					return false;
				}
			}
		}
		
		if ( x == 1){
			return true;
		}
		
		return false;
	}
	
	//Think of RPN recursively as x(RPN)*
	//The remaining code is self explanatory
	private static int computeToRPN(String expr){
		
		int length = expr.length();
		
		if ( length == 1 ){
		   if (expr.equals("x")){
			   return 0;
		   }
		   else if ( expr.equals("*")){
			   return 1;
		   }
		}
		
		if ( length == 2){
			
			if ( expr.equals("xx") || expr.equals("*x") || expr.equals("x*")){
				return 1;
			}
			else if ( expr.equals("**")){
				return 2;
			}
		}
		
	    char startChar = expr.charAt(0);
	    char endChar = expr.charAt(expr.length()-1);
	    
	    if ( startChar == 'x' ){
	    	
	    	if ( endChar == 'x'){
	    		return 1 + compute2RPN(expr.substring(1,length-1));
	    	}
	    	else if ( endChar == '*'){
	    		return compute2RPN(expr.substring(1,length-1));
	    	}
	    }
	    
	    return 2 + compute2RPN(expr.substring(1, length-1));
	    
	    
	}
	
	public static int compute2RPN(String expr){
		
		if ( isValidRPN(expr) ) return 0;
		else return computeToRPN(expr);
		
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(compute2RPN("xx*"));
		System.out.println(compute2RPN("xxx**"));
		System.out.println(compute2RPN("xxxx"));
		System.out.println(compute2RPN("*xx"));
		System.out.println(compute2RPN("xxxx*"));
		System.out.println(compute2RPN("**xx"));
		System.out.println(compute2RPN("xx*xx**"));

	}

}

Could you tell me what's wrong witht the following simple algorithm?

s := given string
stack st := empty
for each token t in s 
  if ( t is x)
    push t
  else
    if ( st is empty )
      delete t
    else if st has only one element
      add an 'x' and push it
      pop two 'x's and push one 'x' 
    else
      pop two 'x's and push one 'x'
    endif
endfor

while st is not empty
    if st has only one element
      add 'x' and pushs it 
    endif
    add a '*'
    pop two 'x's and push a 'x'
endwhile

This is actually very simple

int minOperations(string input)
	{
		int o = 0;
		int c = 0;
		for(int i=0; i<input.length(); i++)
		{
			if (input[i] == 'X')
			{
				c++;
			}
			else
			{
				if (c< 2)
				{
					o++; // remove '*'
				}
				else
				{
					o -= 1; // caculate new number XX* => X
				}
			}
		}
		return o + c-1;
	}

To be a valid RPN, there should be one operand in the stack (as the result of all previous operations).

t[i][k] = number of modifications on the substring of length k to get i operands in the stack
t[1][size-1] gives the answer.

* decreases the number of operands in the stack by one.
x increases the number of operands in the stack by one.

When we read a character at k, we have to decide if we should let it as it is, or if we should delete it, or insert x or insert *.

#include "string.h"
#include "stdio.h"
#include "limits.h"


int min_4(int a, int b, int c, int d){
    int m = a;
    if (b<m)
        m=b;
    if (c<m)
        m=c;
    if (d<m)
        m=d;
    return m;
}

int compute(const char *str){
    printf("%s\n", str);
    size_t size = strlen(str);
    int t[size+1][size];
    memset(t, INT_MAX, sizeof(int)*(size+1)*size);

    t[0][0] = 1;

    char first_char = str[0];
    for (int i=1; i<size+1; i++){
        t[i][0] = (first_char == '*') ? i : i-1;
    }
    for (int k=1; k<size; k++){
        char cur_char = str[k];
        for (int i=0; i<size; i++){
            if (cur_char == '*'){
                t[i][k] = min_4(
                    i+1 >= 2 ? (0 + t[i+1][k-1]) : INT_MAX,
                    i-1 >= 0 ? (1 + t[i-1][k-1]) : INT_MAX,
                               (1 + t[i  ][k-1])          ,
                    i+2 >= 2 ? (1 + t[i+2][k-1]) : INT_MAX 
                );
            } else if (cur_char == 'x'){
                t[i][k] = min_4(
                    i-1 >= 0 ? (0 + t[i-1][k-1]) : INT_MAX,
                    i+1 >= 2 ? (1 + t[i+1][k-1]) : INT_MAX,
                               (1 + t[i  ][k-1])          ,
                    i-2 >= 0 ? (1 + t[i-2][k-1]) : INT_MAX
                );
            }
        }
    }

    return t[1][size-1];
}


int main(){

    printf("result = %d\n", compute("xx*x**xx*x**x**xxx*xxx***x*x*x**xxx*xx**xxxxx**xxxxxx*x*xx*xxxx*xxx**x*xxxx**xxx*xx*xxx*xx"));
    printf("result = %d\n", compute("x"));
    printf("result = %d\n", compute("xx*"));
    printf("result = %d\n", compute("xxx**"));
    printf("result = %d\n", compute("*xx"));
    printf("result = %d\n", compute("xx*xx**"));


}

public class MinCostToValidRPN {

	
	public MinCostToValidRPN() {
	}

	final static char VALUE = 'x';
	final static char OPERATOR = '*';
	
	static int evaluate(String s){
		if(s == null){
			throw new IllegalArgumentException();
		}
		
		int n = s.length();
		char[] sc = s.toCharArray();
		
		int result = 0;
		
		// base case
		if(n == 0){
			result = 1;
		} else if (n == 1){
			if(sc[0] == VALUE){
				result = 0;
			} else {
				result = 1;
			}
		} else {
			
			int cost[][][] = new int[n][n][3];
			
			for(int i = 0; i < n; i++){
				for(int j = 0; j < n; j++){
					cost[i][j][0] = j-i+1;
					cost[i][j][1] = j-i+1;
					cost[i][j][2] = j-i+1;
				}
			}
			
			// fill diagonal
			for(int i = 0; i < n; i++){
				char c = sc[i];
				if(c == VALUE){
					cost[i][i][0] = 0;
					cost[i][i][1] = 1;
					cost[i][i][2] = 1;
				} else {
					cost[i][i][0] = 1;
					cost[i][i][1] = 0;
					cost[i][i][2] = 1;
				}
			}
			
			// compose solution for larger span
			for(int length = 2; length < n; length++){
				for(int i = 0; i < n-length; i++){
					helper(sc, cost,i,i+length);
				}
			}
			
			result = cost[0][n-1][0];
		}
		
		return result;
	}
	
	/**
	 * start at i end at j-1
	 */
	  private static void helper(char[] sc, int[][][] cost, int i, int j) {
		  // base - delete until left with X
		  boolean containsValue = false;
		  for(int k = i; k < j; k++){
			  if(sc[k] == VALUE){
				  containsValue = true;
				  break;
			  }
		  }
		  
		  int y = j - i + 1;
		  if(containsValue){
			  y = y-1;
		  }
		  
		for(int k = i-1; k<j-1; k++){
			for(int l = k+1; l<j; l++){
				int c1 = 1;
				if(k>=i){
					c1 = cost[i][k][0];
				}
				
				int c2 = cost[k+1][l][0];
				
				int c3 = 1;
				if(l+1 <=j ){
					c3 = cost[l+1][j][1];
				}
				
				if(c1+c2+c3<y){
					y = c1+c2+c3;
				}
			}
		}
		
		boolean containsOp = false;
		  for(int k = i; k < j; k++){
			  if(sc[k] == OPERATOR){
				  containsOp = true;
				  break;
			  }
		  }
		  
		  int z = j-i+1;
		  if(containsOp){
			  z = z-1;
		  }
		
		  cost[i][j][0] = y;
		  cost[i][j][1] = z;
	}

	public static void main(String[] args){
		   MinCostToValidRPN wrapper = new MinCostToValidRPN();
		   String[] testcase = { "x" , "*" , "xxx**" , "*xx" };
		   
		   for(String s : testcase){
			   System.out.println(s);
			   int c = wrapper.evaluate(s);
			   System.out.println("cost " + c);
		   }
	   }
}

Isnt this problem is just about pushing *'s after X's. which can be done in O(n) time using standard two pointer method ?. can somebody give an example where result produced by this method is not the minimum ?

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <string>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
//---------- macros ----------
#define fp(i,a,b) for(int i=a; i<b; i++)
#define fm(i,a,b) for(int i=a; i>b; i--)

using namespace std;

string reduce(string s)
{
int n = s.length();
for(int i=0; i < n; i++)
if (s[i]=='*')
{
if(i>=2 && s[i-1]=='x' && s[i-2]=='x'){ s.erase(i-1,2);
i=i-2; }
}
return s;
}

int main()
{
int n;
cin >> n;
while(n--)
{
string s;
cin >> s;
int c = 0;
s=reduce(s);
while(s!="x")
{
int firstStar = (int)s.find('*');
if(s.size()==2)
{
if(s=="**")
c = c+2;
else // "x*", "*x", "xx"
c++;
s = "x";
}
else
{
if(firstStar>=0)
{
if((int)s.find('x')<0) // all *'s
{
c = c+s.size()/2+1;
s = "x";
}
else
{
c++;
s[firstStar]= 'x';
}
}
else // all x's replace 1/2 by *.. if odd replace delete last one
{
c = c+s.size()/2;
s = "x";
}
if(s!="x")
s=reduce(s);
}
}
cout << c << endl;
}




//-----------------------------
cout << endl;
// system("pause");
return 0;
}

We define
S[i][j] to be the minimum number of operations required to convert substring a[i] .. a[j] into RPN.

Now we have the following recursive formulation of S[i][j]

S[i][j] =
min { (0, if i == j & a[i] is an operand),
          (1, if i == j & a[i] is an operator [either delete it or replace with operand, both have same cost, if they would have been different we would have chosen the minimum]),
          (S[i][j-1] + 1,  [just delete a[j] and convert a[i] .. a[j-1] into RPN]),
          (min_(i<=k<j-1){S[i][k] + S[k+1][j-1]},  if a[j] is an operator [if we convert S[i][k] and S[k+1][j-1] into RPN, and just use the operator a[j] we have a valid RPN, minimize over all such k]),
          min{
                  (min_(i<=k<j-1){S[i][k] + S[k+1][j-1]} + 1,  if a[j] is an operand [if we convert S[i][k] and S[k+1][j-1] into RPN, and convert a[j] into operator we have a valid RPN, minimize over all such k]),
                  (min_(i<=k<j){S[i][k] + S[k+1][j]} + 1,  if a[j] is an operand [if we convert S[i][k] and S[k+1][j] into RPN, and insert an operator we have a valid RPN, minimize over all such k])
                  }
        }

isn't it very simple???

int idx = 0, res = 0;
while (cin >> ch) if (ch == '*') {
     if (idx >= 2) idx -= 1; // remove two from stack top, then push a new one
     else if (idx == 0) res++; // nothing on the stack, remove '*', otherwise will need more moves
     else res++; // we can either add a 'x' or remove the '*', and either way won't affect the stack status.
} else idx++;
if (idx == 0)
    cout << res + 1;
else
    cout << res + idx - 1;

why every body is writing that long?