<?php
// This file is part of Moodle - http://moodle.org/
//
// Moodle is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// Moodle is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with Moodle.  If not, see <http://www.gnu.org/licenses/>.

// Parser code for the Moodle Algebra question type
// Moodle algebra question type class
// Author: Roger Moore <rwmoore 'at' ualberta.ca>
// License: GNU Public License version 3.

defined('MOODLE_INTERNAL') || die();

/**
 * Helper function which will compare two strings using their length only.
 *
 * This function is intended for use in sorting arrays of strings by their string
 * length. This is used to order arrays for regular expressions so that the longest
 * expressions are checked first.
 * In this version, if both strings have equal length, string order is used. So this
 * version of the sort is stable.
 *
 * @param $a first string to compare
 * @param $b second string to compare
 * @return -1 if $a is longer than $b,  and +1 if $a is shorter
 */
function qtype_algebra_parser_strlen_sort($a, $b) {
    // Get the two string lengths once so we don't have to repeat the function call.
    $alen = strlen($a);
    $blen = strlen($b);
    // If the two lengths are equal use strings order.
    if ($alen == $blen) {
        return ($a > $b) ? -1 : +1;
    }
    // Otherwise return +1 if a is shorter or -1 if longer.
    return ($alen > $blen) ? -1 : +1;
}

/**
 * Base class for all the types of exception we throw.
 */
class parser_exception extends moodle_exception {
    public function __construct($error) {
        parent::__construct('exceptionmessage', 'qtype_algebra', '', $error);
    }
}
/**
 * Class which represents a single term in an algebraic expression.
 *
 * A single algebraic term is considered to be either an operation, for example addition,
 * subtraction, raising to a power etc. or something operated on, such as a number or
 * variable. Each type of term implements a subclass of this base class.
 */
class qtype_algebra_parser_term {
    // Member variables.
    public $_value;             // String of the actual term itself.
    public $_arguments = array(); // Array of arguments in class form.
    public $_formats;           // Array of format strings.
    public $_nargs;             // Number of arguments for this term.

    /**
     * Constructor for the generic parser term.
     *
     * This method is called by all subclasses to initialize the base class for use.
     * It initializes the number of arguments required, the format strings to use
     * when converting the term in various strng formats, the parser text associated
     * with the term and whether the term is one which commutes.
     *
     * @param $nargs number of arguments which this type of term requires
     * @param $formats an array of the format strings for this term keyed by type
     * @param $text the text from the expression associated with the array
     * @param $commutes if set to true then this term commutes (only for 2 argument terms)
     */
    public function __construct($nargs, $formats,  $text = '', $commutes = false) {
        $this->_value = $text;
        $this->_nargs = $nargs;
        $this->_formats = $formats;
        $this->_commutes = $commutes;
    }

    /**
     * Generates the list of arguments needed when converting the term into a string.
     *
     * This method returns an array with the arguments needed when converting the term
     * into a string. The arrys can then be used with a format string to generate the
     * string representation. The method is recursive because it needs to convert the
     * arguments of the term into strings and so it will walk down the parse tree.
     *
     * @param $method name of method to call to convert arguments into strings
     * @return array of the arguments that, with a format string, can be passed to sprintf
     */
    public function print_args($method) {
        // Create an empty array to store the arguments in.
        $args = array();
        // Handle zero argument terms differently by making the
        // first 'argument' the value of the term itself.
        if ($this->_nargs == 0) {
            $args[] = $this->_value;
        } else {
            foreach ($this->_arguments as $arg) {
                $args[] = $arg->$method();
            }
        }
        // Return the array of arguments.
        return $args;
    }

    /**
     * Produces a 'prettified' string of the expression using the standard input syntax.
     *
     * This method will use the {@link print_args} method to convert the term and all its
     * arguments into a string.
     *
     * @return string input syntax format string of the expression
     */
    public function str() {
        // First check to see if the class has been given all the arguments.
        $this->check_arguments();
        // Get an array of all the arguments except for the format string.
        $args = $this->print_args('str');
        // Insert the format string at the front of the argument array.
        array_unshift($args, $this->_formats['str']);
        // Call sprintf using the argument array as the arguments.
        return call_user_func_array('sprintf', $args);
    }

    /**
     * Produces a LaTeX formatted string of the expression.
     *
     * This method will use the {@link print_args} method to convert the term and all its
     * arguments into a LaTeX formatted string. This can then be given to the main Moodle
     * engine, with TeX filter enabled, to produce a graphical representation of the
     * expression.
     *
     * @return LaTeX format string of the expression
     */
    public function tex() {
        // First check to see if the class has been given all the arguments.
        $this->check_arguments();
        // Get an array of all the arguments except for the format string.
        $args = $this->print_args('tex');
        // Insert the format string at the front of the argument array.
        array_unshift($args, $this->_formats['tex']);
        // Call sprintf using the argument array as the arguments.
        return call_user_func_array('sprintf', $args);
    }

    /**
     * Produces a SAGE formatted string of the expression.
     *
     * This method will use the {@link print_args} method to convert the term and all its
     * arguments into a SAGE formatted string. This can then be passed to SAGE via XML-RPC
     * for symbolic comparisons. The format is very similar to the {@link str} method but
     * has all multiplications made explicit with an asterix.
     *
     * @return SAGE format string of the expression
     */
    public function sage() {
        // First check to see if the class has been given all the arguments.
        $this->check_arguments();
        // Get an array of all the arguments except for the format string.
        $args = $this->print_args('sage');
        // Insert the format string at the front of the argument array. First we
        // check to see if there is a format element called 'sage' if not then we
        // default to the standard string format.
        if (array_key_exists('sage', $this->_formats)) {
            // Insert the sage format string at the front of the argument array.
            array_unshift($args, $this->_formats['sage']);
        } else {
            // Insert the normal format string at the front of the argument array.
            array_unshift($args, $this->_formats['str']);
        }
        // Call sprintf using the argument array as the arguments.
        return call_user_func_array('sprintf', $args);
    }

    /**
     * Returns the list of arguments for the term.
     *
     * This method provides access to the arguments of the term. Although this should
     * ideally be private information it is needed in certain cases to determine
     * how neighbouring terms should display themselves.
     *
     * @return array of arguments for this term
     */
    public function arguments() {
        return $this->_arguments;
    }

    /**
     * Sets the arguments of the term to the values in the given array.
     *
     * The code here overrides the base class's method. The code uses this method to actually
     * set the arguments in the given array but a second stage to choose the format of the
     * multiplication operator is required. This is because a 'x' symbol is required when
     * multiplying two numbers. However this can be omitted when multiplying two variables,
     * a variable and a function etc.
     *
     * @param $args array to set the arguments of the term to
     */
    public function set_arguments($args) {
        if (count($args) != $this->_nargs) {
            throw new parser_exception(get_string('nargswrong', 'qtype_algebra', $this->_value));
        }
        $this->_arguments = $args;
    }

    /**
     * Checks to ensure that the correct number of arguments are defined.
     *
     * Note that this method just checks for the number or arguments it does not check
     * whether they are valid arguments. If the parameter passed is true (default value)
     * an exception will be thrown if the correct number of arguments are not present. Otherwise
     * the function returns false.
     *
     * @param $exc if true then an exception will be thrown if the number of arguments is incorrect
     * @return true if the correct number of arguments are present, false otherwise
     */
    public function check_arguments($exc = true) {
        $retval = (count($this->_arguments) == $this->_nargs);
        if ($exc && !$retval) {
            throw new parser_exception(get_string('nargswrong', 'qtype_algebra', $this->_value));
        } else {
            return $retval;
        }
    }

