Printing result when making target number by adding mathematical operators to a string

user_11245255 0
Viewed 113

I have a question how to print results in this problem.

I designed recursive function to solve because it's required condition but really don't know how to print the results

Here is problem

person1 and person2 play the game "target making by numerical expression". They make target number by using input string, numerical expression: +, -, *.

If they succeed to make target, they print how to make target number by numerical expression. If not, print "None"

First they input the string number like: "123"

Second input target like: "6"

We can only use numerical expression: '+', '-', '*'

The way to make target: 6 by "123" is "1 + 2 + 3", "1 * 2 * 3"

the way to make target: 7 by "125" is "1 * 2 + 5", "12 - 5"

If we can't make target by input string number, print "None" e.g) input string: "123", target: "4" => there is no result to make target.

#include <stdio.h>
#include <math.h>
#include <string.h>
#define max_string_num 11

void find_target(char string[], int target, int start, int end, int size);

int main() {
    char string[max_string_num];
    int result[100];
    int target;
    int len, count = 0;

    scanf("%s %d", string, &target); //input string number and input target number
    len = strlen(string); // check string number length
    
    //partitioning string number by recurtion function
    //can change the number of digit by changing 'i'
    for(int i = 1; i < len; i++)
        find_target(string, target, 0, len, i);

    return 0;
}

void find_target(char string[], int target, int start, int end, int size) {
    int i;
    int num1 = 0, num2 = 0; // save results of partitioning numbers

    // partitioning numbers
    for (i = start; i < size; i++)
        num1 += (string[i] - '0') * pow(10, size - 1 -i);

    for (i = size; i < end; i++)
        num2 += (string[i] - '0') * pow(10, end - 1 - i);

    //finish recursion
    if (end == size)
        return;

    // i don't know how to print result when i find target result
    if ((num1 + num2) == target) {
    }
    else if ((num1 - num2) == target) { 
    }
    else if ((num1 * num2) == target) {
    }
    else {
        //if don't make target by num1, num2, go recursion and partitioning
        find_target(string, target - num1, start + 1, end, size + 1);
        find_target(string, num1 - target, start + 1, end, size + 1);
        find_target(string, target / num1, start + 1, end, size + 1);
    }
}

First, I thought that I can print the result to save number in the array (or stack), but I can't make through my idea.

c algorithm
1 Answers

I think this code does what you intended to do. Note that it is not very efficient, but my guess it is not an issue here. First it creates all the combinations of numbers and operators as a string using recursive function and evaluates it to check if it equals to the desired value. Since it looks like your university work, I do not explain it in detail, try to find out the details yourself.

Example output:

Target=22, string=123456 
found: 1+2*3+4+5+6
found: 1-2+3*4+5+6
found: 1-2+34-5-6
found: 1-2-3+4*5+6
found: 1-2-3-4+5*6
found: 12+3-4+5+6
found: 12*3-4*5+6

#include <stdio.h>
#include <math.h>
#include <string.h>
#define max_string_num 11

bool found=false;

void find_target(const char string[], const char result[], const int target, const int end, const int size);

//Evaluate expression, str=string to evaluate, len - length of string, sign - sign
int eval(const char* str, const int len, const int sign=1)
{
    for (int i = 0; i < len; i++){
        if (str[i] == '+') return sign*eval(str, i) + eval(str+i+1, len-i-1);
        if (str[i] == '-') return sign*eval(str, i) + eval(str+i+1, len-i-1,-1);            
    }        
    for (int i = 0; i < len; i++)
        if (str[i] == '*') return sign*eval(str, i) * eval(str+i+1, len-i-1);         
    char tmp[max_string_num];
    strncpy (tmp, str, len );
    tmp[len] = '\0';   //copy a zero at the end
    return sign*atoi(tmp);
}

void process_operator(const char op, const char string[], const char result[], const int target, const int end, const int size)
{
    char str1[max_string_num];      //string of partitioning number 1
    char str2[max_string_num];      //string of partitioning number 2

    // partitioning strings
    strncpy (str1, string, size );
    str1[size] = '\0';   //copy a zero at the end
    
    strncpy (str2, string+size, end-size);
    str2[end-size] = '\0';   
   
    char tmp[2*max_string_num];
    sprintf(tmp,"%s%s%c%s", result, str1,op, str2);            
    if (eval(tmp, strlen(tmp)) == target) {
        found=1;
        printf("found: %s\n", tmp);  
    } 

    for(int i = 1; i < end-size; i++)
    {
        sprintf(tmp,"%s%s%c",result,str1,op);
        find_target(string+size, tmp, target, end-size, i);
    }
}

void find_target(const char string[], const char result[], const int target, const int end, const int size) {     
    process_operator('+',string, result, target,  end, size);
    process_operator('-',string, result, target,  end, size);
    process_operator('*',string, result, target,  end, size);
}


int main() {
    char result[]="";
    char string[max_string_num]="123456";
    int target=12*3-4*5+6;
    printf("Target=%d, string=%s \n", target, string);

    int len = strlen(string); // check string number length
    
    //partitioning string number by recurtion function
    //can change the number of digit by changing 'i'
    for(int i = 1; i < len; i++)
    {
        find_target(string, result, target, len, i);
    }

    if(!found) printf("None");

    return 0;
}
user_62007280
Related