fast math expression parser

Ceee4d1295c32a0c1c08a9eae8c9459d
0
v71 105 Oct 15, 2009 at 14:00

This is a code i wrote when i had inspiration from a recent topic about designing languages.
Its a math parser, i am working for adding support for math function and maybe in the future
more advanced like integration and differentiation but this goes outside my main game development interest :P
I would love to know how and if you are using in your pojects, there shouldn’t be any bugs ,
i spent much time working on error detection but something may always slip from hands.

#include "stdafx.h"
#include <string>
#include <iostream>
#include <fstream>
#include <cstdarg>
#include <assert.h>

using namespace std;

/////////////////////////////////////////////////////////////////////////

#define     MAXIDSIZE       256

enum EToken
{
    TEnd,
    TValue,
    TPlus,
    TMinus,
    TMul,
    TDiv,
    TMod,
    TExp,
    TLparen,
    TRparen,
    TAssign,
    TIdent
};

enum EError
{
    ETextExpected,
    EUnknownSymbol,
    EIncompleteExpression,
    EExpectedIdentifierOrNumeric,
    EExpectedParenBalance,
    EExpectedIdentifier,
    EExpcetedNumeric,
    EExpectedLParen,
    EExpectedRParen,
    EIdentifierTooLong
};

//////////////////////////////////////////////////////////////////////////

class CExprParser 
{
    char       *Look;
    double      Value;
    EToken      Token;
    char        Identifier[MAXIDSIZE];

    bool EatSymbol( void )
    {
        
        int Lenght=0;
        
        memset( Identifier,0,sizeof(char)*MAXIDSIZE );

        if ( isalpha( *Look ) || *Look=='_' )
        {

            Token=TIdent;

            do
            {
                Identifier[ Lenght++ ]=*Look;
                
                if ( Lenght>=MAXIDSIZE) 
                    return Error( EIdentifierTooLong );
    
                Look++;
            } 
            while ( isalnum( *Look ) || *Look =='_' );
            
        }
        else
        {
            return false;
        }
        
        return true;
    };

    bool GetNextToken( void )
    {
        
        if ( *Look==NULL )
        {
            Token=TEnd; 
            return true; }

        // Skip over white space.

        while ( isspace( *Look   ) )
            Look++;

        switch ( *Look )
        {
            // check for delimiter

            case '+'  : *Look++ ; Token= TPlus;   break;
            case '-'  : *Look++ ; Token= TMinus;  break;
            case '*'  : *Look++ ; Token= TMul;    break;
            case '/'  : *Look++ ; Token= TDiv;    break;
            case '='  : *Look++ ; Token= TAssign; break;
            case '('  : *Look++ ; Token= TLparen; break;
            case ')'  : *Look++ ; Token= TRparen; break;
            case '%'  : *Look++ ; Token= TMod;    break;
            case '^'  : *Look++ ; Token= TExp;    break;

            // check for numeric

            case '0'  :
            case '1'  :
            case '2'  :
            case '3'  :
            case '4'  :
            case '5'  :
            case '6'  :
            case '7'  :
            case '8'  :
            case '9'  : 
            case '.'  : 
                        //////////////////////////////////////////
                        // eat numeric value

                        char *p;
                        Value=strtod( Look,&p );
                        Look=p;
                        Token=TValue;
                
                        break;

            // end of text

            case '\0' : Token=TEnd;    break;
    
            // check for symbolic

            default   : 
                
                        if ( !EatSymbol() ) 
                            return Error( EUnknownSymbol );

                        Token=TIdent ;

                        break;
        }

        return true;
    }

    bool Error( int err )
    {
        switch ( err )
        {
            case ETextExpected:                 ErrorString="Error: No Text\n";                   break;
            case EIncompleteExpression:         ErrorString="Error: Syntax error\n";          break;  
            case EUnknownSymbol:                ErrorString="Error: Unknown identifier\n" ;       break;
            case EExpectedIdentifierOrNumeric:  ErrorString="Expected Identifier or numeric\n"; break;
            case EExpectedIdentifier:           ErrorString="Expected Identifier\n";          break;
            case EExpcetedNumeric:              ErrorString="Expected numeric\n";             break;
            case EExpectedLParen:               ErrorString="Error: expected '('";                break;
            case EExpectedRParen:               ErrorString="Error: expected ')'";                break;
            case EExpectedParenBalance:         ErrorString="Error: Parenthesys unbalanced\n";  break;
            case EIdentifierTooLong :           ErrorString="Error: Identifier too long\n";       break;  
        };
        return false;
    }
    