    /**
     * Returns a list of all the variable names found in the expression.
     *
     * This method uses the {@link collect} method to walk down the parse tree and collect
     * a list of all the variables which the parser has found in the expression. The names
     * of the variables are then returned.
     *
     * @return an array containing all the variables names in the expression
     */
    public function get_variables() {
        $list = array();
        $this->collect($list, 'qtype_algebra_parser_variable');
        return array_keys($list);
    }

    /**
     * Returns a list of all the function names found in the expression.
     *
     * This method uses the {@link collect} method to walk down the parse tree and collect
     * a list of all the functions which the parser has found in the expression. The names
     * of the functions are then returned.
     *
     * @return an array containing all the function names used in the expression
     */
    public function get_functions() {
        $list = array();
        $this->collect($list, 'qtype_algebra_parser_function');
        return array_keys($list);
    }

    /**
     * Collects all the terms of a given type with unique values in the parse tree
     *
     * This method walks recursively down the parse tree by calling itself for the arguments
     * of the current term. The method simply adds the current term to the given imput array
     * using a key set to the value of the term but only if the term matches the selected type.
     * In this way terms only a single entry per term value is return which is the functionality
     * required for the {@link get_variables} and {@link get_functions} methods.
     *
     * @param $list the array to add the term to if it matches the type
     * @param $type the name of the type of term to collect.
     * @return an array containing all the terms of the selected type keyed by their value
     */
    public function collect(&$list, $type) {
        // Add this class to the list if of the correct type.
        if (is_a($this, $type)) {
            // Add a key to the array with the value of the term, this means
            // that multiple terms with the same value will overwrite each
            // other so only one will remain.
            $list[$this->_value] = 0;
        }
        // Now loop over all the argument for this term (if any) and check them.
        foreach ($this->_arguments as $arg) {
            // Collect terms from the arguments as well.
            $arg->collect($list, $type);
        }
    }

    /**
     * Checks to see if this term is equal to another term ignoring arguments.
     *
     * This method compares the current term to another term. The default method simply compares
     * the class of each term. Terms which require more than this, for example comparing values
     * too, override this method in theor own classes.
     *
     * @param $term the term to compare to the current one
     * @return true if the terms match, false otherwise
     */
    public function equals($term) {
        // Default method just checks to ensure that the Terms are both of the same type.
        return is_a($term, get_class($this));
    }

    /**
     * Compares this term, including any arguments, with another term.
     *
     * This method uses the {@link equals} method to see if the current and given term match.
     * It then looks at any arguments which the two terms have and, recursively, calls their
     * compare methods to determine if they also match. For terms with two arguments which
     * also commute the reverse ordering of the arguments is also tried if the first order
     * fails to match.
     *
     * @param $expr top level term of an expression to compare against
     * @return true if the expressions match, false otherwise
     */
    public function equivalent($expr) {
        // Check that the argument is also a term.
        if (!is_a($expr, 'qtype_algebra_parser_term')) {
            throw new parser_exception(get_string('badequivtype', 'qtype_algebra'));
        }
        // Now check that this term is the same as the given term.
        if (!$this->equals($expr)) {
            // Terms are not equal immediately return false since the two do not match.
            return false;
        }
        // Now compare the arguments recursively...
        switch($this->_nargs) {
            case 0:
                // For zero arguments we already compared this class and found it the same so
                // because there are no arguments to check we are equivalent!
                return true;
            case 1:
                // For one argument we also need to compare the argument of each term.
                return $this->_arguments[0]->equivalent($expr->_arguments[0]);
            case 2:
                // Now it gets interesting. First we compare the two arguments in the same
                // order and see what we get...
                if ($this->_arguments[0]->equivalent($expr->_arguments[0]) and
                   $this->_arguments[1]->equivalent($expr->_arguments[1])) {
                    // Both arguments are equivalent so we have a match.
                    return true;
                } else if ($this->_commutes and $this->_arguments[0]->equivalent($expr->_arguments[1]) and
                        $this->_arguments[1]->equivalent($expr->_arguments[0])) {
                    // Otherwise if the operator commutes we can see if the first argument matches
                    // the second argument and vice versa.
                    return true;
                } else {
                    return false;
                }
            default:
                throw new parser_exception(get_string('morethantwoargs', 'qtype_algebra'));
        }
    }

    /**
     * Returns the number of arguments required by the term.
     *
     * @return the number of arguments required by the term
     */
    public function n_args() {
        return $this->_nargs;
    }

    /**
     * Evaluates the term numerically using the given variable values.
     *
     * The given parameter array is keyed by the name of the variable and the numerical
     * value to assign it is stored in the array value. This method is an abstract one
     * which must be implemented by all subclasses. Failure to do so will generate an
     * exception when the method is called.
     *
     * @param $params array of values keyed by variable name
     * @return the numerical value of the term given the provided values for the variables
     */
    public function evaluate($params) {
        throw new parser_exception(get_string('noevaluate', 'qtype_algebra', $this->_value));
    }

    /**
     * Dumps the term and its arguments to standard out.
     *
     * This method will recursively call the entire parse tree attached to it and produce
     * a nicely formatted dump of the term structure. This is mainly useful for debugging
     * purposes.
     *
     * @param $indent string containing the indentation to use
     * @param $params variable values to use if an evaluation is also desired
     * @return a string indicating the type of the term
     */
    public function dump(&$params = array(), $indent = '') {
        echo "$indent<Term type '".get_class($this).'\' with value \''.$this->_value;
        if (!empty($params)) {
            echo ' eval = \''.$this->evaluate($params)."'>\n";
        } else {
            echo "'>\n";
        }
        foreach ($this->_arguments as $arg) {
            $arg->dump($params, $indent.'  ');
        }
    }

    /**
     * Special casting operator method to convert the term object to a string.
     *
     * This is primarily a debug method. It is called when the term object is cast into a
     * string, such as happens when echoing or printing it. It simply returns a string
     * indicating the type of the parser term.
     *
     * @return a string indicating the type of the term
     */
    public function __toString() {
        return '<Algebraic parser term of type \''.get_class($this).'\'>';
    }
}

/**
 * Class representing a null, or empty, term.
 *
 * This is the type of term returned when the parser is given an empty string to parse.
 * It takes no arguments and will never be found in a parser tree. This term is solely
 * to give a valid return type for an empty string condition and so avoids the need to
 * throw an exception in such cases.
 */
class qtype_algebra_parser_nullterm extends qtype_algebra_parser_term {
    /** @var The TeX multiply operator. */
    public $id;
    /**
     * Constructs an instance of a null term.
     *
     * Initializes a null term class. Since this class represents nothing no special
     * initialization is required and no arguments are needed.
     */
    public function __construct() {
        parent::__construct(self::NARGS, self::$formats, '');
    }

    /**
     * Returns the array of arguments needed to convert this class into a string.
     *
     * Since this class is represented by an empty string which has no formatting fields
     * we override the base class method to return an empty array.
     *
     * @param $method name of method to call to convert arguments into strings
     * @return array of the arguments that, with a format string, can be passed to sprintf
     */
    public function print_args($method) {
        return array();
    }

