🔒 Locked

math expressions

Started by OleKaiwalker Apr 13, 2006 at 4:24 AM 3 replies 850+ views

Original Post

Apr 13, 2006 at 4:24 AM

hey there, a keen and fairly simple way to handle mathematical expressions? i'm not looking for anything to evaluate functions, just a parser which also handles parentheses and so on? Anyone with a good idea?

haegarr

Apr 13, 2006 at 4:35 AM

There was a thread about free parsers just yesterday or the day before.... ah, here:
http://www.gamedev.net/community/forums/topic.asp?topic_id=386780

If you want to do it (halfway) yourself: You could try to use simply parseable formats like UPN (avoiding braces). Or use flex/bison (lex/yacc). Also try using the search form above. There are already some discussions about that issue.

However, how to write a parser depends a bit on the language paradigm. Do you use OOP? Which language?

In general a tree is build of a math expression, where the nodes represent an operator/function, and the branches refer to the argument nodes. Leafes are of course literal constants.

Aardvajk

Apr 13, 2006 at 5:30 AM

If you can get hold of a copy of Stroustrup's The C++ Programming Lanugaue (any version) it has the most elegant and comprehensible calculator example I've ever seen.

If we assume a scanner already with a get_token function, a token_type and a token_value (for when a number is scanned), something like

int norm(bool get){    int v=term(get);    while(true)        {        switch(token_type)            {            case PLUS: v+=term(true); break;            case MINUS: v-=term(true); break;                        default: return v;            }        }}int term(bool get){    int v=prim(get);    while(true)        {        switch(token_type)            {            case MULTIPLY: v*=prim(true); break;            case DIVIDE: v/=prim(true); break;                        default: return v;            }        }}int prim(bool get){    if(get) get_token(); int v;    switch(token_type)        {        case NUMBER: v=token_value; get_token(); return v;                case LEFT_BRACKET: v=norm(true); assert(token_type=RIGHT_BRACKET);                           get_token(); return v;        default: syntax_error(); return 0;        }}

This is from memory. Basic idea is that after each construct is scanned and handled, the scanner is left with the next token in it. You can then just call

value=norm(true);

from wherever to get the value of the expression and leave the scanner ready to handle the next expression.

HTH. Sorry a bit complicated but this is a complex subject.

Troll

Apr 13, 2006 at 12:59 PM

You should also check out Boost.Spirit. It comes with 8 different calculator examples, a few of which are impressively concise and readable. Here's one:

struct calc_closure : boost::spirit::closure<calc_closure, double>{    member1 val;};struct calculator : public grammar<calculator, calc_closure::context_t>{    template <typename ScannerT>    struct definition    {        definition(calculator const& self)        {            top = expression[self.val = arg1];            expression                =   term[expression.val = arg1]                    >> *(   ('+' >> term[expression.val += arg1])                        |   ('-' >> term[expression.val -= arg1])                        )                ;            term                =   factor[term.val = arg1]                    >> *(   ('*' >> factor[term.val *= arg1])                        |   ('/' >> factor[term.val /= arg1])                        )                ;            factor                =   ureal_p[factor.val = arg1]                |   '(' >> expression[factor.val = arg1] >> ')'                |   ('-' >> factor[factor.val = -arg1])                |   ('+' >> factor[factor.val = arg1])                ;        }        typedef rule<ScannerT, calc_closure::context_t> rule_t;        rule_t expression, term, factor;        rule<ScannerT> top;        rule<ScannerT> const&        start() const { return top; }    };};

King of Men

Apr 13, 2006 at 1:17 PM

The simplest possible way to do this is to write your own LISP interpreter. [grin]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.