Thread: Some logic help please

Hello,

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.

Input: "3c5(ab2(ac))"

Parse this input into a binary tree, to get the following:

Code:

  3c5(ab2(ac))
     /   \
  3c     5(ab2(ac))
 /  \      /   \
3    c    5     ab2(ac)
                  /  \
                ab   2(ac)
                      /  \
                     2   ac

(Each leaf node is either a digit or a string)
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?

Cheers.

Thank you both for your suggestions. But I have found a simple solution. (Well, whether it will be simpler to implement in C++ remains to be seen).

Basically it requires two regular expressions and two while loops (at most):

input = ab3(c4(ba3(ac))ab)b

While input contains brakets
match digit-then-bracket pair
replace matched pattern with n*content matched in brackets (n = digit preceding bracket pair)
loop next

while input contains digits
match digit-character pairs
replace matched pattern witn n*character (n = digit preceding character)

(this is obviously worst case scenario, as pattern may not contain brakets or digits)

And this will give the execution order. I've already mocked up a quick-and-dirty implementation of this algorithm in another language with native regexp support.

Does C++ support regular expressions?

Cheers

Ah thank you.

May I ask a simple, unrelated question?

I'm only able to make console apps atm. Why is it that when I use std::cout<<"whatever"; the text gets displayed in the console window then the console immediately closes?

I have to write std::cin.get(); for the console to remain open after the text is outputted.

You'd think that a program would stay open until it's closed?!

Thank you all for your help.

Yeah actually, if main() is "running" my program then it makes sense that the program is terminated when I return 0.