    /**
     * Evaluates the term numerically.
     *
     * Since this is an empty term we define the evaluation as zero regardless of the parameters.
     *
     * @param $params array of the variable values to use
     */
    public function evaluate($params) {
        // Return something which is not a number.
        return acos(2.0);
    }

    // Static class properties.
    const NARGS = 0;
    private static $formats = array('str' => '',
                                  'tex' => '');
}


/**
 * Class representing a number.
 *
 * All purely numerical quantities will be represented by this type of class. There are
 * two basic types of numbers: non-exponential and exponential. Both types are handled by
 * this single class.
 */
class qtype_algebra_parser_number extends qtype_algebra_parser_term {

    /**
     * Constructs an instance of a number term.
     *
     * This function initializes an instance of a number term using the string which
     * matches the number's regular expression.
     *
     * @param $text string matching the number regular expression
     */
    public function __construct($text = '') {
        // Unfortunately PHP maths will only support a '.' as a decimal point and will not support
        // ',' as used in Danish, French etc. To allow for this we always convert any commas into
        // decimal points before we parse the string.
        $text = str_replace(',', '.', $text);
        $this->_sign = '';
        // Now determine whether this is in exponent form or just a plain number.
        if (preg_match('/([\.0-9]+)E([-+]?\d+)/', $text, $m)) {
            $this->_base = $m[1];
            $this->_exp = $m[2];
            $eformats = array('str' => '%sE%s',
                            'tex' => '%s \\' . get_config('qtype_algebra', 'multiplyoperator') . '10^{%s}');
            parent::__construct(self::NARGS, $eformats, $text);
        } else {
            $this->_base = $text;
            $this->_exp = '';
            parent::__construct(self::NARGS, self::$formats, $text);
        }
    }

    /**
     * Sets this number to be negative.
     *
     * This method will convert the number into a nagetive one. It is called when
     * the parser finds a subtraction operator in front of the number which does
     * not have a variable or another number preceding it.
     */
    public function set_negative() {
        // Prepend a minus sign to both the base and total value strings.
        $this->_base = '-'.$this->_base;
        $this->_value = '-'.$this->_value;
        $this->_sign = '-';
    }

    /**
     * Checks to see if this number is equal to another number.
     *
     * This is a two step process. First we use the base class equals method to ensure
     * that we are comparing two numbers. Then we check that the two have the same value.
     *
     * @param $expt the term to compare to the current one
     * @return true if the terms match, false otherwise
     */
    public function equals($expr) {
        // Call the default method first to check type.
        if (parent::equals($expr)) {
            return (float)$this->_value == (float)$expr->_value;
        } else {
            return false;
        }
    }

    /**
     * Generates the list of arguments needed when converting the term into a string.
     *
     * For number terms there are two possible formats: those with an exponent and those
     * without an exponent. This method determines which to use and then pushes the correct
     * arguments into the array which is returned.
     *
     * @param $method name of method to call to convert arguments into strings
     * @return array of the arguments that, with a format string, can be passed to sprintf
     */
    public function print_args($method) {
        // When displaying the number we need to worry about whether to use a decimal point
        // or a comma depending on the language currently selected/ Do this by replacing the
        // decimal point (which we have to use internally because of the PHP math standard)
        // with the correct string from the language pack.
        $base = str_replace('.', get_string('decimal', 'qtype_algebra'), $this->_base);
        // Put the base part of the number into the argument array.
        $args = array($base);
        // Check to see if we have an exponent...
        if ($this->_exp) {
            // We do so add it to the argument array as well.
            $args[] = $this->_exp;
        }
        // Return the list of arguments.
        return $args;
    }

    /**
     * Evaluates the term numerically.
     *
     * All this method does is return the string representing the number cast as a double
     * precision floating point variable.
     *
     * @param $params array of the variable values to use
     */
    public function evaluate($params) {
        return doubleval($this->_value);
    }

    // Static class properties.
    const NARGS = 0;
    private static $formats = array('str' => '%s',
                                  'tex' => '%s ');
}

/**
 * Class representing a variable term in an algebraic expression.
 *
 * When the parser finds a text string which does not correspond to a function it creates
 * this type of term and puts the contents of that text into it. Variables with names
 * corresponding to the names of the greek letters are replaced by those letters when
 * rendering the term in LaTeX. Other variables display their first letter with all
 * subsequent letters being lowercase. This reduces confusion when rendering expressions
 * consisting of multiplication of two variables.
 */
class qtype_algebra_parser_variable extends qtype_algebra_parser_term {
    // Define the list of variable names which will be replaced by greek letters.
    public static $greek = array (
        'alpha',
        'beta',
        'gamma',
        'delta',
        'epsilon',
        'zeta',
        'eta',
        'theta',
        'iota',
        'kappa',
        'lambda',
        'mu',
        'nu',
        'xi',
        'omicron',
        'pi',
        'rho',
        'sigma',
        'tau',
        'upsilon',
        'phi',
        'chi',
        'psi',
        'omega',

        'Alpha',
        'Beta',
        'Gamma',
        'Delta',
        'Epsilon',
        'Zeta',
        'Eta',
        'Theta',
        'Iota',
        'Kappa',
        'Lambda',
        'Mu',
        'Nu',
        'Xi',
        'Omicron',
        'Pi',
        'Rho',
        'Sigma',
        'Tau',
        'Upsilon',
        'Phi',
        'Chi',
        'Psi',
        'Omega',
     );

    /**
     * Constructor for an algebraic term class representing a variable.
     *
     * Initializes an instance of the variable term subclass. The method is given the text
     * in the expression corresponding to the variable name. This is then parsed to get the
     * variable name which is split into a base and subscript. If the start of the string
     * matches the name of a greek letter this is taken as the base and the remainder as the
     * subscript. Failing that either the subscript must be explicitly specified using an
     * underscore character or the first character is taken as the base.
     *
     * @param $text text matching the variable name
     */
    public function __construct($text) {
        // Create the array to store the regular expression matches in.
        $m = array();
        // Set the sign of the variable to be empty.
        $this->_sign = '';
        if (preg_match('/([^_]+)_(.*)/A', $text, $m)) {
          $this->_base = $m[1];
          $this->_subscript = $m[2];
        } else {
          $this->_base = $text;
          $this->_subscript = '';
        }
        $gmode = in_array($this->_base, self::$greek, 1) ? 'greek' : 'std';
        parent::__construct(self::NARGS, self::$formats[$gmode], $text);
    }

    /**
     * Sets this variable to be negative.
     *
     * This method will convert the number into a nagetive one. It is called when
     * the parser finds a subtraction operator in front of the number which does
     * not have a variable or another number preceding it.
     */
    public function set_negative() {
        // Set the sign to be a '-'.
        $this->_sign = '-';
    }

    /**
     * Generates the list of arguments needed when converting the term into a string.
     *
     * The string of the variable depends solely on the name and subscript and hence these
     * are the only two arguments returned in the array.
     *
     * @param $method name of method to call to convert arguments into strings
     * @return array of the arguments that, with a format string, can be passed to sprintf
     */
    public function print_args($method) {
        $under = $this->_subscript == '' ? '' : '_';
        return array($this->_sign, $this->_base, $under, $this->_subscript);
    }

