# Is shunting-yard algorithm needed if there is no parenthesis?

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.

• 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. Oct 21, 2014 at 9:20
• 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.
– Eric
Oct 21, 2014 at 9:24
• 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. Oct 21, 2014 at 9:32
• 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.
– Eric
Oct 21, 2014 at 10:05
• 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.
– Eric
Oct 21, 2014 at 10:08