find_equation_in_string.txt

/*
 Given a number find whether the digits in the number can be used to form an equation with + and '='. 
 That is if the number is 123, we can have a equation of 1+2=3. But even the number 17512 also forms the equation 12+5=17.
*/

#include <iostream>
using namespace std;

#define N 20

bool isEquation(int num1[], int num2[], int num3[], int len1,int len2, int len3){
    //In this function, the first step is to convert int array[] to integer
    int int1=0, int2=0, int3=0;
    for (int i=0; i<len1; ++i){
        int1 *= 10;
        int1 += num1[i];
    }
    for (int i=0; i<len2; ++i){
        int2 *= 10;
        int2 += num2[i];
    }
    for (int i=0; i<len3; ++i){
        int3 *= 10;
        int3 += num3[i];
    }
    if (int1+int2==int3)
        return true;
    else return false;
    
}

void printEquation(int num1[], int num2[], int num3[], int len1,int len2, int len3){
    for (int i=0; i<len1; ++i)
        cout<<num1[i];
    cout<<" + ";
    for (int i=0; i<len2; ++i)
        cout<<num2[i];
    cout<<" = ";
    for (int i=0; i<len3; ++i)
        cout<<num3[i];
    cout<<endl;
}

int main(){
    string str;//the input
    cout<<"Input a sequence of number:"<<endl;
    cin>>str;
    //verify the input
    for (int i=0; i<str.length(); ++i){
        if (str[i]>'9' || str[i]<'0'){
            cout<<"wrong input."<<endl;
            return 0;
        }
    }
    
    int str1[N], str2[N], str3[N], len1=0, len2=0,len3=0;
    int i,j,k;//i is the first index of +/=, j is the second index of +/=
    for (i=1; i<str.length()-1; ++i){
        for (j=i; j<str.length()-1; ++j){
            for (k=0; k<i; ++k){
                str1[k]=str[k]-'0';
                
            }
            len1=i;
            for (k=i; k<=j; ++k){
                str2[k-i]=str[k]-'0';
                
            }
            len2=j-i+1;
            for (k=j+1; k<str.length(); ++k){
                str3[k-j-1]=str[k]-'0';
                
            }
            len3 = str.length()-1-j;
            if (isEquation(str1,str2,str3,len1,len2,len3)){//determine if str1+str2=str3
                cout<<"This is an equation"<<endl;
                printEquation(str1,str2,str3,len1,len2,len3);
                return 0;
            }
            if (isEquation(str1,str3,str2,len1,len3,len2)){//determine if str1+str3=str2
                cout<<"This is an equation"<<endl;
                printEquation(str1,str3,str2,len1,len3,len2);
                return 0;
            }
            if (isEquation(str2,str3,str1,len2,len3,len1)){//dertermine if str2+str3=str1
                cout<<"This is an equation"<<endl;
                printEquation(str2,str3,str1,len2,len3,len1);
                return 0;
            }
        }
    }
cout<<"This is not equation"<<endl;    
return 0;
}




REMARK
1. NOTE: for simplicity, we set the size of all the array as N(=20).
2. IDEA: Because the equation is composed of three part, so we first break the string in three part, a,b,c. Then we test if any of the 3 cases valid:
1)a+b=c
2)a+c=b
3)b+c=a