    /**
     * Evaluates the number numerically.
     *
     * Overrides the base class method to simply return the numerical value of the number the
     * class represents.
     *
     * @param $params array of values keyed by variable name
     * @return the numerical value of the term given the provided values for the variables
     */
    public function evaluate($params) {
        if ($this->_sign == '-') {
            $mult = -1;
        } else {
            $mult = 1;
        }
        if (array_key_exists($this->_value, $params)) {
            return $mult * doubleval($params[$this->_value]);
        } else {
            // Found an indefined variable. Cannot evaluate numerically so throw exception.
            throw new parser_exception(get_string('undefinedvariable', 'qtype_algebra', $this->_value));
        }
    }

    /**
     * Checks to see if this variable is equal to another variable.
     *
     * This is a two step process. First we use the base class equals method to ensure
     * that we are comparing two variables. Then we check that the two are the same variable.
     *
     * @param $expr the term to compare to the current one
     * @return true if the terms match, false otherwise
     */
    public function equals($expr) {
        // Call the default method first to check type.
        if (parent::equals($expr)) {
            return $this->_value == $expr->_value and $this->_sign == $expr->_sign;
        } else {
            return false;
        }
    }

    // Static class properties.
    const NARGS = 0;
    private static $formats = array(
        'greek' => array('str' => '%s%s%s%s',
                          'tex' => '%s\%s%s{%s}'),
        'std' => array('str' => '%s%s%s%s',
                          'tex' => '%s%s%s{%s}')
    );
}


/**
 * Class representing a power operation in an algebraic expression.
 *
 * The parser creates an instance of this term when it finds a string matching the power
 * operator's syntax. The string which corresponds to the term is passed to the constructor
 * of this subclass.
 */
class qtype_algebra_parser_power extends qtype_algebra_parser_term {

    /**
     * Constructs an instance of a power operator term.
     *
     * This function initializes an instance of a power operator term using the string which
     * matches the power operator expression. Since this is simply the character representing
     * the operator it is not used except when producing a string representation of the term.
     *
     * @param $text string matching the term's regular expression
     */
    public function __construct($text) {
        parent::__construct(self::NARGS, self::$formats, $text);
    }

    /**
     * Evaluates the power operation numerically.
     *
     * Overrides the base class method to simply return the numerical value of the power
     * operation. The method evaluates the two arguments of the term and then passes them to
     * the 'pow' function from the maths library.
     *
     * @param $params array of values keyed by variable name
     * @return the numerical value of the term given the provided values for the variables
     */
    public function evaluate($params) {
        $this->check_arguments();
        return pow(doubleval($this->_arguments[0]->evaluate($params)),
                   doubleval($this->_arguments[1]->evaluate($params)));
    }

    // Static class properties.
    const NARGS = 2;
    private static $formats = array(
        'str' => '%s^%s',
        'tex' => '%s^{%s}'
    );
}


/**
 * Class representing a divide operation in an algebraic expression.
 *
 * The parser creates an instance of this term when it finds a string matching the divide
 * operator's syntax. The string which corresponds to the term is passed to the constructor
 * of this subclass.
 */
class qtype_algebra_parser_divide extends qtype_algebra_parser_term {

    /**
     * Constructs an instance of a divide operator term.
     *
     * This function initializes an instance of a divide operator term using the string which
     * matches the divide operator expression. Since this is simply the character representing
     * the operator it is not used except when producing a string representation of the term.
     *
     * @param $text string matching the term's regular expression
     */
    public function __construct($text) {
        parent::__construct(self::NARGS, self::$formats, $text);
    }

    /**
     * Evaluates the divide operation numerically.
     *
     * Overrides the base class method to simply return the numerical value of the divide
     * operation. The method evaluates the two arguments of the term and then simply divides
     * them to get the return value.
     *
     * @param $params array of values keyed by variable name
     * @return the numerical value of the term given the provided values for the variables
     */
    public function evaluate($params) {
        $this->check_arguments();
        // Get the value we are trying to divide by.
        $divby = $this->_arguments[1]->evaluate($params);
        // Check to see if this is zero.
        if ($divby == 0) {
            // Check the sign of the other argument and use to determine whether we return
            // plus or minus infinity.
            return INF * $this->_arguments[0]->evaluate($params);
        } else {
            return $this->_arguments[0]->evaluate($params) / $divby;
        }
    }

    // Static class properties.
    const NARGS = 2;
    private static $formats = array(
        'str' => '%s/%s',
        'tex' => '\\frac{%s}{%s}'
    );
}

/**
 * Class representing a modulo operation in an algebraic expression.
 *
 * The parser creates an instance of this term when it finds a string matching the modulo
 * operator's syntax. The string which corresponds to the term is passed to the constructor
 * of this subclass.
 */
class qtype_algebra_parser_modulo extends qtype_algebra_parser_term {

    /**
     * Constructs an instance of a modulo operator term.
     *
     * This function initializes an instance of a modulo operator term using the string which
     * matches the modulo operator expression. Since this is simply the character representing
     * the operator it is not used except when producing a string representation of the term.
     *
     * @param $text string matching the term's regular expression
     */
    public function __construct($text) {
        parent::__construct(self::NARGS, self::$formats, $text);
    }

    /**
     * Evaluates the modulo operation numerically.
     *
     * Overrides the base class method to simply return the numerical value of the modulo
     * operation. The method evaluates the two arguments of the term and then performs
     * the required operation to get the return value.
     *
     * @param $params array of values keyed by variable name
     * @return the numerical value of the term given the provided values for the variables
     */
    public function evaluate($params) {
        $this->check_arguments();
        // Get the value we are trying to modulo by.
        $denom = $this->_arguments[1]->evaluate($params);
        // Check to see if this is zero.
        if ($denom == 0) {
            // Check the sign of the other argument and use to determine whether we return
            // plus or minus infinity.
            return INF * $this->_arguments[0]->evaluate($params);
        } else {
            $nume = $this->_arguments[0]->evaluate($params);
            $rslt = fmod($nume, $denom);
            return $rslt;
        }
    }

    // Static class properties.
    const NARGS = 2;
    private static $formats = array(
        'str' => '%s%%%s',
        'tex' => '{%s}\%%{%s}'
    );
}

/**
 * Class representing a multiplication operation in an algebraic expression.
 *
 * The parser creates an instance of this term when it finds a string matching the multiplication
 * operator's syntax. The string which corresponds to the term is passed to the constructor
 * of this subclass.
 */
class qtype_algebra_parser_multiply extends qtype_algebra_parser_term {

    /**
     * Constructs an instance of a multiplication operator term.
     *
     * This function initializes an instance of a multiplication operator term using the string which
     * matches the multiplication operator expression. Since this is simply the character representing
     * the operator it is not used except when producing a string representation of the term.
     *
     * @param $text string matching the term's regular expression
     */
    public function __construct($text) {
        $this->mformats = array('*' => array('str' => '%s*%s',
                                            'tex' => '%s \\' . get_config('qtype_algebra', 'multiplyoperator') . ' %s'),
                                '.' => array('str' => '%s %s',
                                            'tex' => '%s %s',
                                            'sage' => '%s*%s')
                              );
        parent::__construct(self::NARGS, $this->mformats['*'], $text, true);
    }

