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.

/* Copyleft: Ming Lin <minggr@gmail.com> */ /* http://www.careercup.com/question?id=5762415492857856 */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <limits.h> #define MAX 300 int cache[MAX][MAX]; int postfix(char *expr, int i, int j) { char c = expr[j]; int min; int tmp; int k; if (cache[i][j] != -1) return cache[i][j]; if (i == j) { if (expr[i] == '*') { cache[i][j] = 1; return cache[i][j]; } else { cache[i][j] = 0; return cache[i][j]; } } // why need? if (i + 1 == j) { if (expr[i] == '*' && expr[j] == '*') { cache[i][j] = 2; return cache[i][j]; } if (expr[i] == '*' && expr[j] == 'X') { cache[i][j] = 1; return cache[i][j]; } if (expr[i] == 'X' && expr[j] == '*') { cache[i][j] = 1; return cache[i][j]; } if (expr[i] == 'X' && expr[j] == 'X') { cache[i][j] = 1; return cache[i][j]; } } min = INT_MAX; if (c == '*') { for (k = i; k <= j-2; k++) { tmp = postfix(expr, i, k) + postfix(expr, k+1, j-1); if (tmp < min) min = tmp; } } else { //replace 'X' with '*' for (k = i; k <= j-2; k++) { tmp = postfix(expr, i, k) + postfix(expr, k+1, j-1) + 1; if (tmp < min) min = tmp; } //delete 'X' tmp = postfix(expr, i, j-1) + 1; if (tmp < min) min = tmp; //add '*' for (k = i; k <= j-1; k++) { tmp = postfix(expr, i, k) + postfix(expr, k+1, j) + 1; if (tmp < min) min = tmp; } } cache[i][j] = min; return cache[i][j]; } void init_cache(void) { int i, j; for (i = 0; i < MAX; i++) for (j = 0; j < MAX; j++) cache[i][j] = -1; } int main() { char expr[MAX]; int j; init_cache(); while (1) { scanf("%s", expr); j = strlen(expr) - 1; printf("%d\n", postfix(expr, 0, j)); } return 0; }