C code using DP.. not very pleasant coding experience..


  • 0
    M
    `int* diffWaysToCompute(char* input, int* returnSize) {
    int *result = NULL;
    int t;
    
    // read the input into two arrays: numbers and opers; 
    //for example "2-1" will be stored as numbers[] = {2, 1} and opers[] = {-};
    char ch, *opers = NULL;
    int j, i = 0, oldpos = 0, temp = 0, pivot = 0, size = 0;
    int *numbers = NULL;
    while ((ch = input[i]) != '\0') {
        if (ch == '+' || ch == '-' || ch == '*') {
            opers = (char *)realloc(opers, sizeof(char)*(pivot+1));
            numbers  = (int *)realloc(numbers, sizeof(int)*(pivot+1));
            opers[pivot] = ch;
            for (j=oldpos; j<i; j++)
                temp = 10*temp + input[j] - '0';
            numbers[pivot++] = temp;
            oldpos = i+1;
            temp = 0;
        }
        size++;
        i++;
    }
    for (j=oldpos; j<i; j++)
        temp = 10*temp + input[j] - '0';
    numbers = (int *)realloc(numbers, sizeof(int)*(pivot+1));
    numbers[pivot++] = temp;
    
    // if there is only one number, then return it
    if (pivot == 1) {
        *returnSize = 1;
        result = (int *)malloc(sizeof(int));
        *result = numbers[0];
        return result;
    }
    
    // DP part, bottom up solution; the base case is dp[i][i], where there is only one number; 
    //then the length changes from 2 to pivot; pivot is the # of numbers from the input
    //the result would be dp[0][pivot-1]
    int l, k, m, n;
    int *dp[pivot][pivot];
    int dps[pivot][pivot];   // this two dimensional array is to store the size of dp[i][j]
    
    for (i=0; i<pivot; i++) {
        dp[i][i] = (int *)malloc(sizeof(int));
        *dp[i][i] = numbers[i];
        dps[i][i] = 1;
    }
        
    for (l=2; l<pivot+1; l++)
        for (i=0; i<(pivot-l+1); i++) {
            t = 0;
            j = i+l-1;
            dp[i][j] = NULL;
            for (k=i; k<j; k++) {
                m = 0; n = 0;
                for (m=0; m<dps[i][k]; m++)
                    for (n=0; n<dps[k+1][j]; n++) {
                        dp[i][j] = (int *)realloc(dp[i][j], sizeof(int)*(t+1));
                        switch(opers[k]) {
                            case '+':
                                dp[i][j][t++] = dp[i][k][m] + dp[k+1][j][n];
                                break;
                            case '-':
                                dp[i][j][t++] = dp[i][k][m] - dp[k+1][j][n];
                                break;
                            case '*':
                                dp[i][j][t++] = dp[i][k][m] * dp[k+1][j][n];
                                break;
                        }
                    }
            }
            dps[i][j] = t;
        }
        *returnSize = t;
        return dp[0][pivot-1];
    

    }`


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.