    /**
     * Sets the arguments of the term to the values in the given array.
     *
     * This method sets the term's arguments to those in the given array.
     *
     * @param $args array to set the arguments of the term to
     */
    public function set_arguments($args) {
        // First perform default argument setting method. This will generate
        // an error if there is a problem with the number of arguments.
        parent::set_arguments($args);
        // Set the default explicit format.
        $this->_formats = $this->mformats['*'];
        // Only allow the implicit multiplication if the second argument is either a
        // special, variable, function or bracket and not negative. In all other cases the operator must be
        // explicitly written.
        if (is_a($args[1], 'qtype_algebra_parser_bracket') or
           is_a($args[1], 'qtype_algebra_parser_variable') or
           is_a($args[1], 'qtype_algebra_parser_special') or
           is_a($args[1], 'qtype_algebra_parser_function')) {
            if (!method_exists($args[1], 'set_negative') or $args[1]->_sign == '') {
                $this->_formats = $this->mformats['.'];
            }
        }
        // Check for one more special exemption: if the second argument is a power expression
        // then we use the same criteria on the first argument of it.
        if (is_a($args[1], 'qtype_algebra_parser_power')) {
            // Get the arguments from the power term. Note we do not check these since
            // power terms are parsed before multiplication ones and are required to
            // have two arguments.
            $powargs = $args[1]->arguments();
            // Allow the implicit multiplication if the power's first argument is either a
            // special, variable, function or bracket and not negative.
            if (is_a($powargs[0], 'qtype_algebra_parser_bracket') or
               is_a($powargs[0], 'qtype_algebra_parser_variable') or
               is_a($powargs[0], 'qtype_algebra_parser_special') or
               is_a($powargs[0], 'qtype_algebra_parser_function')) {
                if (!method_exists($powargs[0], 'set_negative') or $powargs[0]->_sign == '') {
                    $this->_formats = $this->mformats['.'];
                }
            }
        }
    }

    /**
     * Evaluates the multiplication operation numerically.
     *
     * Overrides the base class method to simply return the numerical value of the multiplication
     * operation. The method evaluates the two arguments of the term and then simply multiplies
     * them to get the return value.
     *
     * @param $params array of values keyed by variable name
     * @return the numerical value of the term given the provided values for the variables
     */
    public function evaluate($params) {
        $this->check_arguments();
        return $this->_arguments[0]->evaluate($params) * $this->_arguments[1]->evaluate($params);
    }

    // Static class properties.
    const NARGS = 2;
}


/**
 * Class representing a addition operation in an algebraic expression.
 *
 * The parser creates an instance of this term when it finds a string matching the addition
 * operator's syntax. The string which corresponds to the term is passed to the constructor
 * of this subclass.
 */
class qtype_algebra_parser_add extends qtype_algebra_parser_term {

    /**
     * Constructs an instance of a addition operator term.
     *
     * This function initializes an instance of a addition operator term using the string which
     * matches the addition operator expression. Since this is simply the character representing
     * the operator it is not used except when producing a string representation of the term.
     *
     * @param $text string matching the term's regular expression
     */
    public function __construct($text) {
        parent::__construct(self::NARGS, self::$formats, $text, true);
    }

    /**
     * Evaluates the addition operation numerically.
     *
     * Overrides the base class method to simply return the numerical value of the addition
     * operation. The method evaluates the two arguments of the term and then simply adds
     * them to get the return value.
     *
     * @param $params array of values keyed by variable name
     * @return the numerical value of the term given the provided values for the variables
     */
    public function evaluate($params) {
        $this->check_arguments();
        return $this->_arguments[0]->evaluate($params) + $this->_arguments[1]->evaluate($params);
    }

    // Static class properties.
    const NARGS = 2;
    private static $formats = array(
        'str' => '%s+%s',
        'tex' => '%s + %s'
    );
}


/**
 * Class representing a subtraction operation in an algebraic expression.
 *
 * The parser creates an instance of this term when it finds a string matching the subtraction
 * operator's syntax. The string which corresponds to the term is passed to the constructor
 * of this subclass.
 */
class qtype_algebra_parser_subtract extends qtype_algebra_parser_term {

    /**
     * Constructs an instance of a subtraction operator term.
     *
     * This function initializes an instance of a subtraction operator term using the string which
     * matches the subtraction operator expression. Since this is simply the character representing
     * the operator it is not used except when producing a string representation of the term.
     *
     * @param $text string matching the term's regular expression
     */
    public function __construct($text) {
        parent::__construct(self::NARGS, self::$formats, $text);
    }

    /**
     * Evaluates the subtraction operation numerically.
     *
     * Overrides the base class method to simply return the numerical value of the subtraction
     * operation. The method evaluates the two arguments of the term and then simply subtracts
     * them to get the return value.
     *
     * @param $params array of values keyed by variable name
     * @return the numerical value of the term given the provided values for the variables
     */
    public function evaluate($params) {
        $this->check_arguments();
        return $this->_arguments[0]->evaluate($params) - $this->_arguments[1]->evaluate($params);
    }

    // Static class properties.
    const NARGS = 2;
    private static $formats = array(
        'str' => '%s-%s',
        'tex' => '%s - %s'
    );
}


/**
 * Class representing a special constant in an algebraic expression.
 *
 * The parser creates an instance of this term when it finds a string matching the a predefined
 * special constant such as pi or 'e' (from natural logarithms).
 */
class qtype_algebra_parser_special extends qtype_algebra_parser_term {

    /**
     * Constructs an instance of a special constant term.
     *
     * This function initializes an instance of a special term using the string which
     * matches the regular expression of a special constant.
     *
     * @param $text string matching a constant's regular expression
     */
    public function __construct($text) {
        parent::__construct(self::NARGS, self::$formats[$text], $text);
        $this->_sign = '';
    }

    /**
     * Sets this special to be negative.
     *
     * This method will convert the number into a nagetive one. It is called when
     * the parser finds a subtraction operator in front of the number which does
     * not have a variable or another number preceding it.
     */
    public function set_negative() {
        // Set the sign to be a '-'.
        $this->_sign = '-';
    }

    /**
     * Evaluates the special constant numerically.
     *
     * Overrides the base class method to simply return the numerical value of the special
     * constant which is defined by an internal switch based on the constant's name.
     *
     * @param $params array of values keyed by variable name
     * @return int the numerical value of the term given the provided values for the variables
     */
    public function evaluate($params) {
        if ($this->_sign == '-') {
            $mult = -1;
        } else {
            $mult = 1;
        }
        switch($this->_value) {
            case 'pi':
                return $mult * pi();
            case 'e':
                return $mult * exp(1);
            default:
                return 0;
        }
    }

    /**
     * Returns the array of arguments needed to convert this special term into a string.
     *
     * The special term generally has a fixed, predefined formatting already hard coded so
     * the only remaining variable is the sign of the term and this is what this method
     * returns.
     *
     * @param $method name of method to call to convert arguments into strings
     * @return array of the arguments that, with a format string, can be passed to sprintf
     */
    public function print_args($method) {
        return array($this->_sign);
    }

    /**
     * Checks to see if this constant is equal to another term.
     *
     * This is a two step process. First we use the base class equals method to ensure
     * that we are comparing two variables. Then we check that the two are the same constant.
     *
     * @param $expr the term to compare to the current one
     * @return true if the terms match, false otherwise
     */
    public function equals($expr) {
        // Call the default method first to check type.
        if (parent::equals($expr)) {
            return $this->_value == $expr->_value and $this->_sign == $expr->_sign;
        } else {
            return false;
        }
    }