    bool VerifyParenthesysBalance( void )
    {
        int count=0;
    
        char *ptr;
        
        ptr=Look;

        do
        {
            if ( *ptr=='(' ) count++;
                else 
                    if ( *ptr==')' ) count--;
        
            ptr++;
        }
        while ( *ptr!=0 ) ;

        return ( count==0 ) ;
    }
    
    bool Factor ( double &c )
    {
        if ( Token==TValue )
        {
            c=Value;
        }
        else if ( Token==TMinus )
        {
            if ( GetNextToken()==false )
                return false;

            if ( Token==TValue )
                c=-Value;

            else if ( Token==TLparen )
            {
                double b;
                
                if ( GetNextToken()==false )
                    return false;
                
                Expr( b  );

                c=-b;

                if ( Token!=TRparen && Token!=TEnd )
                    return Error( EExpectedRParen  );

            }
            else
            {
                return Error( EIncompleteExpression );
            }
        }
        else if ( Token==TPlus )
        {
            if ( GetNextToken()==false )
                return false;
        
            if ( Token==TValue )
                c=Value;

            else if ( Token==TLparen )
            {
                double b;
                
                if ( GetNextToken()==false )
                    return false;

                Expr( b  );

                c=b;

                if ( Token!=TRparen && Token!=TEnd )
                    return Error( EExpectedRParen  );

            }
            else
            {
                return Error( EIncompleteExpression );
            }

        }
        else if ( Token==TLparen )
        {
            double b;

            if ( GetNextToken()==false )
                return false;
            
            Expr( b  );

            c=b;
            
            if ( Token!=TRparen && Token!=TEnd )
                return Error( EExpectedRParen  );

        }
        else if ( Token==TRparen )
        {
            // () condition, no value returned
            c=0.0f;
            return true;
        }
        else if ( Token==TEnd )
        {
            return Error( EIncompleteExpression );
        }

        else 
        {
            return Error( EUnknownSymbol );
        }
        
        return true;
    }

    bool Term ( double &c )
    {
        double b;

        if ( Factor( c )==false ) 
            return false;

        if ( GetNextToken()==false )
            return false;

        while ( Token==TMul || Token==TDiv )
        {

            if ( Token==TMul )
            {
                if ( GetNextToken()==false )
                    return false;

                if ( Factor ( b )==false )
                    return false;

                c*=b;
            }
            else if ( Token==TDiv )
                {
                    if ( GetNextToken()==false )
                        return false;

                    if ( Factor ( b )==false )
                        return false;

                    c/=b;
                    
                }
    
            if ( GetNextToken()==false )
                return false;
        }
        
        return true;
    }
         
    bool Expr( double &c )
    {
    
        double b;

        if ( Term ( c )==false )
            return false;

        while ( Token==TPlus || Token==TMinus )
        {

            if ( Token == TPlus )
            {
                if ( GetNextToken()==false )
                    return false;

                if ( Term( b )==false )
                    return false;

                c+=b;
            }
            else if ( Token == TMinus )
            {
                if ( GetNextToken()==false )
                    return false;
                
                if ( Term( b )==false )
                    return false;

                c-=b;
            }
            
            if ( Token!=TPlus   && 
                 Token!=TMinus  && 
                 Token!=TRparen && 
                 Token!=TEnd )
                {
                    return Error( EIncompleteExpression );
                }       
        }

        return true;
    }

    public :

    bool Parse( char *text )
    {
        if ( text==NULL )
            return  Error( ETextExpected ) ;

        double result;

        Look=text;

        Token=TEnd;

        Value=0.0f;

        if ( VerifyParenthesysBalance()==false )
             return Error(EExpectedParenBalance);
    
        GetNextToken();

        Expr( result  );

        cout << result << endl;

        return true;

    }

    //////////////////////////////////

    string      ErrorString;

    CExprParser()
    {
        Value=0.0f;
        Look=NULL;  
    };

   ~CExprParser()
    {
    };

};


//////////////////////////////////////////////////////////////////////////

