241 Different Ways to Add Parentheses（C代碼版）

這道題有點像矩陣連乘問題

主要參考http://blog.csdn.net/pointbreak1/article/details/47315357的java版的代碼

public class Solution {  
    public List<Integer> diffWaysToCompute(String input) {  
        List<Integer> result = new ArrayList<Integer>();  
        int val = , index = ;  
        while(index < input.length() && Character.isDigit(input.charAt(index))) {  
            val *= ;  
            val += input.charAt(index++) - '0';  
        }  
        if(index == input.length()) {  
            result.add(val);  
            return result;  
        }  

        for(int i = ; i < input.length(); i++) {  
            if(!Character.isDigit(input.charAt(i))) {  
                List<Integer> left = diffWaysToCompute(input.substring(, i));  
                List<Integer> right = diffWaysToCompute(input.substring(i+, input.length()));  
                for(int j = ; j < left.size(); j++) {  
                    for(int k = ; k < right.size(); k++) {  
                        result.add(compute(left.get(j), right.get(k), input.charAt(i)));  
                    }  
                }  
            }  
        }  
        return result;  
    }  

    int compute(int a, int b, char op) {  
        switch(op) {  
            case '+': return a + b;  
            case '-': return a - b;  
            case '*': return a * b;  
            default: return ;  
        }  
    }  
}  
           

自己實作的C代碼如圖所示

#include<stdbool.h>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int cmp(const void* i,const void* j){
    int* a = (int *) i ;
    int* b = (int *) j ;
    if(*a>*b)
        return  ;
    if(*a<*b)
        return - ;
    return  ;
}
bool isdigital(char symbol){
    if(symbol>='0'&&symbol<='9'){
        return true ;
    }
    return false ;
}

bool computeTerminate(char* input){
    int length = strlen(input) ;
    for(int i=;i<length;i++){
        if(!isdigital(input[i]))
            return false ;
    }
    return true ;
}

char* subString(char* input,int start ,int end){
    char* temp = (char*)malloc(sizeof(char)*(end-start+)) ;
    for(int i=;i<(end-start);i++){
        temp[i] = input[start+i] ;
    }
    temp[end-start] = '\0' ;
    return temp ;
}

int computeResult(int a,int b,char op){
    switch(op){
        case '+': return a+b ;
        case '-': return a-b ;
        case '*': return a*b ;
    }
}

//左右遞歸，終止條件隻包含一個數，不包含符号時
int* diffWaysToCompute(char* input,int* returnSize){
    //隻包含了一個數
    if(computeTerminate(input)){    
//      result[*returnSize] = atoi(input) ;
//      (*returnSize)++ ;
//      return result ; 
        int* result = (int *)malloc(sizeof(int)*) ;
        result[] = atoi(input) ;
                *returnSize =  ;
                return result ;
    }

    int* result = (int *)malloc(sizeof(int)*) ;
    for(int i=;i<strlen(input);i++){
        if(!isdigital(input[i])){
            int lSize =  ;
            int RSize =  ;
            char* left = subString(input,,i) ;
            char* right = subString(input,i+,strlen(input)) ;
            int* l = diffWaysToCompute(left,&lSize) ;
            int* r = diffWaysToCompute(right,&RSize) ;
            for(int j=;j<lSize;j++)
                for(int k=;k<RSize;k++){
                    result[*returnSize] = computeResult(l[j],r[k],input[i]) ;
                    (*returnSize)++ ;
                }
        }
    }
    int* temp = (int*)malloc(sizeof(int)*(*returnSize-)) ;
    for(int i=;i<*returnSize;i++){
        temp[i] = result[i] ;
    }
    free(result) ;
    //釋放result所指向的空間----告訴系統，這個空間可以被重新配置設定了。此時result本身的值（即所指向的空間不變）
    //是以為了保證指針的安全性，通常都會在free(result);之後緊跟一句result=NULL,避免result再次操作到原來的空間。
    result = NULL ;
    return temp ;   
}

int main(void){
    char array[] = "1-2+3*4-5*6-7+8*9" ; 
    int returnSize =  ;
    int* result = NULL ;
    result = diffWaysToCompute(array,&returnSize) ;
    qsort(result,returnSize,sizeof(int),cmp) ;
    for(int i=;i<returnSize;i++){
        printf("%d ",result[i]) ;
    }
    printf("\n") ;
    return  ;
}