    // Static class properties.
    const NARGS = 0;
    private static $formats = array(
        'pi' => array(  'str' => '%spi',
                         'tex' => '%s\\pi'),
        'e' => array(  'str' => '%se',
                         'tex' => '%se')
    );
}

/**
 * implement math functions that aren't php builtins
 */
function log2($arg)
{
    return log($arg, 2);
}

function ln($arg)
{
    return log($arg);
}

/**
 * Class representing a function in an algebraic expression.
 *
 * The parser creates an instance of this term when it finds a string matching the function's
 * syntax. The string which corresponds to the term is passed to the constructor
 * of this subclass.
 */
class qtype_algebra_parser_function extends qtype_algebra_parser_term {

    /**
     * Constructs an instance of a function term.
     *
     * This function initializes an instance of a function term using the string which
     * matches the name of a function.
     *
     * @param $text string matching the function's regular expression
     */
    public function __construct($text) {
        if ($text == 'log') {
            throw new parser_exception(get_string('deprecatedlog', 'qtype_algebra'));
        }
        if (!function_exists($text) and !array_key_exists($text, self::$fnmap)) {
            throw new parser_exception(get_string('undefinedfunction', 'qtype_algebra', $text));
        }
        $formats = array( 'str' => '%s'.$text.'%s');
        if (array_key_exists($text, self::$texmap)) {
            $formats['tex'] = '%s'.self::$texmap[$text].' %s';
        } else {
            $formats['tex'] = '%s\\'.$text.' %s';
        }
        $this->_sign = '';
        parent::__construct(self::NARGS, $formats, $text);
    }

    /**
     * Sets this function to be negative.
     *
     * This method will convert the function into a negative one. It is called when
     * the parser finds a subtraction operator in front of the function which does
     * not have a variable or another number preceding it e.g. 3*-sin(x)
     */
    public function set_negative() {
        // Set the sign to be a '-'.
        $this->_sign = '-';
    }

    /**
     * Sets the arguments of the term to the values in the given array.
     *
     * The code here overrides the base class's method. The code uses this method to actually
     * set the arguments in the given array but a second stage to insert brackets around the
     * function's argument is required.
     *
     * @param $args array to set the arguments of the term to
     */
    public function set_arguments($args) {
        if (count($args) != $this->_nargs) {
            throw new parser_exception(get_string('badfuncargs', 'qtype_algebra', $this->_value));
        }
        if (!is_a($args[0], 'qtype_algebra_parser_bracket')) {
            // Check to see if this function requires a special bracket.
            if (in_array($this->_value, self::$bracketmap)) {
                $b = new qtype_algebra_parser_bracket('<');
            } else {
                // Does not require special brackets so create normal ones.
                $b = new qtype_algebra_parser_bracket('(');
            }
            $b->set_arguments($args);
            $this->_arguments = array($b);
        } else {
            // First term already a bracket.
            // Check to see if we need a special bracket.
            if (in_array($this->_value, self::$bracketmap)) {
                // Make the bracket special.
                $args[0]->make_special();
            }
            // Set the arguments to the given type.
            $this->_arguments = $args;
        }
    }

    /**
     * Generates the list of arguments needed when converting the term into a string.
     *
     * The string of the function depends solely on the function argument and the sign.
     * The name has already been coded in at construction time.
     *
     * @param $method name of method to call to convert arguments into strings
     * @return array of the arguments that, with a format string, can be passed to sprintf
     */
    public function print_args($method) {
        // First ensure that there are the correct number of arguments.
        $this->check_arguments();
        return array($this->_sign, $this->_arguments[0]->$method());
    }

    /**
     * Evaluates the function numerically.
     *
     * Overrides the base class method to simply return the numerical value of the function.
     * Each function name is first checked against an internal map to determine the corresponding
     * PHP math function to call. If the function is not in the map it is assumed to already be
     * the correct name for a PHP math function.
     *
     * @param $params array of values keyed by variable name
     * @return the numerical value of the term given the provided values for the variables
     */
    public function evaluate($params) {
        // First ensure that there are the correct number of arguments.
        $this->check_arguments();
        // Get the correct sign to multiply the value by.
        if ($this->_sign == '-') {
            $mult = -1;
        } else {
            $mult = 1;
        }
        // Check to see if there is an entry to map the function name to a PHP function.
        if (array_key_exists($this->_value, self::$fnmap)) {
            $func = self::$fnmap[$this->_value];
            return $mult * $func($this->_arguments[0]->evaluate($params));
        } else {
            // No map entry so the function name must already be a PHP function...
            $tmp = $this->_value;
            return $mult * $tmp($this->_arguments[0]->evaluate($params));
        }
    }

    /**
     * Checks to see if this function is equal to another term.
     *
     * This is a two step process. First we use the base class equals method to ensure
     * that we are comparing two variables. Then we check that the two are the same constant.
     *
     * @param $expr the term to compare to the current one
     * @return true if the terms match, false otherwise
     */
    public function equals($expr) {
        // Call the default method first to check type.
        if (parent::equals($expr)) {
            return $this->_value == $expr->_value and $this->_sign == $expr->_sign;
        } else {
            return false;
        }
    }

    // Static class properties.
    const NARGS = 1;
     /* fnmap is not needed, since all needed
      *   functions are implemented without pseudonyms
      */
    public static $fnmap = array ();
    public static $texmap = array(
        'floor'  => '\\mathrm{floor}',
        'ceil'  => '\\mathrm{ceil}',
        'sqrt'  => '\\sqrt',
        'log2'  => '\\log_{2}',
        'log10' => '\\log_{10}',
        'asin'  => '\\sin^{-1}',
        'acos'  => '\\cos^{-1}',
        'atan'  => '\\tan^{-1}',
        'asinh' => '\\sinh^{-1}',
        'acosh' => '\\cosh^{-1}',
        'atanh' => '\\tanh^{-1}',
    );

    // List of functions requiring special brackets.
    public static $bracketmap = array ('sqrt'
                                       );
}


/**
 * Class representing a bracket operation in an algebraic expression.
 *
 * The parser creates an instance of this term when it finds a string matching the bracket
 * operator's syntax. The string which corresponds to the term is passed to the constructor
 * of this subclass. Note that a pair of brackets is treated as a single term. There are no
 * separate open and close bracket operators.
 */
class qtype_algebra_parser_bracket extends qtype_algebra_parser_term {

    public function __construct($text) {
        parent::__construct(self::NARGS, self::$formats[$text], $text);
        $this->_sign = '';
        $this->_open = $text;
        switch($this->_open) {
            case '(':
                $this->_close = ')';
                break;
            case '[':
                $this->_close = ']';
                break;
            case '{':
                $this->_close = '}';
                break;
            // Special kind of bracket. This behaves as normal brackets for a string but as invisible
            // curly brackets '{}' with LaTeX.
            case '<':
                $this->_close = '>';
                break;
        }
    }

    /**
     * Evaluates the bracket operation numerically.
     *
     * Overrides the base class method to simply return the numerical value of the bracket
     * operation. The method evaluates the argument of the term, i.e. what is inside the
     * brackets, and then returns the value.
     *
     * @param $params array of values keyed by variable name
     * @return the numerical value of the term given the provided values for the variables
     */
    public function evaluate($params) {
        if ($this->_sign == '-') {
            $mult = -1;
        } else {
            $mult = 1;
        }
        if (count($this->_arguments) != $this->_nargs) {
            return 0;
        }
        return $mult * $this->_arguments[0]->evaluate($params);
    }