int _tmain( )
{

    string text=" 2 + 3 - 2*( 3+2 )*4 ";

    cout << "Parsing : " << text << endl << endl;

    CExprParser parser;

    parser.Parse( &text[0] );
 
    cout << parser.ErrorString << endl;

    cin.get();

    return 0;
}

30 Replies

Please log in or register to post a reply.

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Oct 16, 2009 at 08:51

Nice, a recursive descent parser. It could be simpler though, by using Dijkstra’s Shunting Yard algorithm.

Btw, it’s parantheses, not paranthesys :)

Ceee4d1295c32a0c1c08a9eae8c9459d
0
v71 105 Oct 16, 2009 at 09:56

Sorry english is not my native language

17ba6d8b7ba3b6d82970a7bbba71a6de
0
vrnunes 102 Oct 16, 2009 at 21:33

Oh interesting, I wrote an expression parser only a month ago. I implemented the Reverse Polish Notation algorithm, though. It was used on a proprietary bytecode language for a specific system I’m involved (I got to develop the custom language…).

Ceee4d1295c32a0c1c08a9eae8c9459d
0
v71 105 Oct 16, 2009 at 21:58

…i was expecting harsh comments…

A0c9c0649c5deacc0ae3b7f7721c94d2
0
starstutter 101 Oct 17, 2009 at 21:47

oh wow, this could actually be very useful for something like an in-game console. Nice work.

…i was expecting harsh comments…

Are you disappointed? :P

Ceee4d1295c32a0c1c08a9eae8c9459d
0
v71 105 Oct 18, 2009 at 08:45

i forget that i am not anymore in gamedev comunity :P

A0c9c0649c5deacc0ae3b7f7721c94d2
0
starstutter 101 Oct 18, 2009 at 15:24

@v71

i forget that i am not anymore in gamedev comunity :P

yep, that’s what I thought XD
Do a good job there = flamed

Fd80f81596aa1cf809ceb1c2077e190b
0
rouncer 104 Oct 19, 2009 at 02:23

This is also good if you want to use interpreted ai in your game, with real arithmetic calculations interpreted on the fly…

6837d514b487de395be51432d9cdd078
0
TheNut 179 Oct 19, 2009 at 02:59

Cool stuff, I thought about doing something like this a while back (though more like using someone else’s library ;)

For benchmarking purposes, here are my results:

Core 2 Duo 1.8GHz, optimized release build VS 2008

100000 Tests.

Parsing : 2 + 3 - 2 * (3 + 2) * 4 = -35
Test 1: 250 milliseconds. Result = -35
Test 2: 266 milliseconds. Result = -35
Test 3: 265 milliseconds. Result = -35
Test 4: 250 milliseconds. Result = -35
Test 5: 250 milliseconds. Result = -35

Parsing : ((1 + (2 / 3)) * 0.5) + 0.1666666 = 1
Test 1: 312 milliseconds. Result = 1
Test 2: 313 milliseconds. Result = 1
Test 3: 297 milliseconds. Result = 1
Test 4: 297 milliseconds. Result = 1
Test 5: 313 milliseconds. Result = 1

Ceee4d1295c32a0c1c08a9eae8c9459d
0
v71 105 Oct 19, 2009 at 07:37

It could be speeded up a little putting the term function inside the expr function, but it would be a nightmare for readability.

6837d514b487de395be51432d9cdd078
0
TheNut 179 Oct 19, 2009 at 10:18

Readability and performance usually don’t see eye to eye ;) But I think these results are not bad considering the flexibility here, which is more important.

B7568a7d781a2ebebe3fa176215ae667
0
Wernaeh 101 Oct 19, 2009 at 10:38

but it would be a nightmare for readability

If you really want to see a nightmare for readability, try adding a manual follow-set based error recovery to your expression parser. I had to do this for an university assignment once. It was not nice.

Good work with the parser, though :)
Guess this is a piece of code one can reuse over and over again.
Cheers,
- Wernaeh

886c9946a5dd9887a33d237ddcc9b7e7
0
phresnel 101 Oct 22, 2009 at 15:01

@starstutter

yep, that’s what I thought XD
Do a good job there = flamed

Uhm, if I look at http://www.gamedev.net/community/forums/viewposts.asp?ID=8836&RestrictTo=Replies, then three years later http://www.gamedev.net/community/forums/viewposts.asp?ID=122861&RestrictTo=Replies under ban evasion, then I wonder what good stuff that would be in that case.

