Expression Add Operators Solutions in C++

// Source : https://leetcode.com/problems/expression-add-operators/
// Author : Hao Chen
// Date   : 2016-01-16




class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> result;
        if (num.size() == 0) return result;
        helper(num, target, result, "", 0, 0, 0, ' ');
        return result;        
    }
    
    //DFS algorithm
    void helper(const string &num, const int target, //`num` and `target` never change
                vector<string>& result, // the array store all of the answers
                string solution, //the current potential answer.
                int idx, // the current index of `num` array
                long long val, // the current value we calculated so far
                long long prev, // the lastest value we used for calculation, which used for operation prioirty adjustment
                char preop ) // the latest "+" or "-" operation, which used for operation prioirty adjustment 
    {
        
        if (target == val && idx == num.size()){
            result.push_back(solution);
            return;
        }
        if (idx == num.size()) return;
        
        string n;
        long long v=0;
        for(int i=idx; i<num.size(); i++) {
            //get rid of the number which start by "0"
            //e.g.  "05" is not the case.
            if (n=="0") return;
            
            n = n + num[i];
            v = v*10 + num[i]-'0';
            
            if (solution.size()==0){ 
                // the first time for initialization
                helper(num, target, result, n, i+1, v, 0, ' ');
            }else{
                // '+' or '-' needn't to adjust the priority
                helper(num, target, result, solution + '+' + n, i+1, val+v, v, '+');
                helper(num, target, result, solution + '-' + n, i+1, val-v, v, '-');
                
                //if we meet multiply operation, we need adjust the calcualtion priority
                // e.g. if the previous value is calculated by 2+3=5, 
                //      then if we need to multipy 4, it is not 5*4, it is 2+3*4=2+12=24
                //      we need be careful about multiply again, such as: 2+3*4*5
                if (preop=='+') {
                    helper(num, target, result, solution + '*' + n, i+1, (val-prev)+prev*v, prev*v, preop);
                }else if (preop=='-'){
                    helper(num, target, result, solution + '*' + n, i+1, (val+prev)-prev*v, prev*v, preop);
                }else {
                    helper(num, target, result, solution + '*' + n, i+1, val*v, v, '*');
                }
            }
        }
        
    }
};

/// Source : https://leetcode.com/problems/expression-add-operators/description/
/// Author : liuyubobobo
/// Time   : 2018-09-03

#include <iostream>
#include <string>
#include <vector>
#include <cassert>

using namespace std;


/// Backtracking to split num and eval
/// The eval function comes from Leetcode 227
/// https://leetcode.com/problems/basic-calculator-ii/description/
///
/// Time Complexity: O(n*3^n)
/// Space Complexity: O(3^n)
class Solution {
public:
    vector<string> addOperators(string num, int target) {

        if(num == "")
            return {};
        vector<string> ret;
        split(num, 0, target, "", ret);
        return ret;
    }

private:
    void split(const string& num, int index, int target, const string& expr,
               vector<string>& res){

        if(index == num.size()){
            if(calculate(expr) == target)
                res.push_back(expr);
            return;
        }

        int end = num.size();
        if(num[index] == '0')
            end = index + 1;
        for(int i = index; i < end; i ++){
            int len = (i + 1 - index);
            if(index + len == num.size())
                split(num, index + len, target, expr + num.substr(index, len), res);
            else{
                split(num, index + len, target, expr + num.substr(index, len) + "+", res);
                split(num, index + len, target, expr + num.substr(index, len) + "-", res);
                split(num, index + len, target, expr + num.substr(index, len) + "*", res);
            }
        }
    }

    long long calculate(const string& s) {

        vector<long long> nums;
        vector<char> ops;
        for(int i = 0; i < s.size() ; ){
            if(isdigit(s[i])){
                long long num = s[i] - '0';
                int j;
                for(j = i + 1; j < s.size() && isdigit(s[j]); j ++)
                    num = num * 10 + (s[j] - '0');
                i = j;

                nums.push_back(num);
                if(!ops.empty() && (ops.back() == '*' || ops.back() == '/'))
                    calc(nums, ops);
            }
            else if(s[i] != ' '){
                if((s[i] == '+' || s[i] == '-') && !ops.empty() && (ops.back() == '+' || ops.back() == '-'))
                    calc(nums, ops);
                ops.push_back(s[i++]);
            }
            else
                i ++;
        }
        if(nums.size() != 1){
            assert(nums.size() == 2);
            calc(nums, ops);
        }

        return nums.back();
    }