    public function set_negative() {
        // Set the sign to be a '-'.
        $this->_sign = '-';
    }

    /**
     * Set the bracket type to 'special'.
     *
     * The method converts the bracket to the special type. The special type appears as a
     * normal bracket in string mode but produces the invisible curly brackets for LaTeX.
     */
    public function make_special() {
        $this->_open = '<';
        $this->_close = '>';
        // Call the base class constructor as if this were a new instance of the bracket.
        parent::__construct(self::NARGS, self::$formats['<'], '<');
    }

    // Member variables.
    public $_open = '(';
    public $_close = ')';

    // Static class properties.
    const NARGS = 1;
    private static $formats = array(
        '(' => array('str' => '%s(%s)',
                      'tex' => '%s\\left( %s \\right)'),
        '[' => array('str' => '%s[%s]',
                      'tex' => '%s\\left[ %s \\right]'),
        '{' => array('str' => '%s{%s}',
                      'tex' => '%s\\left\\lbrace %s \\right\\rbrace'),
        '<' => array('str' => '%s(%s)',
                      'tex' => '%s{%s}')
    );

    public function print_args($method) {
        $args = array($this->_sign);
        foreach ($this->_arguments as $arg) {
            $args[] = $arg->$method();
        }
        // Return the array of arguments.
        return $args;
    }
}


/**
 * The main parser class.
 *
 * This class implements the methods needed to parse an expression. It uses a series of
 * regular expressions to indentify the different terms in the expression and then creates
 * instances of the correct subclass to handle them.
 */
class qtype_algebra_parser {
    // Special constants which the parser will understand.
    public static $specials = array (
        'pi',
        'e'
    );

    // Functions which the parser will understand.
    // You have to implement any that are not standard PHP math functions.
    public static $functions = array (
        'floor',
        'ceil',
        'sqrt',
        'exp',
        'log2',
        'ln',
        'log',
        'log10',
        'sinh',
        'cosh',
        'tanh',
        'sin',
        'cos',
        'tan',
        'asin',
        'acos',
        'atan',
        'asinh',
        'acosh',
        'atanh',
    );

    // Array to define the priority of the different operations. The parser implements the standard BODMAS priority:
    // brackets, order (power), division, mulitplication, addition, subtraction.
    private static $priority = array (
        array('qtype_algebra_parser_power'),
        array('qtype_algebra_parser_function'),
        array('qtype_algebra_parser_divide', 'qtype_algebra_parser_multiply', 'qtype_algebra_parser_modulo'),
        array('qtype_algebra_parser_add', 'qtype_algebra_parser_subtract')
    );

    // Regular experssion to match an open bracket.
    private static $openb = '/[\{\(\[]/A';
    // Regular experssion to match a close bracket.
    private static $closeb = '/[\}\)\]]/A';
    // Regular expression to match a plain float or integer number without exponent.
    private static $plainnumber = '(([0-9]+(\.|,)[0-9]*)|([0-9]+)|((\.|,)[0-9]+))';
    // Regular expression to match a float or integer number with an exponent.
    private static $expnumber = '(([0-9]+(\.|,)[0-9]*)|([0-9]+)|((\.|,)[0-9]+))E([-+]?\d+)';
    // Array to associate close brackets with the correct open bracket type.
    private static $bramap = array(')' => '(', ']' => '[', '}' => '{');

    /**
     * Constructor for the main parser class.
     *
     * This constructor initializes the token map of the main parser class. It constructs a map of
     * regular expressions to class types. As it parses a string it uses these regular expressions to
     * find tokens in the input string which are then fed to the corresponding term class for
     * interpretation.
     */
    public function __construct() {
        $this->_tokens = array (
            array ('/(\^|\*\*)/A',                            'qtype_algebra_parser_power'    )
            , array ('/\//A',                                 'qtype_algebra_parser_divide'   )
            , array ('/%/A',                                  'qtype_algebra_parser_modulo'   )
            , array ('/\*/A',                                   'qtype_algebra_parser_multiply' )
            , array ('/\+/A',                                   'qtype_algebra_parser_add'      )
            , array ('/-/A',                                    'qtype_algebra_parser_subtract' )
            , array ('/('.self::$expnumber.'|'.self::$plainnumber.')/A',    'qtype_algebra_parser_number'   )
            , array ('/[A-Za-z][A-Za-z0-9_]*/A',                'qtype_algebra_parser_identifier' )
            );
    }