Anyways, Vincenzo, so far that’s good work.

Let me analyze your code syntactically/cosmetically only for now:

#include "stdafx.h"

MSVC only.

using namespace std;

Dirty, not good practice.

Lenght

Typo: “Length”.

#define     MAXIDSIZE       256

Hardcoded maximum size. Not good practice, error prone.

bool EatSymbol( void )

Putting “void” there is C practice, but is uncommon C++ practice.

if ( GetNextToken()==false )

Explitly comparing against boolean literals is uncommon and redundant. Just write “if (!GetNextToken())”, which many programmers will also find more readable.

NULL

Not standard C++ but MSVC++. Use the literal “0” instead.

CExprParser()
    {
        Value=0.0f;
        Look=NULL;  
    };

You might want to initialize instead of assign to your members: “CExprParser() : Value(0.0f), Look(0)”.

bool Parse( char *text )

If you don’t plan to modify the passed string, then use “const char *text”. See also http://www.parashift.com/c++-faq-lite/const-correctness.html about const correct code.

int _tmain( )

In standard C++, we say “int main ()”, “_tmain()” is MSVC++ again.

parser.Parse( &text[0] );

Undefined behaviour.

21.3.4 basic_string element access [lib.string.access]

const_reference operator[](size_type pos) const;
reference operator[](size_type pos);

1 Returns: If pos < size(), returns data()[pos]. Otherwise, if pos == size(), the const version returns charT(). Otherwise, the behavior is undefined.

Better use text.c_str():

21.3.6 basic_string string operations [lib.string.ops]

const charT* c_str() const;

1 Returns: A pointer to the initial element of an array of length size() + 1 whose first size() elements equal the corresponding elements of the string controlled by *this and whose last element is a null character specified by charT().

The internal representation of std::string that you are dissecting does not have a \0 (null character).

cin.get();

What if your program is run in non-interactive mode?

edit: I forgot about your list of #includes:

//#include "stdafx.h" //! why?
#include <string>
#include <iostream>
//#include <fstream> //! why?
//#include <cstdarg> //! why?
#include <cassert> //! assert.h is for C
#include <cstring> //! was missing, needed for memset()
#include <cstdlib> //! was missing, needed for strtod()

edit: Another issue:

c/=b;

Here you should catch a division by zero before it happens, otherwise your program yields undefined behaviour (cf. ISO/IEC 14882:2003(E), Section 5 Expressions:

If during the evaluation of an expression, the result is not mathematically defined or not in the range of representable values for its type, the behavior is undefined

).

2b97deded6213469bcd87b65cce5d014
0
Mihail121 102 Oct 22, 2009 at 15:51

@phresnel

Thanks for the great introduction to the C++ standard, freely available to all interested, but I hope you are aware of the difference between prototyping something fast and getting a stable, clear code to the market for cash that adheres to the specs and would justify the countless hours of reading the standard. Moreover there are tools for that… I actually can’t believe you waste as much time writing here than he probably needed to develop the code, which is not that bad at all. Never used includes? Who cares…

886c9946a5dd9887a33d237ddcc9b7e7
0
phresnel 101 Oct 22, 2009 at 16:14

@Mihail121

Thanks for the great introduction to the C++ standard, but I hope you are aware of the difference between prototyping something fast and releasing a stable, clear code that adheres to the specification and follows design guidelines.

I posted a more-than-1-line-critique for a buggy program, and tried to give some hints to make it less bug-full and well-formed. I think it actually helps the OP, because he stated that he thinks that

there shouldn’t be any bugs

.

Moreover there are tools for that…

Tools for what? I wrote more than one point.

Anyways: What you say is “learn unportable c++ that yields undefined behaviour and trust 3rd parties to fix that for you” :worthy:

I actually can’t believe you waste as much time writing here than he probably needed to develop the code, which is not that bad at all. Not used includes? Who cares…

Not so much, just 25 Minutes (=roughly 0.00006 % percent of an average 73 year human life), which I hope will help v71 to learn C++ better and improve his program. What is wrong with investing some spare time to write a proper post?

See also starstutters second post which might be interesting.

2b97deded6213469bcd87b65cce5d014
0
Mihail121 102 Oct 22, 2009 at 16:19

@phresnel

….

