#include <iostream> using namespace std; struct MyException { }; double Plus(double first, double second) { return (first + second); } double Minus(double first, double second) { return (first - second); } double Multiply(double first, double second) { return (first * second); } double Divide(double first, double second) { return (first / second); } typedef double (*Calculate) (double, double); Calculate Symbol2Calculate(char symbol) { switch (symbol) { case '+': { return Plus; } case '-': { return Minus; } case '*': { return Multiply; } case '/': { return Divide; } default: { throw MyException(); return NULL; } } } void have_a_try(double numbers[], char symbols[], int & symbols_max_index, double prev_lvalue, char prev_oper, double prev_rvalue, int array[], int start, int end, int & solve_num, int need) { if (start == end) { double result = (Symbol2Calculate(prev_oper))(prev_lvalue, prev_rvalue) - need; if (result > -0.000001 && result < 0.000001) { ++solve_num; cout << "solve " << solve_num << " : "; for (int i = 0; i < symbols_max_index; ++i) { cout << numbers[i] << ' ' << symbols[i] << ' '; } cout << numbers[symbols_max_index] << " = " << 100 << endl; } } else { long value = 0; for (int i = start; i < end; ++i) { value = 10 * value + array[i]; numbers[symbols_max_index + 1] = value; static char oper[] = { '+', '-', '*', '/' }; static Calculate calculate[] = { Plus, Minus, Multiply, Divide }; for (int j = 0; j < 4; ++j) { symbols[symbols_max_index] = oper[j]; ++symbols_max_index; double lvalue = 0.0; double rvalue = 0.0; char next_oper = '\0'; if (j < 2) { lvalue = (Symbol2Calculate(prev_oper))(prev_lvalue, prev_rvalue); rvalue = value; next_oper = oper[j]; } else { if ('*' == prev_oper || '/' == prev_oper) { lvalue = (Symbol2Calculate(prev_oper))(prev_lvalue, prev_rvalue); rvalue = value; next_oper = oper[j]; } else { lvalue = prev_lvalue; rvalue = (Symbol2Calculate(oper[j]))(prev_rvalue, value); next_oper = prev_oper; } } have_a_try( numbers, symbols, symbols_max_index, lvalue, next_oper, rvalue, array, i + 1, end, solve_num, need ); --symbols_max_index; } } } } void get_expression(int array[], int length, int need) { double * numbers = new double[length]; char * symbols = new char[length - 1]; int symbols_max_index = 0; int solve_num = 0; long value = 0; for (int i = 0; i < length; ++i) { value = 10 * value + array[i]; numbers[0] = value; have_a_try( numbers, symbols, symbols_max_index, 1, '*', value, array, i + 1, length, solve_num, need ); } if (0 == solve_num) { cout << "no answer!" << endl; } else { cout << "there are " << solve_num << " solves!" << endl; } delete [] numbers; delete [] symbols; } int main() { cout << " using 1,2,3,4,5,6,7,8,9 with +,-,*,/ to get 100 " << endl; int array1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int length1 = sizeof(array1) / sizeof(array1[0]); int need1 = 100; try { get_expression(array1, length1, need1); } catch (MyException & e) { cout << "exception" << endl; } cin.get(); cout << " using 9,8,7,6,5,4,3,2,1 with +,-,*,/ to get 100 " << endl; int array2[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1 }; int length2 = sizeof(array2) / sizeof(array2[0]); int need2 = 100; try { get_expression(array2, length2, need2); } catch (MyException & e) { cout << "exception" << endl; } return 0; }