Arithmetic Problem Solve

[lennygon]

Suppose we have digits 1 2 3 4 5 6 7 8 9 and arithmetic operators +, -, and *.

Write a program that finds a formula that evaluates to 100 by inserting operators between the sequence of digits.

The following is a sample output:

12-3+4+5*6-7+8-9 = 100

Can anyone Solve this?

[ats15]

Your expression evaluates to 35, not 100
I never tried this problem, but here is how I would do it:
1) You have 4 operators:+,-,*, and keeping digits together
2) You have a string of length 9: 1,2,3,4,5,6,7,8,9
3) There are 8 places in this string where you can insert your operators
4) First create 4^8=65536 strings, where you have all combinations of operators. For example, the first string is 1+2+3+4+5+6+7+8+9, the second is 1-2+3+4+5+6+7+8+9, third is 1*2+3+4+5+6+7+8+9, forth is 12+3+4+5+6+7+8+9, then 1+2-3+4+5+6+7+8+9, 1-2-3+4+5+6+7+8+9, and so on.
5) Write a function to evaluate that string:
5a) split the string into integers (long integers) and operators
5b) keep track of the operators between these integers
5c) start evaluating the multiplication first
5d) evaluate additions and subtractions
So for the example that you gave above, your integers are 12,3,4,5,6,7,8,9, operators are -,+,+,*,-,+,-. You evaluate first the multiplication, 5*6=30, so your expression becomes
12-3+4+30-7+8-9. You initialize your evaluation to first element (12) then if the next operator is + you add the next integer, if the next operator is -, you subtract the next integer

You don't need to store all 65536 strings in memory, you can process them as soon as you create them.