    /**
     * Parses a given string containing an algebric expression and returns the corresponding parse tree.
     *
     * This method loops over the string using the regular expressions in the token map to break down the
     * string into tokens. These tokens are arranged into a structured stack, taking account of the
     * bracket structure. Finally then method calls the {@link interpret} method to convert the structured
     * token strings into a fully parsed term structure. The method can optionally be passed a list of
     * variables which are used in the expression. If such a list is passed then the parser will attempt
     * to match the current position in the string with one of these given variables before any other
     * token. When passing a variable list a third parameter allows a choice of whether to allow additional
     * undeclared variables. This defaults to false when a list of variables is passed and is ignored otherwise.
     *
     * @param $text string containing the expression to parse
     * @param $variables array containing known variable names
     * @param $undecvars whether to allow (true) undeclared variable names
     * @return top term of the parsed expression
     */
    public function parse($text, $variables = array(), $undecvars = false) {
        $i = 0;
        // Create an array to store the parse tree.
        $tree = array();
        // Create an array to act as a temporary storage stack. This stack is used to
        // push higher levels of the parse tree as it is assembled from the expression.
        $stack = array();
        // Array used to store the match results from regular expression searches.
        $m = array();
        // Loop over the expression string moving along it using the offset variable $i while
        // there are still characters left to parse.
        while ($i < strlen($text)) {
            // Match any white space at the start of the string and 'remove' it by advancing
            // the pointer by the length of the string matching the regular expression white
            // space pattern.
            if (preg_match('/\s+/A', substr($text, $i), $m)) {
                $i += strlen($m[0]);
                // Return to the start of the loop in case this was white space characters at
                // the end of the string.
                continue;
            }
            // Since we don't have any white space the first thing we look for (top priority)
            // are open brackets.
            if (preg_match(self::$openb, substr($text, $i), $m)) {
                // Check for a non-operator and if one is found assume implicit multiplication.
                if (count($tree) > 0 and (is_array($tree[count($tree) - 1]) or
                    (is_object($tree[count($tree) - 1])
                     and $tree[count($tree) - 1]->n_args() == 0))) {
                    // Make the implicit assumption explicit by adding an appropriate
                    // multiplication operator.
                    array_push($tree, new qtype_algebra_parser_multiply('*'));
                }
                // Push the current parse tree onto the stack.
                array_push($stack, $tree);
                // Create a new parse tree starting with a bracket term.
                $tree = array(new qtype_algebra_parser_bracket($m[0]));
                // Increment the string pointer by the length of the string that was matched.
                $i += strlen($m[0]);
                // Return to the start of the loop.
                continue;
            }
            // Now see if we have a close bracket here.
            if (preg_match(self::$closeb, substr($text, $i), $m)) {
                // First check that the current parse tree has at least one term.
                if (count($tree) == 0) {
                    throw new parser_exception(get_string('badclosebracket', 'qtype_algebra'));
                }
                // Now check that the current tree started with a bracket.
                if (!is_a($tree[0], 'qtype_algebra_parser_bracket')) {
                    throw new parser_exception(get_string('mismatchedcloseb', 'qtype_algebra'));
                } else if ($tree[0]->_value != self::$bramap[$m[0]]) {
                    // Check that the open and close bracket are of the same type.
                    throw new parser_exception(get_string('mismatchedbracket', 'qtype_algebra', $tree[0]->_value.$m[0]));
                }
                // Append the current tree to the tree one level up on the stack.
                array_push($stack[count($stack) - 1], $tree);
                // The new tree is the lowest level tree on the stack so we
                // pop the new tree off the stack.
                $tree = array_pop($stack);
                $i += strlen($m[0]);
                continue;
            }
            // Here we have not found any open or close brackets or known variables so we can
            // parse the string for a normal token.
            foreach ($this->_tokens as $token) {
                if (preg_match($token[0], substr($text, $i), $m)) {
                    if ($token[1] == 'qtype_algebra_parser_identifier') {
                      if (in_array($m[0], self::$functions, 1)) {
                        $token[1] = 'qtype_algebra_parser_function';
                      }
                      else if (in_array($m[0], self::$specials, 1)) {
                        $token[1] = 'qtype_algebra_parser_special';
                      }
                      else if (in_array($m[0], $variables, 1)) {
                        $token[1] = 'qtype_algebra_parser_variable';
                      } else {
                        if (!empty($variables) and !$undecvars) {
                          throw new parser_exception(get_string('undeclaredvar', 'qtype_algebra', $m[0]));
                        }
                        // heretofore unknown identifier, promote to variable:
                        $token[1] = 'qtype_algebra_parser_variable';
                      }
                    }

                    // Check for a zero argument term preceding a variable, function or special and then
                    // add the implicit multiplication.
                    if (count($tree) > 0 and ($token[1] == 'qtype_algebra_parser_variable' or
                        $token[1] == 'qtype_algebra_parser_function' or
                        $token[1] == 'qtype_algebra_parser_special')
                        and (is_array($tree[count($tree) - 1]) or
                        $tree[count($tree) - 1]->n_args() == 0)) {
                        array_push($tree, new qtype_algebra_parser_multiply('*'));
                    }
                    $i += strlen($m[0]);
                    array_push($tree, new $token[1]($m[0]));
                    continue 2;
                }
            }
            throw new parser_exception(get_string('unknownterm', 'qtype_algebra', substr($text, $i)));
        } // End while loop over tokens.
        // If all the open brackets have been closed then the stack will be empty and the
        // tree will contain the entire parsed expression.
        if (count($stack) > 0) {
            throw new parser_exception(get_string('mismatchedopenb', 'qtype_algebra'));
        }
        return $this->interpret($tree);
    }

    /**
     * Takes a structured token map and converts it into a parsed term structure.
     *
     * This is an internal method of the parser class and is called by the {@link parse}
     * method. It performs the final stage of the parsing process and returns the fully
     * parsed term structure.
     *
     * @param $tree structured token array
     * @return top term of the fully parsed structure
     */
    public function interpret($tree) {
        // First check to see if we are passed anything at all. If not then simply
        // return a qtype_algebra_parser_nullterm.
        if (count($tree) == 0) {
            return new qtype_algebra_parser_nullterm;
        }
        // Now we check to see if this tree is inside brackets. If so then
        // we remove the bracket object from the tree and store it in a
        // temporary variable. We will then parse the remainder of the tree
        // and make the top level term the bracket's argument if applicable.
        if (is_a($tree[0], 'qtype_algebra_parser_bracket')) {
            $bracket = array_splice($tree, 0, 1);
            $bracket = $bracket[0];
        } else {
            $bracket = '';
        }
        // Next we loop over the tree and look for arrays. These represent
        // brackets inside our tree and so we need to process them first.
        for ($i = 0; $i < count($tree); $i++) {
            // Check for a list type if we find one then replace
            // it with the interpreted term.
            if (is_array($tree[$i])) {
                $tree[$i] = $this->interpret($tree[$i]);
            }
        }
        // The next job is to check the subtraction operations to determine whether they are
        // really subtraction operations or whether they are minus signs for negative numbers.
        $toremove = array();
        for ($i = 0; $i < count($tree); $i++) {
            // Check that this element is an addition or subtraction operator.
            if (is_a($tree[$i], 'qtype_algebra_parser_subtract') or is_a($tree[$i], 'qtype_algebra_parser_add')) {
                // Check whether the precedding argument (if there is one) is a number or
                // a variable. In either case this is a addition/subtraction operation so we continue.
                if ($i > 0 and (is_a($tree[$i - 1], 'qtype_algebra_parser_variable') or
                             is_a($tree[$i - 1], 'qtype_algebra_parser_number') or
                             is_a($tree[$i - 1], 'qtype_algebra_parser_bracket'))) {
                    continue;
                } else {
                    // Otherwise we have found a minus sign indicating a positive or negative quantity...
                    // Check that we do have a number following otherwise generate an exception...
                    if ($i == (count($tree) - 1) or !method_exists($tree[$i + 1], 'set_negative')) {
                        throw new parser_exception(get_string('illegalplusminus', 'qtype_algebra'));
                    }
                    // If we have a subtract operation then we need to make the following number negative.
                    if (is_a($tree[$i], 'qtype_algebra_parser_subtract')) {
                        // Set the number to be negative.
                        $tree[$i + 1]->set_negative();
                    }
                    // Add the term to the removal list.
                    $toremove[$i] = 1;
                }
            }
        }
        // Remove the elements from the tree who's keys are found in the removal list.
        $tree = array_diff_key($tree, $toremove);
        // Re-key the tree array so that the keys are sequential.
        $tree = array_values($tree);
        foreach (self::$priority as $ops) {
            $i = 0;
            while ($i < count($tree)) {
                if (in_array(get_class($tree[$i]), $ops)) {
                    if ($tree[$i]->n_args() == 1) {
                        if (($i + 1) < count($tree)) {
                            $tree[$i]->set_arguments(array_splice($tree, $i + 1, 1));
                            $i++;
                            continue;
                        } else {
                            throw new parser_exception(get_string('missingonearg', 'qtype_algebra', $tree[$i]->_value));
                        }
                    } else if ($tree[$i]->n_args() == 2) {
                        if ($i > 0 and $i < (count($tree) - 1)) {
                            $tree[$i]->set_arguments(array($tree[$i - 1],
                                                    $tree[$i + 1]));
                            array_splice($tree, $i + 1, 1);
                            array_splice($tree, $i - 1, 1);
                            continue;
                        } else {
                            throw new parser_exception(get_string('missingtwoargs', 'qtype_algebra', $tree[$i]->_value));
                        }
                    }
                } else {
                    $i++;
                }
            }
        }
        // If there are no terms in the parse tree then we were passed an empty string
        // in which case we create a null term and return it.
        if (count($tree) == 0) {
            return new qtype_algebra_parser_nullterm;
        } else if (count($tree) != 1) {
            throw new parser_exception(get_string('notopterm', 'qtype_algebra'));
        }
        if ($bracket) {
            $bracket->set_arguments(array($tree[0]));
            return $bracket;
        } else {
            return $tree[0];
        }
    }
}