1
$\begingroup$

I am trying to find a permutation (with replacement) of operators(such as addition and multiplication) that makes numbers 1 2 3 , ..., 9 result in to some numbers.

My guess is to find all possible permutation with Cartesian products (8 times) of {operator set}, and append them after the numbers (e.g. 1 2 3 , ..., 9 + * + + * * ...) and evaluate them.

The question is, if I am not using parentheses, i.e. there is nothing like 1 + 2 * (3 + 4), am I safe to attach an array of 8 binary operators after the 9 numbers?

Or even in that case should I first construct the expression in in-fix, and convert it into Reverse Polish notation using Shunting-yard algorithm?

Also, will there be any further optimization or better algorithms that I could make use of?

Thanks.

$\endgroup$
  • $\begingroup$ I don't think you are asking the right question. If you had only 1,2,3,4,5 for example and wanted 1+2*3*4+5, you can't get it with reverse polish notation having 1,2,3,4,5 in that fixed order and then some arithmetic operators. $\endgroup$ – user21820 Oct 21 '14 at 9:20
  • $\begingroup$ I am finding, say, combinations of * and + that results in 30. Then I will put 1 2 3 4 5 and all possible cases of 4 operators in stack, and evaluate them. It will find that the output of (1 2 3 4 5 + * * +) is 30, and will find other combinations. $\endgroup$ – Eric Na Oct 21 '14 at 9:24
  • $\begingroup$ No that doesn't work. That means you don't understand reverse polish notation. What your sequence will get is (5+4)*3*2+1. $\endgroup$ – user21820 Oct 21 '14 at 9:32
  • $\begingroup$ You are right. I see that now. However, is there any way to put all numbers first and then all operators later and calculate them? For example if the array of numbers is 1 2 3, I want to test 1 + 2 + 3, 1 + 2 * 3, 1 * 2 + 3, 1 * 2 * 3. I first thought this would be done by putting 123++, 123*+, 123+*, 123**, but this does not work, esp. for larger array of numbers, because of the order of operators. $\endgroup$ – Eric Na Oct 21 '14 at 10:05
  • $\begingroup$ The easiest way I could think of was to make all possible in-fix expressions, and then convert them into Reverse Polish notation using Shunting-yard algorithm, and then evaluating the value. However, this is too complex, so I posted the question. $\endgroup$ – Eric Na Oct 21 '14 at 10:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.