    void calc(vector<long long>& nums, vector<char>& ops){

        assert(nums.size() >= 2);
        long long second = nums.back();
        nums.pop_back();
        long long first = nums.back();
        nums.pop_back();

        assert(!ops.empty());
        char op = ops.back();
        ops.pop_back();

        switch(op){
            case '+': nums.push_back(first + second); return;
            case '-': nums.push_back(first - second); return;
            case '*': nums.push_back(first * second); return;
            case '/': nums.push_back(first / second); return;
            default: assert(false); return;
        }
    }
};


void print_vec(const vector<string>& vec){
    cout << "[ ";
    for(const string& e: vec)
        cout << e << " ";
    cout << "]" << endl;
}

int main() {

    string nums1 = "123";
    print_vec(Solution().addOperators(nums1, 6)); //2

    string nums2 = "232";
    print_vec(Solution().addOperators(nums2, 8)); // 2

    string nums3 = "105";
    print_vec(Solution().addOperators(nums3, 5)); // 2

    string nums4 = "00";
    print_vec(Solution().addOperators(nums4, 0)); // 3

    string nums5 = "3456237490";
    print_vec(Solution().addOperators(nums5, 9191)); // 0

    string nums6 = "2147483647";
    print_vec(Solution().addOperators(nums6, 2147483647)); // 1

    string nums7 = "2147483648";
    print_vec(Solution().addOperators(nums7, -2147483648)); // 0

    return 0;
}

/// Source : https://leetcode.com/problems/expression-add-operators/description/
/// Author : liuyubobobo
/// Time   : 2018-09-07

#include <iostream>
#include <string>
#include <vector>
#include <cassert>

using namespace std;


/// Backtracking to split num and eval
/// Evaluate the expression on the fly :)
///
/// Time Complexity: O(3^n)
/// Space Complexity: O(3^n)
class Solution {
public:
    vector<string> addOperators(string num, int target) {

        if(num == "")
            return {};
        vector<string> ret;
        split(num, 0, target, "", ' ', -1, 0ll, ret);
        return ret;
    }

private:
    void split(const string& num, int index, int target, const string& expr,
               char lastop, long long pre, long long res, vector<string>& ret){

        if(index == num.size()){
            if(res == (long long)target)
                ret.push_back(expr);
            return;
        }

        int end = num.size();
        if(num[index] == '0')
            end = index + 1;

        for(int i = index + 1; i <= end; i ++){
            int len = i - index;
            string cur_num_s = num.substr(index, len);
            long long cur = atol(cur_num_s.c_str());

            char next_lastop = ' ';
            long long next_pre = cur;
            long long next_res = res;

            if(expr[expr.size() - 1] == '*' && (lastop == '+' || lastop == '-')){
                assert(pre != -1);
                if(lastop == '+')
                    next_res -= pre, next_res += pre * cur;
                else
                    next_res += pre, next_res -= pre * cur;
                next_pre = pre * cur;
                next_lastop = lastop;
            }
            else if(expr != ""){
                switch(expr[expr.size() - 1]){
                    case '+': next_res += cur; break;
                    case '-': next_res -= cur; break;
                    case '*': next_res *= cur; break;
                    default:assert(false); break;
                }
                next_lastop = expr[expr.size() - 1];
            }
            else
                next_res = cur;

            if(index + len == num.size())
                split(num, index + len, target, expr + cur_num_s,
                      ' ', next_pre, next_res, ret);
            else{
                split(num, index + len, target, expr + cur_num_s + "*",
                      next_lastop, next_pre, next_res, ret);
                split(num, index + len, target, expr + cur_num_s + "+",
                      next_lastop, next_pre, next_res, ret);
                split(num, index + len, target, expr + cur_num_s + "-",
                      next_lastop, next_pre, next_res, ret);
            }
        }
    }
};


void print_vec(const vector<string>& vec){
    cout << "[ ";
    for(const string& e: vec)
        cout << e << " ";
    cout << "]" << endl;
}

int main() {

    string nums1 = "123";
    print_vec(Solution().addOperators(nums1, 6)); //2

    string nums2 = "232";
    print_vec(Solution().addOperators(nums2, 8)); // 2

    string nums3 = "105";
    print_vec(Solution().addOperators(nums3, 5)); // 2

    string nums4 = "00";
    print_vec(Solution().addOperators(nums4, 0)); // 3

    string nums5 = "3456237490";
    print_vec(Solution().addOperators(nums5, 9191)); // 0

    string nums6 = "2147483647";
    print_vec(Solution().addOperators(nums6, 2147483647)); // 1

    string nums7 = "2147483648";
    print_vec(Solution().addOperators(nums7, -2147483648)); // 0

    string nums8 = "123456789";
    print_vec(Solution().addOperators(nums8, 45));

    return 0;
}