Some logic help please

This is a discussion on Some logic help please within the C++ Programming forums, part of the General Programming Boards category; Hello, I have a program with 3 functions: a, b and c. The user will input a string which will ...

  1. #1
    Registered User
    Join Date
    Feb 2008
    Posts
    10

    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.

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I think a task such as this calls for a stack and/or recursive matching of brackets.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,167
    What I can think of is trying to parse the expression and for every number, it will push X number of that function to the stack. If ( is encountered, then extract the whole text within ( and ) and do recursive loops to parse and execute them.
    Then you can just pop the stack and execute all that.
    Could also work with a vector, of course...
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
    For information on how to enable C++11 on your compiler, look here.
    よく聞くがいい!私は天才だからね! ^_^

  4. #4
    Registered User
    Join Date
    Feb 2008
    Posts
    10
    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

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,958
    Does C++ support regular expressions?
    There is currently no regular expression support in the standard library, but you may be able to use the one from Boost or from PCRE.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Registered User
    Join Date
    Feb 2008
    Posts
    10
    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.

  7. #7
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,167
    Because that's just how Windows works. All console apps are terminated upon exit.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
    For information on how to enable C++11 on your compiler, look here.
    よく聞くがいい!私は天才だからね! ^_^

  8. #8
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,424
    Quote Originally Posted by Herz View Post
    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 may want to read the following FAQ entry
    http://faq.cprogramming.com/cgi-bin/...&id=1043284385
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  9. #9
    Registered User
    Join Date
    Feb 2008
    Posts
    10
    You'd think that a program would stay open until it's closed?!

    Thank you all for your help.

  10. #10
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,167
    No, it won't. All programs terminate when they reach the exit. The "console" is just a window and disappears, just as all others windows, when the application exits.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
    For information on how to enable C++11 on your compiler, look here.
    よく聞くがいい!私は天才だからね! ^_^

  11. #11
    Registered User
    Join Date
    Feb 2008
    Posts
    10
    Yeah actually, if main() is "running" my program then it makes sense that the program is terminated when I return 0.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Digital Logic
    By strokebow in forum Tech Board
    Replies: 3
    Last Post: 12-09-2006, 12:05 PM
  2. Logic
    By LordBronz in forum C++ Programming
    Replies: 6
    Last Post: 05-23-2006, 05:41 PM
  3. Actors, cues, event based logic.
    By Shamino in forum Game Programming
    Replies: 2
    Last Post: 04-27-2006, 10:58 PM
  4. Circular Logic
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 10-15-2001, 08:10 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21