Arithmetic expression generator
MrWraith
I've seen this rather interesting question posed on a couple of
programming tests for jobs I was pursuing. Has anyone out there
encountered this type of problem before, or give me pointers on how to
tackle it?
you have a program with the following prototype:
char * arith_expression_fit(char *digits, int size, int answer);
The routine has to construct an arithmetic expression with '+' and '*'
operators with the digits string such that it evaluates to the answer
parameter. If there is no proper expression, an errored int is
returned.
Example:
digits -> "1237410"
answer -> 9112
expression: 123 * 74 + 10
Thanks for your help! C.
--
comp.lang.c.moderated - moderation address: cl...@plethora.net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.
Jack Klein
<spamt...@gmail.com> wrote in comp.lang.c.moderated:
> Hi all -
>
> I've seen this rather interesting question posed on a couple of
> programming tests for jobs I was pursuing. Has anyone out there
> encountered this type of problem before, or give me pointers on how to
> tackle it?
>
> you have a program with the following prototype:
>
> char * arith_expression_fit(char *digits, int size, int answer);
>
> The routine has to construct an arithmetic expression with '+' and '*'
> operators with the digits string such that it evaluates to the answer
> parameter. If there is no proper expression, an errored int is
> returned.
>
> Example:
>
> digits -> "1237410"
> answer -> 9112
>
> expression: 123 * 74 + 10
You haven't provided nearly enough information for anyone to provide
you with much help. How do you know that your particular input string
is supposed to be interpreted as you show?
Why not 123 + 74 * 10?
Why not 12 * 37 + 410?
What if the string has six digits instead of seven? Or five, or eight
or ten?
> Thanks for your help! C.
Without a proper specification for what the function should do, there
isn't too much help I can offer.
Generically, I would make sure I had a sufficiently large array to
copy the digit string into, in case the pointer passed was to a string
literal. If necessary, I would use malloc() to obtain the array. Then
I would copy the contents of the digit string into my array.
Then, knowing by some means what the proper number of digits should
be, I would verify that the array copy had exactly the correct number
of digits with no incorrect characters.
Finally, knowing by some means you have not disclosed how the digits
are supposed to be partitioned, I would iterate through the string,
copying the proper subset of digits for each value into a separate
array, terminating with '\0' each time, and use the strtol() or
strtoul() library functions to retrieve the value.
--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://c-faq.com/
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.club.cc.cmu.edu/~ajo/docs/FAQ-acllc.html
Hans-Bernhard Bröker
> I've seen this rather interesting question posed on a couple of
> programming tests for jobs I was pursuing. Has anyone out there
> encountered this type of problem before, or give me pointers on how to
> tackle it?
Pretty much none of the problem's difficulty has anything to do with C.
It's entirely an algorithmic question.
> The routine has to construct an arithmetic expression with '+' and '*'
> operators with the digits string such that it evaluates to the answer
> parameter. If there is no proper expression, an errored int is
> returned.
The example is more descriptive than the solution --- you forgot to
mention that the digits are to be used in sequence. The solution is
quite obviously exhaustive search. Try all possible placements of '+'
and '*' operators in the string, and evaluate them. Return once you
found match.
Jens Schweikhardt
in <clcm-2008...@plethora.net>:
# Hi all -
#
# I've seen this rather interesting question posed on a couple of
# programming tests for jobs I was pursuing. Has anyone out there
# encountered this type of problem before, or give me pointers on how to
# tackle it?
#
# you have a program with the following prototype:
#
# char * arith_expression_fit(char *digits, int size, int answer);
#
# The routine has to construct an arithmetic expression with '+' and '*'
# operators with the digits string such that it evaluates to the answer
# parameter. If there is no proper expression, an errored int is
# returned.
#
# Example:
#
# digits -> "1237410"
# answer -> 9112
#
# expression: 123 * 74 + 10
My approach would be this:
1. You have three "operators" to place in between each single digit,
"" (nothing), "*" and "+".
2. Write a loop to generate all these combinations.
3. Evaluate each result, in two passes, where pass one computes
the multiplications and pass two the remaining additions.
4. Print result.
I've done something similar a while back for the operators + - * /, and
able to deal with fractions. You can specify the number of values, a
start value, an increment and a goal value. E.g. 8 values, start 2,
increment by 1/2 and goal 42 would print
$ ./prog 8 2 1/2 42
2 * 5/2 - 3 + 7/2 * 4 + 9/2 + 5 * 11/2 - 6 = 42
2 * 5/2 * 3 + 7/2 + 4 * 9/2 + 5 - 11/2 + 6 = 42
2 + 5/2 + 3 * 7/2 + 4 + 9/2 * 5 - 11/2 + 6 = 42
2 + 5/2 + 3 - 7/2 + 4 + 9/2 * 5 + 11/2 + 6 = 42
2 - 5/2 - 3 + 7/2 + 4 + 9/2 + 5 * 11/2 + 6 = 42
2 * 5/2 - 3 + 7/2 + 4 + 9/2 - 5 + 11/2 * 6 = 42
2 * 5/2 + 3 - 7/2 + 4 - 9/2 + 5 + 11/2 * 6 = 42
2 - 5/2 * 3 + 7/2 * 4 - 9/2 + 5 + 11/2 * 6 = 42
2 / 5/2 * 3 + 7/2 + 4 - 9/2 / 5 + 11/2 * 6 = 42
This program is open source, you'll find it here
http://www.ioccc.org/years.html#1996 (look for schweikh2)
Have fun :-)
Regards,
Jens
--
Jens Schweikhardt http://www.schweikhardt.net/
SIGSIG -- signature too long (core dumped)
Kevin Ashley
> Hi all -
>
> I've seen this rather interesting question posed on a couple of
> programming tests for jobs I was pursuing. Has anyone out there
> encountered this type of problem before, or give me pointers on how to
> tackle it?
>
One way is to search online. Someone rejoicing in the handle "Icebeing"
asked an almost identical question in this newsgroup on September 21st
last year, and received a number of replies (although due to moderation
delays they didn't appear until January of the following year.)
Keith Thompson
> On Sat, 28 Jun 2008 19:02:54 -0500 (CDT), MrWraith
> <spamt...@gmail.com> wrote in comp.lang.c.moderated:
>> programming tests for jobs I was pursuing. Has anyone out there
>> encountered this type of problem before, or give me pointers on how to
>> tackle it?
>>
>> you have a program with the following prototype:
>>
>> char * arith_expression_fit(char *digits, int size, int answer);
>>
>> The routine has to construct an arithmetic expression with '+' and '*'
>> operators with the digits string such that it evaluates to the answer
>> parameter. If there is no proper expression, an errored int is
>> returned.
>>
>> Example:
>>
>> digits -> "1237410"
>> answer -> 9112
>>
>> expression: 123 * 74 + 10
>
> You haven't provided nearly enough information for anyone to provide
> you with much help. How do you know that your particular input string
> is supposed to be interpreted as you show?
>
> Why not 123 + 74 * 10?
>
> Why not 12 * 37 + 410?
Because neither of those evaluates to 9112.
I think you missed the fact that both the digit string "1237410" and
the result 9112 are provided as input. The problem is to partition
the digits, with "*" and "+" operators, so the result is what was
specified.
It's still a bit under-specified (does it have to be x*y+z, or can it
be x+y*z?).
[snip]
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Dag-Erling Smørgrav
> I've seen this rather interesting question posed on a couple of
> programming tests for jobs I was pursuing. Has anyone out there
> encountered this type of problem before, or give me pointers on how to
You know, the whole point with tests like these, or exams or whatnot, is
to figure out what you can do on your own, not what you can get someone
else to do for you.
DES
--
Dag-Erling Smørgrav - d...@des.no