Not flamming you for anything, it’s evident you are proficient with the specification, it’s completely fine to provide help, it’s fine to reveal bugs, it’s just that my personal belief that the point of the post is to show a quick parser and nothing more. But I’m just being ignorant, most honestly your post was fully ok, sorry. Let’s not start an off-topic war.

P.S.

What you say is “learn unportable c++ that yields undefined behaviour and trust 3rd parties to fix that for you”

No, that’s not what I’ve said, contact me on ICQ\Skype and I’ll explain it in German :)

886c9946a5dd9887a33d237ddcc9b7e7
0
phresnel 101 Oct 22, 2009 at 16:55

@Mihail121

Not flamming you for anything, it’s evident you are proficient with the specification, it’s completely fine to provide help, it’s fine to reveal bugs, it’s just that my personal belief that the point of the post is to show a quick parser and nothing more. But I’m just being ignorant, most honestly your post was fully ok, sorry.

If my first post was a tad too offensive in some point, then I am sorry, that was not my intention. But yes, I am guilty of prosecuting not to write unportable code, and probably go into too much detail sometimes.

On the other hand, I also highly welcome other peoples critique on me or my stuff, e.g. once I release picogen 0.3, I’d be happy if people point out bugs or otherwise bad/dumb code that I did not recognize. Because once written, the probability is pretty high that I’ll never fix some subtleties that really needed to be.

Let’s not start an off-topic war.

Amen :D

Ceee4d1295c32a0c1c08a9eae8c9459d
0
v71 105 Oct 22, 2009 at 16:59

Thanks for your dissection, i will work to fix those ‘bugs’
why posting a 3 years old rants from gamedev ? how did you know my name ?

why is using namespace std , dirty ?????

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Oct 22, 2009 at 18:37

@phresnel

#include "stdafx.h"

MSVC only.

Nonsense. Naming a header ‘stdafx.h’ is by no means MSVC only. There is no standard stdafx.h header in MSVC++. It’s a user-defined header, usually containing precompiled stuff. Probably just a result of copypasting his code out of his project. There’s nothing wrong with it, and there’s nothing unportable about it.

using namespace std;

Dirty, not good practice.

In a header, yes. In a sourcefile everybody should decide for himself. All names in de std namespace are defined by the standard. Other symbols in the std namespace provided by the implementation should follow reserved names rules (start with a underscore followed by a capital letter, or contain double underscores), so accidental name clashes shouldn’t happen.

NULL

Not standard C++ but MSVC++. Use the literal “0” instead.

Again, nonsense. According to ISO/IEC 14882:2003, paragraph C.2.2.3/1:

The macro NULL, defined in any of <clocale>, <cstddef>, <cstdio>, <cstdlib>, <cstring>, <ctime>, or <cwchar>, is an implementation-defined C++ null pointer constant in this International Standard (18.1).

#include <cassert> //! assert.h is for C

Oh, then what is the C++ counterpart of assert()?

886c9946a5dd9887a33d237ddcc9b7e7
0
phresnel 101 Oct 22, 2009 at 19:53

@.oisyn

Nonsense. Naming a header ‘stdafx.h’ […]’s nothing unportable about it.

Nitpicky, yes. But only in this case. When code is published that #includes unpublished blackboxes, then
a) (the “mild” form) it might not compile at all
b) (the “evil” form) intended behaviour and actual behaviour might largely vary. Think of #define macros, function overloads, template partial and explicit specializations, et al.

Where is the portability when a) or b) strike?

In a header, yes. In a sourcefile everybody should decide for himself.

In my opinion, blanket using statements should never exceed function scope. Scope should (imho) be as big as needed, but not bigger.

All names in de std namespace are defined by the standard.

And as the standard does not define which names may be defined outside “de std namespace”, those pulled-in names may very well collide with your code. Sooner or later, with or without tweaking the sourcefile in question.

revision 0:
foo.hh:

#ifndef FOO_HH
#define FOO_HH
#endif

bar.cc:

#include <string>
using namespace std;
#include "foo.hh"
class list {};
int main () {
    list frogs;
}

revision 2048:
foo.hh:

#ifndef FOO_HH
#define FOO_HH
#include <list>
#endif

Example consequence (note: bar.cc was never changed anymore!):

