Kay Schluehr <kay.schluehr <at> gmx.net> writes:
> Now lets drop the assumption that a and b commute. More general: let be
> M a set of expressions and X a subset of M where each element of X
> commutes with each element of M: how can a product with factors in M be
> evaluated/simplified under the condition of additional information X?
> It would be interesting to examine some sorting algorithms on factor
> lists with constrained item transpositions. Any suggestions?
I don't think that sorting is the answer here.
Firts of all IMHO you have to add an
additional constraint - associativity of the operation in question
So the problem could be reduced to making the constant
parts be more associative than the non-constant parts.
which you should be able to
do with a parser. The BNF grammar could look like this:
expr ::= v_expr "*" v_expr | v_expr
v_expr ::= variable | c_expr
c_expr ::= l_expr "*" literal | l_expr
l_expr ::= literal | "(" expr ")"
The trick is to create a stronger-binding multiplication operator on constants
than on mixed
This grammar is ambigue of course - so a LL(k) or maybe even LALR won't work.
But earley's method
implemented in spark should do the trick.
If I find the time, I'll write an short implementation