Divide and Conquer Solution


  • 0
    C
    vector<char> op_vec;
    vector<int> num_vec;
    
    int NUM(string::const_iterator &iter)
    {
        int result = 0;
        while('0'<=*iter && *iter<='9')
            result = result*10 + *(iter++)-'0';
        return result;
    }
    
    void Lexer(const string& input)
    {
        string::const_iterator iter = input.begin();
        
        num_vec.push_back( NUM(iter) );
        
        while(*iter)
        {
            op_vec.push_back(*iter++);
            num_vec.push_back( NUM(iter) );
        }
    }
    
    int basic_calc(char op, int n1, int n2)
    {
        if(op == '+') return n1 + n2;
        if(op == '-') return n1 - n2;
        if(op == '*') return n1 * n2;
        if(op == '/') return n1 / n2;
    }
    
    vector<int> calculate(int start_op_id, int end_op_id)
    {
        if(start_op_id == end_op_id)
        {
            vector<int> result;
            int op_id = start_op_id;
            result.push_back( basic_calc(op_vec[op_id], num_vec[op_id], num_vec[op_id+1]) );
            return result;
        }
        
        vector<int> result;
        for(int op_id = start_op_id; op_id <= end_op_id; op_id++)
        {
            vector<int> r1;
            if(start_op_id > op_id-1) r1.push_back( num_vec[start_op_id] );
            else                      r1 = calculate(start_op_id, op_id-1);
            
            vector<int> r2;
            if(op_id+1 > end_op_id)   r2.push_back( num_vec[end_op_id+1] );
            else                      r2 = calculate(op_id+1, end_op_id);
            
            for(vector<int>::const_iterator iter1 = r1.begin(); iter1 != r1.end(); iter1++)
                for(vector<int>::const_iterator iter2 = r2.begin(); iter2 != r2.end(); iter2++)
                    result.push_back( basic_calc(op_vec[op_id], *iter1, *iter2) );
        }
    
        return result;
    }
    
    vector<int> diffWaysToCompute(string input) 
    {
        Lexer(input);
        if( !op_vec.size() ) return num_vec;
        return calculate(0, op_vec.size()-1);
    }

Log in to reply
 

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