main.cc: In function 'int main()':
main.cc:10: error: reference to 'list' is ambiguous
main.cc:6: error: candidates are: class list
/usr/include/c++/4.3/bits/stl_list.h:416: error:                 template<class _Tp, class _Alloc> class std::list
main.cc:10: error: reference to 'list' is ambiguous
main.cc:6: error: candidates are: class list
/usr/include/c++/4.3/bits/stl_list.h:416: error:                 template<class _Tp, class _Alloc> class std::list
main.cc:10: error: expected `;' before 'frogs'

Again, nonsense. According to ISO/IEC 14882:2003, paragraph C.2.2.3/1:

The macro NULL, defined in any of <clocale>, <cstddef>, <cstdio>, <cstdlib>, <cstring>, <ctime>, or <cwchar>, is an implementation-defined C++ null pointer constant in this International Standard (18.1).

int main () {
        int *p;
        if (NULL == p) {
        }
}

main.cc: In function 'int main()':
main.cc:3: error: 'NULL' was not declared in this scope

I am not sure whether I shall now dive into all my source code files and pull in unrelated #include files just to have NULL defined, or just follow the well established and less redundant convention of using a builtin literal that also happens to be portable.

Oh, then what is the C++ counterpart of assert()?

The macro assert(). Why?

Anyways, it is good practice to use the C++ counterparts of the C library where available. E.g., math.h defines cos and cosf, whereas cmath only defines the function name cos with three function overloads, thus reducing redundancy, improving readability of template code, helping to avoid the subtle issues when accidentally using 64bit floating point where only 32bit floating point is intended. There are some more less than irrelevant differences.

cassert and assert.h are the same, but why make an exception to the rule for only the assert macro?

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Oct 22, 2009 at 21:13

@phresnel

Nitpicky, yes.

No, just wrong. “stdafx.h” is by no means “MSVC++ only”

In my opinion, blanket using statements should never exceed function scope. Scope should (imho) be as big as needed, but not bigger.

I agree with you on this, but the point is that it is not wrong or evil to do otherwise (as opposed to putting a using directive in a header, which *is* evil). It’s just a matter of taste.

And as the standard does not define which names may be defined outside “de std namespace”, those pulled-in names may very well collide with your code. Sooner or later, with or without tweaking the sourcefile in question.

And some think that you shouldn’t use those names in the first place to avoid confusion. This is especially true for functions, due to the two phase name lookup in templates.
and obviously I meant “the” std namespace ;)

int main () {
        int *p;
        if (NULL == p) {
        }
}

main.cc: In function int main():
main.cc:3: error: NULL was not declared in this scope

I am not sure whether I shall now dive into all my source code files and pull in unrelated #include files just to have NULL defined, or just follow the well established and less redundant convention of using a builtin literal that also happens to be portable.

That is besides the point. NULL is not C only. It is just as well C++, and pulling in a header for a language construct is nothing strange (see typeid()). And some think using NULL makes the code more readable. Of course, it has other problems as well (the 0 literal has these as well, but would make these more evident to the programmer), but that will be fixed with nullptr, in which case we will al be using ‘nullptr’ rather than ‘0’.

The macro assert(). Why?

I’m sorry, I misread your comment. I thought you said you didn’t need <cassert> as assert() is not C++, but I see now that you meant that you should include <cassert> rather than <assert.h>. Of course I can do nothing other than to agree on that :)

6837d514b487de395be51432d9cdd078
0
TheNut 179 Oct 23, 2009 at 02:01

Man, you guys need to get out more :lol:

886c9946a5dd9887a33d237ddcc9b7e7
0
phresnel 101 Oct 23, 2009 at 08:35

@.oisyn

No, just wrong. “stdafx.h” is by no means “MSVC++ only”

Oops, okay. My intention was more to tell about #including unknown code, rather than to complain about what was MSVC once. Bad wording from my side.

I agree with you on this, but the point is that it is not wrong or evil to do otherwise (as opposed to putting a using directive in a header, which *is* evil). It’s just a matter of taste.

Okay. My taste is to pollute namespaces and scope as sparse as possible. I think it makes my code more “future compatible”.

And some think that you shouldn’t use those names in the first place to avoid confusion.

But then the problem is that only the fewest know which words are reserved for the standard (I don’t belong to them), and it doesn’t help that every decade a plethora of new words are reserved. Especially the upcoming standard will describe a lot of new names, of which are some pretty common in some C++ milieus (e.g. I’ve seen several different mt19937 in the one or another path tracer implementation; I can only hope they [and me] did not use using namespace, as C++0x describes that name [for kicks, g++-4.4 -std=c++0x, header should be <random>], and many, many others).

That is besides the point. NULL is not C only. It is just as well C++, and pulling in a header for a language construct is nothing strange (see typeid()). And some think using NULL makes the code more readable. Of course, it has other problems as well (the 0 literal has these as well, but would make these more evident to the programmer), but that will be fixed with nullptr, in which case we will al be using ‘nullptr’ rather than ‘0’.

That’s right. Though I think 0 vs. pointers is evident enough. I personally consider typeid() and NULL a bit, uhm, dirty, for you must include headers for them (in that respect, I find typeid() even dirtier -> typeid()=first class operator, but “return value” of it needs header :wacko: ). Okay, personal opinion.

@TheNut

Man, you guys need to get out more

Where, …, there are people? :ohmy:

joke aside, actually I have a significant other, enjoy pubs, and from time to time go for a walk: http://phresnel.deviantart.com/

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Oct 23, 2009 at 09:15

@TheNut

Man, you guys need to get out more ;)

duty\_calls.png

:)

36b416ed76cbaff49c8f6b7511458883
0
poita 101 Oct 24, 2009 at 02:41

Cool code, thanks for sharing. Recursive decent parsers are always fun.

Personally, I would change the interface of Parse to be:

const bool Parse(string::iterator first, string::iterator last)

or even better

template <class InputIter>
const bool Parse(InputIter first, InputIter last)

This interface is more flexible, allowing people to parse substrings, or even lists of chars.

Ceee4d1295c32a0c1c08a9eae8c9459d
0
v71 105 Oct 24, 2009 at 07:32

Thanks for the hint, i am working for adding the \^ operator which i included but not added to the parser, and corrected the code to be more oop compliant, further more i would like to add math functions and the derivatie and integral operator, when its finished i will post it here again.

B7109317066ddd5327cb0674388c4974
0
Luz_Reyes 101 Aug 27, 2010 at 22:08

Oisyn that is hilarious! you are spot on, but sometimes i’ve been on both sides of that cartoon’s computer scree, both correcting ppl and being corrected.

Ceee4d1295c32a0c1c08a9eae8c9459d
0
v71 105 Aug 28, 2010 at 08:58

I just want to point ouy that all those posts on gamedev were posted while i was away and someone used my account, only now taht i have seen this old post again i realized what the sarcasm was…

Ee48f6b8883b99a7c93e41220e6444f5
0
happyuk 101 Oct 16, 2013 at 22:09

Lovely article.

For your information, I have also implemented Java expression parsers (in addition to C++) to convert expressions into reverse Polish notation and evaulate the result. Some free downloads can be found at this link.:

http://www.technical-recipes.com/2011/a-mathematical-expression-parser-in-java-and-cpp/

Comments and suggestions much appreciated.

Andy

B5262118b588a5a420230bfbef4a2cdf
0
Stainless 151 Oct 17, 2013 at 09:40

Man you need Forth for this

VARIABLE 'EXPRESSION : EXPRESSION 'EXPRESSION @EXECUTE ;
VARIABLE TEMP CREATE )
: ,C ( a) 2- , ;
: NEXT ( - a) -' IF NUMBER TEMP ! 0 ELSE DROP THEN ;
: CHECK ( a a') - ABORT" not matched" ;
: FACTOR ( a - a') DUP ['] ( = IF DROP NEXT EXPRESSION
['] ) CHECK ELSE ?DUP IF ,C
ELSE TEMP @ [COMPILE] LITERAL THEN THEN NEXT ;    : TERM ( a - a') FACTOR BEGIN DUP ['] * = OVER ['] / =
OR WHILE NEXT FACTOR SWAP ,C REPEAT ;
: EXPRESSION ( a - a') TERM BEGIN DUP ['] + = OVER ['] - =
OR WHILE NEXT TERM SWAP ,C REPEAT ;
: INFIX NEXT ['] ( CHECK NEXT EXPRESSION ['] ) CHECK ;
IMMEDIATE ' EXPRESSION 'EXPRESSION !

LOL

Example of use:

44 CONSTANT FRED
: TEST ( -- n ) INFIX ( 3 * FRED / ( ( 3 + 5 ) / 2 ) ) ;