How to find all possible placements in a stack with using recursive function

[Armanc]

I am trying to code a program that finds a target number by using six other integers and four mathematical operations (+, -, *, /). I do not want to use any kind of library. In the end, I want to generate and print a string with parentheses that show how it did the mathematical process. I searched a bit and everyone suggests RPN for this type of coding but I couldn't figure out how I can try all possibilities. I can use numbers just once but I can use operations more than once. Such as 1 2 3 4 5 6 + + + + +, 4 6 - 3 2 1 5 * - - +, and 1 2 + 3 4 - 5 6 + * * or similar variants. Long story short, I want to use a recursive function that puts numbers in different places in the stack with different operators every time to find the target number. Can anyone show me what kind of approach I need?

[jonnin]

I would attack it by solving, not by iteration.
that said, by iteration, it is just a permutation, but it is a permutation inside a permutation.

if the numbers are a b c d e f
then you can permute those
there are 720 arrangements of these letters...
a b c d e f
a b c d f e
a b c f d e
... craft a loop to generate these.
now you need to do the same for the symbols, except that you are allowed repeats. its actually a 4 bit (digit) number scheme. you need 5 (digits) of them.
say + is 0, - is 1, * is 2, / is 3

0 0 0 0 0
0 0 0 0 1
0 0 0 0 2
0 0 0 0 3
0 0 0 1 0
0 0 0 1 1
0 0 0 1 2
... etc .. just increment the last digit and 'carry' into the next column each time.
I think that gives you 1024 possible values, 4 to the 5th power?
each of the 720 number combinations is tried with each of the 1024 symbol arrangements.
yuck, brute force.

I do not see a pattern to make RPN random stuffing work nicely. I will observe that RPN is not distinct.
1+2+3 is
1,2+ 3+
and it is the same for
1,2,3,++
this is partly due to the rules of addition (associative etc) and partly due to RPN.
so if you iterated every possible way, you will have repeats!

There has to be a better way, but nothing I can think of avoids a lot of iteration.
you can make a tree of it..
I am thinking every possible combination of 2 numbers (each pair of numbers with each operation). Then the results of that, each pair with each operation ... and so on. This is a much smaller number of things, I believe (?). The last set of pairs and operations should yield your number target and trace back to get how you arrived there?
some branches can be culled, is part of the key to the above. if your target is 123 and the last operation gave you 1975511 then multiplication and addition are right out as the next step, you gonna have to divide or subtract something.... (or if negative inputs, add a negative, which maybe should be factored out up front and restored after the fact).

I would try to solve it with say 3 numbers and 2 operations at first. Easier to debug and see all the possible combos etc.

[Armanc]

Thank you for your answer, but there is one more deal and it is that I need to use parentheses. If we assume that numbers are 1, 2, 3, 4, 5, and 6 then the answer should be written as (1+2)*(3-4)/(5+6) or (((((1+2)+3)/4)*5)-6). I actually wrote a code that recursively works and can calculate (((((1+2)+3)/4)*5)-6) type of answers but it cannot calculate (1+2)*(3-4)/(5+6) this type of operations. Also, can you show me what kind of loops do I need to use? Should I use for inside for with 6 and 4 times?

[jonnin]

it is perfectly *safe* to add () to RPN with a dumb algorithm that puts in excess.
I believe that every time you hit an operation, you can just drop () around the terms that make it up.
eg
3 2* 5 1/ *
(3*2)*(5/1) is what it comes down to.
but if you put () around every set of terms, it has the excessive
((3*2)*(5/1))
which is valid, if annoying.
do you know the RPN stack approach?
numbers: push onto the stack.
operators: pop the stack twice, operate, push result back onto the stack.
for stringify, you perform the operation becomes a string concat instead of math.
so lets do that...
3 2*5 1/*
3//push
2//push
* pop twice, multiply, push:
pop: 2
pop: 3
operate: *
so you have some sort of string s
s+='('
s+= toint(second_pop) //s = "(3"
s+= operator // s = "(3 *"
s+= first pop // s = "(3 * 2"
s+= ')' //s = "(3 * 2)"
push s back onto the stack (is stack of strings, of course)
5 push
1 push
/ (s = "(5/1)" and that is pushed back on
*
pop1 is "(5/1)"
pop2 is"(3*2)"
s becomes ((3*2)*(5/1))
right?
now try it for 4 2 * 16+
should get ((4*2)*16)

The loops depend on how you approached it.
if you are doing brute force, its nested loops, yes.
I would pre-compute the stuff.
pre-compute all the number orderings and stuff them into a container.
pre-compute all the operation orderings, and stuff those away as well.
then the loops look like
for(all the number orderings)
for(all the operator orderings)
compute the result and see if it matches.
if you did the tree or something like that, it is a recursive 'touch every leaf' algorithm, see examples of tree traversal code online, but basically
foo(node)
{
if not null go down * pointer: foo(node->*)
if not null go down + pointer : foo(node->+)
if not null go down / pointer ..etc
if not null go down - pointer
when all 4 pointers are null, check vs desired result for match, if got one, unwind call stack to find the computation.
}
I dunno about the tree idea, TBH. you would need either 1 tree for each number ordering, or a wide tree where the children are both value & operation not just operation.

for storing the intermediate computations, I would just use a map keyed off the value and how it was computed as the data (could even be a formatted string). There would not even be a loop, just query the map for the answer after it is populated. The loops would stuff the map, and would be sort of like the brute force one, just different..
I am honestly not sure any of these ideas are any better than brute force. There may be some trims you can do in the math (say, if you multiply the 2 largest values, there is no way to reduce it back to a small enough value to be the desired one, then a whole line of iteration dies on the first check) but its going to take some crunching to find the answer.