How to arrange brackets in an expression in all possible ways? what is the complexity of the optimal algorithm?

Question

Algorithms

Good afternoon!
There is an arithmetic expression consisting of integers, and operations +, -, *, \ for example 1 + 2-3 * 4. It is necessary to find the set of all unique results of the given expression for all possible arrangements of brackets in the expression:
(1+2)-(3*4); (1+2-3)*4 etc.
I came up with 3 algorithms, but they all have O(n!) worst case. Are there better algorithms?
For simplicity, let's assume that there are two arrays nums and ops - so as not to go into the details of parsing the expression.
My solutions:
Option 1
1. we define a recursive function, which receives two arrays ops and nums and a third array, where we will add the results
2. If ops is empty, or ops contains one operation, or ops contains operations of the same priority, evaluate the value of the expression, because its result does not depend on the arrangement of brackets, we add this result to the array with the results and return from the function.
3. Loop through all operations from the ops array
4. for the selected operation - we consider that it will be the first, select the operands corresponding to it from nums, perform the operation
5. update the nums array, replacing two operands with the result of the operation and deleting the operation from the ops array
6. recursively call the function for new smaller nums and ops arrays
7. continue the loop
8. remove all duplicates in the resulting array using standard functions
Option 2.
1. define a recursive function with the same input as in the first option
2. If ops is empty, or ops contains one operation, or ops contains operations of the same priority, we calculate the value of the expression, because its result does not depend on the arrangement of brackets, we add this result to the array with the results and return from the function.
3. cycle through all operations
4. we will consider the selected operation as the last one when calculating
5. We form two subexpressions, everything that is to the left of the selected operation and everything to the right
6. Recursively calculate the result of the function execution on 2 subexpressions, we get two arrays with unique results.
7. make a Cartesian product of these arrays - performing the selected operation for each pair, enter it into the resulting array 8. Remove
duplicates from the resulting array And with more or less standard algorithms, we get all possible permutations of this array, then we consider the expression, taking into account the sequence of operations in accordance with the next permutation. Analysis All algorithms have O(n!) complexity, but the second algorithm reduces complexity due to the fact that: 1. (1+1-4+6) - this kind of subexpressions are immediately considered without trying to place brackets in different ways

2. (1-2)-(3*4) - calculates once because it doesn't matter to us what will be counted first (1-2) or (3*4). In the first algorithm, such an expression will be obtained both when choosing the first minute as the first operation and when choosing the first multiplication operation.
I will be grateful if someone sends more interesting solutions or helps to prove that the second option is the optimal solution.

Answer 1

For your case, the results of the expression will differ from the variant without parentheses only if the priority of operations changes. Those. (1+2)-(3*4) does not give a unique result, but (1+2-3)*4 does.
Total - you need to put a closing bracket before the sign * or /, and an opening bracket before each previous operation.
In addition, when you arrange the brackets, you need to take the expression in brackets and recursively run it through the algorithm, thus arrange the nested brackets until there is a simple expression like a + b inside the brackets, where nothing can be put.

Answer 2

This is pure dynamic programming. We have N+1 operands, and N operations.
Create cache: for all L and R, 0<=L<=R<=N, we store:
• Operation: null, +, ×, many.
• Associative array:
•• Key - a number (integer/rational/floating/fixed - with what you want to work with).
̃•• Value - triple:
••• Operation number with max. priority.
••• Value on the left (same number).
••• Value on the right (same number).
For all L=R, the cache is filled with the following value:
• The operation is null.
• There is one element in the array: the key is the operand, the value is any plug.
For a cache, for example, a matrix (N + 1) × (N + 1) is suitable.
After that, we go through the diagonals of our cache, processing first L=0..N−1, R=L+1, then L=0..N−2, R=L+2, etc., until we reach to a diagonal of one element: L=0, R=N. How exactly do we process?
1. We look at the operation recorded in the cache (L + 1, R), and the L-th operation in the expression. If the second is “add” or “multiply”, and the first is null or the same, we write this operation into the cache in place (L, R). Otherwise, we write many.
2. Calculate R1: if there is some operation in the cache in place (L, R), then L; if many, then R−1 (associativity optimization).
3. We go through all M=L…R1.
3.1. Double loop through the contents of the cache in (L,M) and (M+1, R). Let's denote the variables u and v.
3.1.1. Write to the cache in place (L,R) if there is none:
       • key u (+−×/) v
       • operation number — M
       • left and right values ​​— u and v.
Consider, for example, 1 + 2 + 3 − 4.
(0, 0) - null; (1 → ? ? ?)
(1, 1) — null, (2 → ? ? ?)
(2, 2) — null, (3 → ? ? ?)
(3, 3) — null, (4 → ? ? ?)
UPD: We have operands { 1 2 3 4 }, orerations { + + − }. Well, of course.
Now we look at what will happen in (0, 1). At (1, 1) in the null cache, the null + operation is the + operation. One iteration, R1=0.
Scrolling through this iteration, we get ...
(0, 1) - +; (3 → 0 1 2). This means: we got 3 by adding 0 plus 1 and 2.
Similarly ...
(1, 2) - +; (5 → 1 2 3)
(2, 3) - many; (−1 → 2 3 4)
second diagonal. (0, 2). At position (1, 2): in cache +, 0th operation +. We write down + and scroll through one iteration, from 0 to 0. I.e. add (0, 0) and (1, 2).
(0, 2) - +; (6 → 0 1 5).
Now (1, 3). The operation will be many; scroll and get:
for M=1 — add (1, 1) and (2, 3), and get (1 → 1, 2, −1).
for M=2, subtract (1, 2) and (3, 3), and get (1 → 2, 5, 4).
If without duplicates ...
(1,3) - many; (1 → 1 2 -1)
And finally, let's go (0, 3). The operation will be many ...
for M=0 - add (0, 0) and (1, 3), and it will be (2 → 0 1 1).
for M=1, add (0, 1) and (2, 3), and it will be (2 → 1 3 −1).
for M=2, subtract (0, 2) and (3, 3), and it will be (2 → 2 6 −4). Let's repeat what this means: it turned out 2, due to the fact that we subtracted the 2nd minus 6 and −4.
Total, without duplicates, (0, 3) - many, (2 → 0 1 1).
So "lucky" that we got one result. But as a result of the union, there can be a set.
And now the question is: where did we get 2-ku from? We look at (0, 3) and get: 2 = 1 + ₀ 1. We open the left unit through (0, 0), the right one through (1, 3): 2 = 1 + ₀ 2 + ₁ (−1).
It remains to expand −1, and we get 2 = 1 + 2 + 3 − 4.
This can be done recursively.
If the exact computation path is not needed, the associative array is turned into a set without repetitions. Not (2 → 0 1 1), but just 2.
In many variants of dynamic programming, if a forward move is not needed, a two-dimensional cache can be turned into a one-dimensional cache. I don't see a way here. I wrote, but I realized that I was mistaken.
UPD. And what is the difficulty? - I get 2 ⁿ · n². Pretty sure the real figure is less, just thinking about it is a bummer.