Click here to Skip to main content
15,892,537 members
Home / Discussions / C / C++ / MFC
   

C / C++ / MFC

 
GeneralRe: JOB_INFO_2 Time member not set Pin
Blake Miller28-Jul-05 5:23
Blake Miller28-Jul-05 5:23 
GeneralRe: JOB_INFO_2 Time member not set Pin
David Crow28-Jul-05 5:47
David Crow28-Jul-05 5:47 
GeneralRe: JOB_INFO_2 Time member not set Pin
koothkeeper3-Aug-05 5:52
professionalkoothkeeper3-Aug-05 5:52 
Generalwindowsmessage Pin
_tasleem27-Jul-05 13:06
_tasleem27-Jul-05 13:06 
GeneralRe: windowsmessage Pin
John R. Shaw28-Jul-05 5:59
John R. Shaw28-Jul-05 5:59 
Generalextract byte code from string for COM1 Pin
quarry_0627-Jul-05 12:37
quarry_0627-Jul-05 12:37 
GeneralRe: extract byte code from string for COM1 Pin
John R. Shaw28-Jul-05 6:15
John R. Shaw28-Jul-05 6:15 
Question.* and .*? Pin
John R. Shaw27-Jul-05 11:10
John R. Shaw27-Jul-05 11:10 
How does one handle a non-greedy match case ".*?" at the NFA and DFA levels. The problem is that the methods I have come up with, that work for all my test expressions, are greedy. The greedy form ".*" and the non-greedy form ".*?" both produce the same DFA on conversion from NFA to DFA (no surprize there).

Note: I did some searching and discovered that my methods are almost identicle to those specified in computer science courses; in other words, they are all greedy.

Examaple:
Expression: "/\*.*?\*/"
Test input: /*123*//*456*/
Output: /*123*//*456*/

The NFA and DFA simulators produce the same output. The simulators also produce the same output for "/\*.*\*/".
// NFA simulator
template<class T_>
nfamap<T_>::string_size_type
nfamap<T_>::get_match(const string_type& in) const
{
    if( empty() || in.empty() )
        return(0);
#ifdef SHOW_SIMULATOR_PROCESS
    sim_clear();
#endif
#ifdef _DEBUG
    string_type out;
#endif
    string_type::size_type count = 0, final_count = 0;
    state_set_type c_set, m_set;
    m_set.insert(0);
    epsilon_closure(c_set,m_set);
    string_type::const_iterator ii;
    for( ii = in.begin(); ii != in.end(); ++ii )
    {
        if( move(m_set,c_set,*ii,true).empty() )
            break;
        ++count;
#ifdef _DEBUG
        out += *ii;
#endif
        epsilon_closure(c_set,m_set);
        if( c_set.find(final_state_) != c_set.end() )
            final_count = count;
    }
    return(final_count);
}
// DFA simulator
template<class Nfa_>
dfamap<Nfa_>::string_size_type
dfamap<Nfa_>::get_match(const string_type& in) const
{
    assert(this);
    if( in.empty() || empty() )
        return(0);

#ifdef _DEBUG
    string_type out;
#endif
    state_set_type m_set, c_set;    // move set, current set
    c_set.insert(0);

    string_type::size_type count = 0, final_count = 0;
    string_type::const_iterator str_i;
    for( str_i = in.begin(); str_i != in.end(); ++str_i )
    {
        // get set of states reachable by *str_i from states in m_set
        if( match_move(m_set,c_set,*str_i).empty() )
            break;
        ++count;
#ifdef _DEBUG
        out += *str_i;
#endif
        // check if m_set intersects final_set
        state_set_type::const_iterator msi;
        for( msi = m_set.begin(); msi != m_set.end(); ++msi )
        {
            if( final_state(*msi) )
            {
                final_count = count;
                break;
            }
        }
        m_set.swap(c_set);
    }
    return(final_count);
}


Any ideas or articles w/algorithm that may help solve this problem?

I prefer to solve this problem at the NFA/DFA simulator level.

I've already read the articles at CP, GameDev_Net, and several university .pdf files. But none of them covers the non-greedy approach and studying RegEx++, and others, to see how they work, has provided no insights to the solution.

To tell the truth, I do not fully understand how RegEx++ works. Every thing depends on the char_traits and there are some inconsistancies in naming conventions, that serve to confuse understanding.

I do not realy expect anyone to be able to answer this post, but if you have any ideas/solutions; please reply.

Thanks!

INTP
"The more help VB provides VB programmers, the more miserable your life as a C++ programmer becomes."
Andrew W. Troelsen
AnswerRe: .* and .*? Pin
includeh1027-Jul-05 11:55
includeh1027-Jul-05 11:55 
GeneralRe: .* and .*? Pin
John R. Shaw27-Jul-05 12:10
John R. Shaw27-Jul-05 12:10 
GeneralGDI + to save graphics from the screen into a file Pin
flamy27-Jul-05 10:47
flamy27-Jul-05 10:47 
GeneralRe: GDI + to save graphics from the screen into a file Pin
mark novak27-Jul-05 15:04
mark novak27-Jul-05 15:04 
GeneralRe: GDI + to save graphics from the screen into a file Pin
flamy27-Jul-05 15:21
flamy27-Jul-05 15:21 
General'Web' or 'Tree' Display Pin
bugDanny27-Jul-05 10:43
bugDanny27-Jul-05 10:43 
Generaldialog box trouble Pin
DaveHuber27-Jul-05 10:27
DaveHuber27-Jul-05 10:27 
GeneralRe: dialog box trouble Pin
bugDanny27-Jul-05 10:49
bugDanny27-Jul-05 10:49 
GeneralRe: dialog box trouble Pin
DaveHuber28-Jul-05 4:48
DaveHuber28-Jul-05 4:48 
GeneralDriver programming question Pin
JakeTruman27-Jul-05 9:47
JakeTruman27-Jul-05 9:47 
GeneralRe: Driver programming question Pin
Toby Opferman27-Jul-05 14:37
Toby Opferman27-Jul-05 14:37 
GeneralRe: Driver programming question Pin
JakeTruman3-Aug-05 12:01
JakeTruman3-Aug-05 12:01 
QuestionHow to disable the help in VC6 Pin
JWood27-Jul-05 9:22
JWood27-Jul-05 9:22 
AnswerRe: How to disable the help in VC6 Pin
David Crow27-Jul-05 9:45
David Crow27-Jul-05 9:45 
GeneralRe: How to disable the help in VC6 Pin
JWood28-Jul-05 4:57
JWood28-Jul-05 4:57 
AnswerRe: How to disable the help in VC6 Pin
Blake Miller27-Jul-05 12:08
Blake Miller27-Jul-05 12:08 
Generalproblem with multiple defined symbols Pin
Qvicksilver27-Jul-05 9:07
Qvicksilver27-Jul-05 9:07 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.