[ACCEPTED]-Building a computer algebra system-computer-algebra-systems

A really useful next step would be to construct 24 a parse tree:

You'd make one of these by 23 writing an infix parser. You could either 22 do this by writing a simple recursive descent 21 parser, or by bringing in the big guns and 20 using a parser generator. In either case, it helps to construct 19 a formal grammar:

expression: additive

additive: multiplicative ([+-] multiplicative)*

multiplicative: primary ('*' primary)*

primary: variable
       | number
       | '(' expression ')'

Note that this grammar 18 does not handle the 2x syntax, but it should 17 be easy to add.

Notice the clever use of 16 recursion in the grammar rules. primary only captures 15 variables, numbers, and parenthesized expressions, and 14 stops when it runs into an operator. multiplicative parses 13 one or more primary expressions delimited by * signs, but 12 stops when it runs into a + or - sign. additive parses 11 one or more multiplicative expressions delimited by + and 10 -, but stops when it runs into a ). Hence, the 9 recursion scheme determines operator precedence.

It 8 isn't too terribly difficult to implement 7 a predictive parser by hand, as I've done below (see full example at ideone.com):

function parse()
{
    global $tokens;
    reset($tokens);
    $ret = parseExpression();
    if (current($tokens) !== FALSE)
        die("Stray token at end of expression\n");
    return $ret;
}

function popToken()
{
    global $tokens;
    $ret = current($tokens);
    if ($ret !== FALSE)
        next($tokens);
    return $ret;
}

function parseExpression()
{
    return parseAdditive();
}

function parseAdditive()
{
    global $tokens;

    $expr = parseMultiplicative();

    for (;;) {
        $next = current($tokens);
        if ($next !== FALSE && $next->type == "operator" &&
            ($next->op == "+" || $next->op == "-"))
        {
            next($tokens);
            $left = $expr;
            $right = parseMultiplicative();
            $expr = mkOperatorExpr($next->op, $left, $right);
        } else {
            return $expr;
        }
    }
}

function parseMultiplicative()
{
    global $tokens;

    $expr = parsePrimary();

    for (;;) {
        $next = current($tokens);
        if ($next !== FALSE && $next->type == "operator" &&
            $next->op == "*")
        {
            next($tokens);
            $left = $expr;
            $right = parsePrimary();
            $expr = mkOperatorExpr($next->op, $left, $right);
        } else {
            return $expr;
        }
    }
}

function parsePrimary()
{
    $tok = popToken();
    if ($tok === FALSE)
        die("Unexpected end of token list\n");
    if ($tok->type == "variable")
        return mkVariableExpr($tok->name);
    if ($tok->type == "number")
        return mkNumberExpr($tok->value);
    if ($tok->type == "operator" && $tok->op == "(") {
        $ret = parseExpression();
        $tok = popToken();
        if ($tok->type == "operator" && $tok->op == ")")
            return $ret;
        else
            die("Missing end parenthesis\n");
    }

    die("Unexpected $tok->type token\n");
}

Okay, so 6 now you have this lovely parse tree, and 5 even a pretty picture to go with it. Now 4 what? Your goal (for now) might be to simply 3 combine terms to get a result of the form:

n1*a + n2*b + n3*c + n4*d + ...

I'll 2 leave that part to you. Having a parse 1 tree should make things much more straightforward.

PHP is good at strings, numbers, and arrays. But 17 it is a poor language for implementing symbolic 16 formula manipulation, because it has no 15 native machinery for processing "symbolic 14 expressions", for which you really 13 want trees. Yes, you can implement all 12 that machinery. What is harder is to do the algebraic manipulations. Its 11 quite a lot of work if you want do build 10 something semi-sophisticated. Ideally you 9 want machinery to help you write the transformations 8 directly and easily.

For instance, how will 7 you implement arbitrary algebra rules? Associativity 6 and commutativity? Term "matching at 5 a distance"?, e.g.

  (3*a+b)-2(a-b)+a ==> 3a-b

You can look at how 4 a simple CAS can be implemented using our DMS program transformation system. DMS has hard mathematical 3 constructs like commutativity and associativity 2 built in, and you can write algebra rules 1 explicitly to operate on symbolic formulas.

The book Computer Algebra and Symbolic Computation: Mathematical Methods by Joel S. Cohen describes an algorithm for automatic 5 simplification of algebraic expressions.

This 4 algorithm is used in the Symbolism computer algebra 3 library for C#. Going with your example, the 2 following C# program:

var x = new Symbol("x");

(1 + 2 * x - 3 * (4 - 5 * (3 * x)))
    .AlgebraicExpand()
    .Disp();

displays the following 1 at the console:

-11 + 47 * x