Expression Add Operators

07/17/2016 Divide and Conquer

Question

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Examples:

"123", 6 -> ["1+2+3", "1*2*3"]
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []

Solution

Result: Accepted Time: 380ms

Here should be some explanations.

#include <stdio.h>
#include <ctype.h>

typedef long long LL;
inline int getlv(char ch)
{
    switch(ch)
    {
    case '+':
    case '-':
        return 1;
    case '*':
    case '/':
        return 2;
    default:
       return 0;
    }
}

LL  operate(LL a ,LL b,char tmp)
{
    ///printf(" %d %c % d\n",a,tmp,b);
    switch (tmp)
    {
    case '+':
        return a + b;
    case '-':
       return a - b;
    case '*':
        return a * b;
    case '/':
       return a/b;
    }
    return 0;
}

bool deal(const char data[],const int target)
{
   // puts(data);
    char sta[100],tmp;
    int top=0,ptr=0,atop=1;
    LL ans[100]={0};
    LL value=0;
    while(data[ptr]!='\0')
    {
        if(isdigit(data[ptr]))
        {
            value = 0;
            if(isdigit(data[ptr+1]) && data[ptr] =='0' )/// pre zero
                return false;
            while(data[ptr]>='0'&&data[ptr]<='9')
                value = value * 10 + data[ptr++] - '0';
            ans[atop++] = value;

        }
        tmp=data[ptr++];
        if(tmp=='\0') break;
        if(top == 0)
            sta[top++] = tmp;
        else if((tmp=='-'||tmp=='+'||tmp=='*'||tmp=='/'))
        {
            int curlv=getlv(tmp);
            int stalv=getlv(sta[top-1]);
            while(curlv<=stalv)
            {
                ans[atop - 2] = operate(ans[atop -2],ans[atop - 1],sta[--top]);
                atop --;
                if(atop>0)
                    stalv=getlv(sta[top-1]);
                else
                    break;
            }
            sta[top++] = tmp;
        }
    }
    while(top > 0)
    {
        ans[atop - 2] = operate(ans[atop -2],ans[atop - 1],sta[--top]);
        atop --;
    }
    return ans[atop-1]==target;
}

class Solution {
public:
    void dfs(vector<string> & ret,char * buff, int cnt ,const char * str,const int target)
    {
        while(*str)
        {
            buff[cnt++] = *(str++);
            if(*str == 0)
            {
                 buff[cnt] =0;
                if(deal(buff,target))
                    ret.push_back(buff);
                return;
            }
            buff[cnt++] = '-';
            dfs(ret,buff,cnt,str,target);
              buff[cnt-1] = '+';
            dfs(ret,buff,cnt,str,target);
              buff[cnt-1] = '*';
            dfs(ret,buff,cnt,str,target);
            cnt--;
        }
    }

    vector<string> addOperators(string num, int target) {
        char buff[256],cnt =0;
        vector<string> ret;
        dfs(ret,buff,cnt,num.c_str(),target);
        return ret;
    }
};

Complexity Analytics

  • Time Complexity:
  • Space Complexity: