Topher Cooper wrote:
Actually the difficulty is "easy". The basic precedence parser could be whipped out in an hour or so. Another day or a bit more to do the interfacing, define the expression data structures, and do the constant folding.
Operators also need associativity, or, more expressively, two precedences -- a left and a right precedence.
You don't really need to specify "allowed variables" any more than you need to specify allowed literals -- if the parser sees a variable it can use it.
Personally I would include templates rather than just an operator string and then depend on the arity to determine the type. Then you can handle ternary and postfix operators.
Topher
On Apr 6, 2010, at 8:01 AM, Stefan wrote:
* A parser capable of evaluating mathematical expressions which contains operands,operators,function calls,variable names and constant names (also considering priority of operators): 1. a list of valid operators described by: a) number of operands (unary/binary/ternary?); b) allowed operand types; c) the precedence (priority of the operator) 2. a list of existent functions described by: a) function name; b) number of parameters; c) type of each parameter and return type; d) a callback (maybe just automatically deduce type based on the callback's type if possible) 3. a list of constants 4. a list of allowed variable names and types
Here's a pseudo-C++ code sample on how it should look like: namespace m = boost::math_expressions_parser; m::parser p; p.add_operators() ('+', 1, ret<int32_t>(_1+_2)) // binary +, precedence 1 ('*', 2, ret<int32_t>(_1*_2)) // binary -, precedence 2 ('+', 3, ret<int32_t>(_1)) // unary +, precedence 3 ('-', 3, ret<int32_t>(-_1)); // unary - (also a funny face), precedence 3 p.add_functions() ("sin", ret<int32_t>(sin(_1))); p.add_constants() ("PI", 3); p.add_allowed_variables() (allowed_var<int32_t>("x"));
m::expression E("1 + 3*sin(PI*x)", p); // evaluates mathematical expression E against parser p if (!E.valid()) { /* ... */ } else { std::cout << E.evaluate( ("x", 3) ); // evaluate this expression by letting x=3 E.let() ("x",4); std::cout << E.evaluate(); } //Maybe an optimization so only the parts that depend on the changed variable will be recalculated every time?. E.g.: for expression f(x)+y, f(x) is recomputed only when x is changed. This may cause problems for functions that do not always yield the same results for the same input. Maybe make this optimization optional, only if the user marks the function/operator as "volatile" or something Difficulty: hard-very hard
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Yes, I apologize. The "hard-very hard" wasn't meant to be there (I only wanted to use very-easy and easy on the difficulty tags initially). This is quite trivial to implement and all the other ideas are. I agree that these alone aren't sufficient for a proposal as they would be all finished in a relatively small amount of time, but I was thinking of implementing some of these in addition to one of the boost's ideas. Also, you have good points on associativity and preferring the use of templates, appreciated. Stefan