[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]


Problem DescriptionInsert +(addition) or × (multiplication) operators as required into the string of digits 123456789 to form
an expression that evaluates to 2002. For example, if the desired value were 100, then one solution would be 1×2×3×4+5+6+7×8+9=100. Background & TechniquesThis program was prompted by a user request. It is similar to the Expressions100 program which requires insertion of + and  signs into the string 123456789 to form an expression which evaluates to 100. The approach used there also works here with a few interesting modifications Here, as in Expressions100, I treat the 8 spaces between the digits as "buckets" into which we'll insert either '+', '×' , or nothing. So we have 3 choices for each of 8 positions. That's only 3^{8 }1 (6581)^{ } possible solutions; hard for humans, trivial for computers. If we let 0 represent concatenation of digits, 1 represent '+' , and 2 represent '×' then the base 3 numbers from 00000000 to 22222222, cover all possibilities. Function Power calculates 3^{8 }and^{ } procedure ConvertBase converts numbers in that range to base three for us. Each these numbers represents an expression so, for example, base 3 number 01201201 represents the expression 12+3x45+6x78+9. The new wrinkle this time is the precedence difference between + and x; multiplications must be performed before additions. So here's a chance to view the world's simplest expression evaluator inn action.
A full expression operator using stacks deserves its own topic page, but for expressions restricted to + and × it's not too bad. We'll process each operation string (e.g. 01201201) from left to right. We concatenate digits as the concatenation operations (0's) are encountered. When we encounter a 1 (+) or 2 (×) operation, if the preceding operation was + we just push the number that is between the two operations, NextNum, onto the stack (see sidebar). If the preceding operation was ×, we'll pop the top entry off of the stack, multiply it by NextNum and push the result back onto the stack. When all 8 operations have been processed, stack items are the terms that must be summed to get the value of the expression. There are about 30 lines of Delphi code in this evaluate loop. I think the code could be cleaner, but it works so the maxim "If it ain't broke, don't fix it" seems to apply.

Original: October 28, 2002 
Modified: February 18, 2016 
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 20002017, Gary Darby All rights reserved. 