I have a program with 3 functions: a, b and c.
The user will input a string which will dertimin an order of execution for these functions.
so if the user inputs "abc" it will execute a then b then c. (abc)
If the input is "b4ca" then the execution order will be bcccca.
If the user inputs 3c2(ab) the order will be: cccabab.
You get the idea... There is no limit to the complexity of the input.
I'm having trouble with the logic for analysing the input. I came up with the following solution.
Parse this input into a binary tree, to get the following:
(Each leaf node is either a digit or a string)Code:3c5(ab2(ac)) / \ 3c 5(ab2(ac)) / \ / \ 3 c 5 ab2(ac) / \ ab 2(ac) / \ 2 ac
Then follow the following procedure.
Run through each leaf node pair, and "multiply" the string node by the digit node.
Look at the node adjacent to the parent node, if the node is a string, concatenate with the last pattern, else "multiply" the last node by the digit.
Loop until root node is reached.
As far as I can tell, this will give me the correct order of execution (cccabacacabacacabacacabacacabacacabacac).
The problem is that it only works if input pattern is nesting in that way. So the above algorithm would fail for an input such as "2(4(ab)7(bc))". It would also fail if the patten was "3c5(2(ac)ab))" (which is the same input as the the one in my example algorithm, just with different ordering within the brackets).
I think I can avoid the problem with parallel sets of nested brackets by checking which brackets have parallel nested brackets. The applying the above procedure on the parallel brackets and swaping them back into the original pattern. But this seems very inelegant.
So my question is: Has anyone got any ideas as to what the best approach to this problem is?