1. Original title

[Title Source: LeetCode question 241] given a string containing numbers and operators, add parentheses to the expression and change its operation priority to get different results. You need to give the results of all possible combinations. Valid operation symbols include +, - and *.
If the given string is 2 + 1-1 and there are two calculation methods ((2 + 1) - 1) = 2 and (2 + (1-1)) = 2, the program output result should be [2,2]

2 topic analysis

Because the original problem is relatively complex, it is considered whether it can be simplified by recursion. With the operator as the boundary, the expression string can be divided into two parts, and the problem becomes to solve the possible values of two simpler strings, so the problem is simplified. The final result is that the solutions of the two parts perform corresponding operations respectively.
The whole recursive process is as follows:

1. If the string expression consists entirely of numbers, it is converted to an integer number and returned.
2. If it is not all composed of numbers, recursive processing is carried out until the recursive exit condition is met, and the possible values of the two parts are calculated.

Still take 2 + 1-1 as an example and divide the expression string into two parts with the operator as the boundary. There are two methods:

1. Divided by + can be divided into two parts: 2 and 1-1. The first half directly returns 2, and the second half can be divided into 1 and 1 after recursive processing. Since the recursive exit conditions are met, 1 and 1 will be returned directly, and 1-1 = 0 will be calculated. Finally, 2 + 0 = 2 will be calculated
2. Divided by -, it can be divided into two parts: 2 + 1 and 1. The first half can be divided into two parts: 2 and 1. Since the recursive exit conditions are met, it will directly return 2 and 1, and calculate 2 + 1 = 3. The second half will directly return 1, and finally calculate 3-1 = 2

3 code implementation

The title requires malloc to apply for space and return its address. The number of returned data is received by the pointer parameter of the function. Its prototype is as follows: int* diffWaysToCompute(char* expression, int* returnSize)

The complete code is as follows:

// Calculate according to operands and operators
int calc(int num1, int num2, char op)
{
	if (op == '+')
		return num1 + num2;
	else if (op == '-')
		return num1 - num2;
	else
		return num1 * num2;
}

// Judge whether a character is a numeric character
int isnum(char c1)
{
	return (c1 >= '0' && c1 <= '9');
}

// Determine whether a character is an operator
int isop(char* c1)
{
	return *c1 == '+' || *c1 == '-' || *c1 == '*';
}

/*
	This function is the real implementation process. exp - string expression, len - expression length retsize - number of received results
*/
int* diffWaysToCompute1(char* exp, int len, int* retsize)
{
	int icnt = 0;
	int* res = NULL;
	int index = 0;
    int retsize1 = 0;
	int retsize2 = 0;

    res = (int*)malloc(sizeof(int));

	// If all are numbers, return directly
	while (icnt < len)
	{
		if (!isnum(*(exp + icnt))) break;
		icnt++;
	}

	if (icnt == len)
	{
		*res = atoi(exp);  
		*retsize = 1;
	}
	else
	{
        for (int i = 0; i < len; i++) // Traverse the string and divide the string according to the operator
		{
			if (isop(exp + i)) // If it is an operator, it is segmented and recursive
			{
				int* res1 = diffWaysToCompute1(exp, i, &retsize1); // Recursively calculate the left half string
				int* res2 = diffWaysToCompute1(exp + i + 1, len - i - 1, &retsize2); // Recursively calculate the right half of the string
				// Re apply for space according to the results of the left and right expression strings. realloc is used because the final results generated in the previous cycle need to be saved
                int* tmp = (int*)realloc(res, (index + retsize1 * retsize2) * sizeof(int));
                res = tmp;
				for (int m = 0; m < retsize1; m++)
				{
					for (int n = 0; n < retsize2; n++)
					{
						res[index++] = calc(res1[m], res2[n], exp[i]); //Calculation expression
					}
				}
				free(res1); // res1 and res2 are applied by malloc in the upper layer recursion, and are released after use
				free(res2);
			}
		}
        *retsize = index; // Return the number of final results
	}
	return res;
}


int* diffWaysToCompute(char* expression, int* returnSize) {
	//The reason why diffWaysToCompute1 with length parameter is used for recursion is mainly to save memory space
	return diffWaysToCompute1(expression, strlen(expression), returnSize);
}

Note: the illegal expression is not considered in the code, and the entered expression is legal by default