Problem Description
Given a set of integers and a target value,
construct an expression by inserting arithmetic operators (+, -,
x, ÷)
into the set of integers without rearranging them so that the value of
the expression equals the target value.
Background & Techniques
This is a generalized extension of the
Expressions100 and Expressions2002
programs previously posted. This version will search for
solutions for any set of digits and any integer expression value. It was prompted by a problem posed by a
viewer (Using five 9's, form an expression which equals
10).
Non-programmers are welcome to read on, but may
want to skip to the bottom of this page to
download executable version of the program.
Expressions2002 generated all 8
digit base 3 numbers (00000000 to 22222222) to define operators to
be inserted into the 8 slots between the 9 given digits. Operators
there were +, x, and concatenation. ExpressionsForBethe
extends the concept to base 5 numbers (for the four operators and
concatenation) and for a variable number of slots (always one less than
the number of input digits).
I handled the "order of operations"
problem in Expressions2002 by introducing a "stack" to
hold terms until we know it is OK to evaluate them. I
described the process in some detail there, so i won't repeat it
here. The division operation here needed tests so that we don't try
to divide b y zero and to make sure that the quotient is an exact integer
(divisor divides the dividend exactly).
Running/Exploring the Program
Suggestions for Further Explorations
 |
Allow
parentheses |
|
Allow
user control of allowable set of operators. |
| Original Date: June 11, 2004 |
Modified: July 21, 2006
|
|
