<file_sep><?php

    require("new_slice.php");
    require("unary_minus.php");
    require("tokenizer.php");
    require("shunting_yard.php");
    require("compare.php");

    // always run this function first before doing anything else
    // relied upon by tokenizer and shunting_yard
    declare_globals();

?>
<file_sep><?php

    function declare_globals() {

        // operators
        // presence of OR as operator for answers with multiple answers (i.e., roots of a quadratic)
        // - is used as a function, not as an operator, to deal with unary minuses (i.e "-3+12PI")
        $GLOBALS["operators"] = [
            '+' => ['precedence' => 0, 'associativity' => 'left', 'commutativity' => true],
            '*' => ['precedence' => 1, 'associativity' => 'left', 'commutativity' => true],
            '/' => ['precedence' => 1, 'associativity' => 'left', 'commutativity' => false],
            '%' => ['precedence' => 1, 'associativity' => 'left', 'commutativity' => false],
            '^' => ['precedence' => 2, 'associativity' => 'right', 'commutativity' => false],
            'OR' => ['precedence' => -1, 'associativity' => 'left', 'commutativity' => true]
        ];

        // specials
        $GLOBALS["specials"] = ['PI', 'E', 'I'];

        // functions
        $GLOBALS["functions"] = [
            'SQRT',
            'ABS',
            'ACOS',
            'COS',
            'TAN',
            'ATAN',
            'ASIN',
            'SIN',
            'CEIL',
            'FLOOR',
            'LOG',
            'LN'
        ];

        // regexes for matching each type of token
        $GLOBALS["format_regexes"] = [
            "number" => "(\d+\.?\d*)",
            "special" => "(PI|E|I)",
            "lparen" => "(\()",
            "rparen" => "(\))",
            "function" => "(SQRT|ABS|ACOS|COS|ATAN|TAN|ASIN|SIN|CEIL|FLOOR|LOG|LN)",
            "operator" => "(\+|\-|\*|\/|\^|OR)",
            "suffix" => "(%|$)"
        ];

        // replace patterns for preg_replace() for formatting tokens
        $GLOBALS["format_replaces"] = [
            "generic_implicit" => "$1 * $2",
            "number_lparen_implicit" => "$1 * (",
            "operator_space" =>  " $1 $2",
            "paren_space" => " $1 "
        ];

    }

    function format($expr) {

        // implicit multiplication

        $regexes = [
            // implicit multiplication
            "/" . $GLOBALS["format_regexes"]["number"] . $GLOBALS["format_regexes"]["special"] . "/", // number, then special
            "/" . $GLOBALS["format_regexes"]["special"] . $GLOBALS["format_regexes"]["number"] . "/", // special, then number
            "/" . $GLOBALS["format_regexes"]["special"] . $GLOBALS["format_regexes"]["special"] . "/", // special, then special
            "/(" . $GLOBALS["format_regexes"]["number"] . "|" . $GLOBALS["format_regexes"]["special"] . ")" . $GLOBALS["format_regexes"]["lparen"] . "/", // number or special, then lparen
            "/" . $GLOBALS["format_regexes"]["rparen"] . "(" . $GLOBALS["format_regexes"]["number"] . "|" . $GLOBALS["format_regexes"]["special"] . ")/", // rparen, then number or special
            "/" . $GLOBALS["format_regexes"]["number"] . $GLOBALS["format_regexes"]["function"] . "/", // number, then unary function
            "/" . $GLOBALS["format_regexes"]["special"] . $GLOBALS["format_regexes"]["function"] . "/", // special, then unary function

            // operator spacing
            "/" . $GLOBALS["format_regexes"]["operator"] . "/", // add spaces before and after each operator

            // parenthesis spacing
            "/(" . $GLOBALS["format_regexes"]["lparen"] . "|" . $GLOBALS["format_regexes"]["rparen"] . ")/" // add spaces before and after lparen and rparen

        ];

        $replaces = [
            // implicit multiplication
            $GLOBALS["format_replaces"]["generic_implicit"], // number, then special
            $GLOBALS["format_replaces"]["generic_implicit"], // special, then number
            $GLOBALS["format_replaces"]["generic_implicit"], // special, then special
            $GLOBALS["format_replaces"]["number_lparen_implicit"], // number or special, then lparen
            $GLOBALS["format_replaces"]["generic_implicit"], // rparen, then number or special
            $GLOBALS["format_replaces"]["generic_implicit"], // number, then unary function
            $GLOBALS["format_replaces"]["generic_implicit"], // special, then unary function


            // operator spacing
            $GLOBALS["format_replaces"]["operator_space"], //add spaces before and after each operator

            // parenthesis spacing
            $GLOBALS["format_replaces"]["paren_space"], // add spaces before and after lparen and rparen
        ];

        return strtoupper(preg_replace($regexes, $replaces, $expr));

    }

    function tokenize($expr) {

        // remove leading and trailing spaces
        $expr = preg_replace('/\G\s|\s(?=\s*$)/', '', format($expr));

        // replace >=2 spaces with only one space and explode to array
        // then make all minuses unary
        $tokens = fix_minus(array_map('trim', explode(' ', preg_replace('/[ ]+/', ' ', $expr))));

        // get count removing parentheses to reduce steps in shunting_yard()
        $count = 0;
        foreach ($tokens as $token) {
            $count = (!preg_match("/(" . $GLOBALS["format_regexes"]["lparen"] . "|" . $GLOBALS["format_regexes"]["rparen"] . ")/", $token)) ? $count + 1 : $count;
        }
        // return array with tokenized array and count
        return [$tokens, $count];

    }


?>
<file_sep><?php

    // PHP's default array_slice doesn't support arrays without zero index.
    // Therefore, this is a new function, written in PHP, to add this functionality.
    // Assume keys are all numerical, consecutive, and in increasing order.
    function new_slice($input_arr, $offset, $length = NULL, $preserve_keys = false) {

        // error checking for $offset
        if (!isset($input_arr[$offset]))
            throw new \InvalidArgumentException(sprintf("Offset %d doesn't exist in array.", $offset));

        else {

            $output_arr = [];

            // if length is set, we will iterate through ($offset + $length)
            if (isset($length)) {
                // if $preserve_keys is set to true, $output_arr is treated like
                // an associative array with numerical keys
                if ($preserve_keys) {
                    for ($cur = $offset, $end = $offset + $length; $cur < $end; $cur++) {
                        $output_arr[$cur] = $input_arr[$cur];
                    }
                }
                // otherwise the keys are ignored and elements are simply added
                // to $output_arr
                else {
                    for ($cur = $offset, $end = $offset + $length; $cur < $end; $cur++) {
                        $output_arr[] = $input_arr[$cur];
                    }
                }
            }
            // same as above, but length is not set so we iterate through the
            // end of the array
            else {
                if ($preserve_keys) {
                    for ($cur = $offset, $end = max(array_keys($input_arr)) + 1; $cur < $end; $cur++) {
                        $output_arr[$cur] = $input_arr[$cur];
                    }
                }
                else {
                    for ($cur = $offset, $end = max(array_keys($input_arr)) + 1; $cur < $end; $cur++) {
                        $output_arr[] = $input_arr[$cur];
                    }
                }
            }
            return $output_arr;
        }
    }

?>
<file_sep><?php

    function compare($arr1, $arr2) {

        // immediately return true if arrays are the same
        if ($arr1 == $arr2)
            return true;

        elseif (count($arr1) != count($arr2))
            return false;

        else {

            // otherwise run usual block_compare
            $compares = [];
            $compares = block_compare($arr1, $arr2, $compares);
            return !in_array(0, $compares);

        }

    }

    // compare simplest order operation
    // $e1, $e2 each have one unary operator and two special constant/numerical operands
    function simple_compare($e1, $e2) {

        // get first item in array
        $e1_min = min(array_keys($e1));
        $e2_min = min(array_keys($e2));

        if ($e1[$e1_min]["symbol"] == $e2[$e2_min]["symbol"]) {
            // compare linearly (first op1 and second op1, then same with op2)
            if ($e1[$e1_min + 1]["value"] == $e2[$e2_min + 1]["value"] &&
                $e1[$e1_min + 2]["value"] == $e2[$e2_min + 2]["value"]) {
                return true;
            }
            // cross compare (first op2 and second op1 and converse) if commutative operator
            elseif (($GLOBALS["operators"][$e1[$e1_min]["symbol"]]['commutativity'] === true) &&
                     $e1[$e1_min + 1] == $e2[$e2_min + 2] &&
                     $e1[$e1_min + 2] == $e2[$e2_min + 1]) {
                return true;
            }
            else {
                return false;
            }

        }
        else {
            return false;
        }

    }

    // compare blocks
    function block_compare($e1, $e2, $compares) {

        // minimum key in array
        $e1_min = min(array_keys($e1));
        $e2_min = min(array_keys($e2));

        // if lengths are different they are not the same
        if (count($e1) != count($e2)) {
            $compares[] = 0;
            return $compares;
        }
        // if each block is a unary function block only, go to unary_func_compare
        elseif ($e1[$e1_min]["type"] == "function" && $e2[$e2_min]["type"] == "function") {
            $compares = unary_func_compare($e1, $e2, $compares);
            return $compares;
        }
        else {

            // expr operators
            $e1_operator = $e1[$e1_min];
            $e2_operator = $e2[$e2_min];

            // find expr operand blocks
            $e1_op1 = new_slice($e1, $e1[$e1_min]["op1_ndx"],
                               ($e1[$e1_min]["op2_ndx"] - $e1[$e1_min]["op1_ndx"]), true);
            $e1_op2 = new_slice($e1, $e1[$e1_min]["op2_ndx"], NULL, true);
            $e2_op1 = new_slice($e2, $e2[$e2_min]["op1_ndx"],
                               ($e2[$e2_min]["op2_ndx"] - $e2[$e2_min]["op1_ndx"]), true);
            $e2_op2 = new_slice($e2, $e2[$e2_min]["op2_ndx"], NULL, true);

            $e1_op1_min = min(array_keys($e1_op1));
            $e1_op2_min = min(array_keys($e1_op2));
            $e2_op1_min = min(array_keys($e2_op1));
            $e2_op2_min = min(array_keys($e2_op2));

            // simple block, for comparison at simple_compare
            $e1_op1_issblock = (count($e1_op1) == 3) ? 1 : 0;
            $e1_op2_issblock = (count($e1_op2) == 3) ? 1 : 0;
            $e2_op1_issblock = (count($e2_op1) == 3) ? 1 : 0;
            $e2_op2_issblock = (count($e2_op2) == 3) ? 1 : 0;

            // complex block, should be returned to block_compare
            $e1_op1_iscblock = (count($e1_op1) > 3) ? 1 : 0;
            $e1_op2_iscblock = (count($e1_op2) > 3) ? 1 : 0;
            $e2_op1_iscblock = (count($e2_op1) > 3) ? 1 : 0;
            $e2_op2_iscblock = (count($e2_op2) > 3) ? 1 : 0;

            // numerical/special value only, can be compared straightaway
            $e1_op1_isval = (count($e1_op1) == 1) ? 1 : 0;
            $e1_op2_isval = (count($e1_op2) == 1) ? 1 : 0;
            $e2_op1_isval = (count($e2_op1) == 1) ? 1 : 0;
            $e2_op2_isval = (count($e2_op2) == 1) ? 1 : 0;

            // unary function only, for unary_func_compare
            $e1_op1_isublock = ($e1_op1[$e1_op1_min]["type"] == "function") ? 1 : 0;
            $e1_op2_isublock = ($e1_op2[$e1_op2_min]["type"] == "function") ? 1 : 0;
            $e2_op1_isublock = ($e2_op1[$e2_op1_min]["type"] == "function") ? 1 : 0;
            $e2_op2_isublock = ($e2_op2[$e2_op2_min]["type"] == "function") ? 1 : 0;

            if ($e1_operator["symbol"] != $e2_operator["symbol"])
                $compares[] = 0;

            else {

                // if we need to compare intermediately for purposes of
                // mutual exclusivity, we have an array without tainting $compares
                $interm_compares = [];

                if ($e1_op1_issblock && $e2_op1_issblock && simple_compare($e1_op1, $e2_op1)) {

                    $compares[] = 1;
                    $compares = template_compare($e1_op2, $e2_op2, $compares);


                }

                elseif (($GLOBALS["operators"][$e1_operator["symbol"]]['commutativity'] === true)
                         && $e1_op1_issblock && $e2_op2_issblock && simple_compare($e1_op1, $e2_op2)) {

                    $compares[] = 1;
                    $compares = template_compare($e1_op2, $e2_op1, $compares);


                }
                elseif ($e1_op1_iscblock && $e2_op1_iscblock &&
                        !in_array(0, block_compare($e1_op1, $e2_op1, $interm_compares))) {

                    $compares[] = 1;
                    $interm_compares = [];
                    $compares = template_compare($e1_op2, $e2_op2, $compares);


                }
                elseif (($GLOBALS["operators"][$e1_operator["symbol"]]['commutativity'] === true) &&
                         $e1_op1_iscblock && $e2_op2_iscblock &&
                         !in_array(0, block_compare($e1_op1, $e2_op2, $interm_compares))) {

                     $compares[] = 1;
                     $interm_compares = [];
                     $compares = template_compare($e1_op2, $e2_op1, $compares);


                }
                elseif ($e1_op1_isublock && $e2_op1_isublock &&
                        !in_array(0, unary_func_compare($e1_op1, $e2_op1, $interm_compares))) {

                    $compares[] = 1;
                    $interm_compares = [];
                    $compares = template_compare($e1_op2, $e2_op2, $compares);


                }
                elseif (($GLOBALS["operators"][$e1_operator["symbol"]]['commutativity'] === true) &&
                        $e1_op1_isublock && $e2_op2_isublock &&
                        !in_array(0, unary_func_compare($e1_op1, $e2_op2, $interm_compares))) {

                    $compares[] = 1;
                    $interm_compares = [];
                    $compares = template_compare($e1_op2, $e2_op1, $compares);


                }
                elseif ($e1_op1_isval && $e2_op1_isval &&
                        $e1_op1[$e1_op1_min]["value"] == $e2_op1[$e2_op1_min]["value"]) {

                    $compares[] = 1;
                    $compares = template_compare($e1_op2, $e2_op2, $compares);


                }
                elseif (($GLOBALS["operators"][$e1_operator["symbol"]]['commutativity'] === true)
                         && $e1_op1_isval && $e2_op2_isval &&
                         $e1_op1[$e1_op1_min]["value"] == $e2_op2[$e2_op2_min]["value"]) {

                    $compares[] = 1;
                    $compares = template_compare($e1_op2, $e2_op1, $compares);
                }

                else {
                    $compares[] = 0;
                }
                return $compares;
            }
        }
    }

    // compare unary functions
    function unary_func_compare($e1, $e2, $compares) {

        // find minimum value in numerical array keys
        $e1_min = min(array_keys($e1));
        $e2_min = min(array_keys($e2));

        // get function name
        $e1_function = $e1[$e1_min];
        $e2_function = $e2[$e2_min];

        // get operands
        $e1_op = new_slice($e1, $e1[$e1_min]["op_ndx"], NULL, true);
        $e2_op = new_slice($e2, $e2[$e2_min]["op_ndx"], NULL, true);

        $e1_op_min = min(array_keys($e1_op));
        $e2_op_min = min(array_keys($e2_op));

        if ($e1_function["name"] != $e2_function["name"]) {
            $compares[] = 0;
        }

        else
            $compares = template_compare($e1_op, $e2_op, $compares);

        return $compares;

    }

    function template_compare($b1, $b2, $compares) {

        $b1_min = min(array_keys($b1));
        $b2_min = min(array_keys($b2));

        // simple block
        $b1_issblock = (count($b1) == 3) ? 1 : 0;
        $b2_issblock = (count($b2) == 3) ? 1 : 0;

        // complex block with unary functions
        $b1_iscblock = (count($b1) > 3) ? 1 : 0;
        $b2_iscblock = (count($b2) > 3) ? 1 : 0;

        // numerical/special value only
        $b1_isval = (count($b1) == 1) ? 1 : 0;
        $b2_isval = (count($b2) == 1) ? 1 : 0;

        // unary function only
        $b1_isublock = ($b1[$b1_min]["type"] == "function") ? 1 : 0;
        $b2_isublock = ($b2[$b2_min]["type"] == "function") ? 1 : 0;

        // if simple block return to simple_compare
        if ($b1_issblock && $b2_issblock)
            $compares[] = simple_compare($b1, $b2) ? 1 : 0;
        // if complex block feed to block_compare
        elseif ($b1_iscblock && $b2_iscblock)
            $compares = block_compare($b1, $b2, $compares);
        // if unary function only block go to unary_func_compare
        elseif ($b1_isublock && $b2_isublock)
            $compares = unary_func_compare($b1, $b2, $compares);
        // if single value compare it right here
        elseif($b1_isval && $b2_isval)
            $compares[] = ($b1[$b1_min]["value"] == $b2[$b2_min]["value"]) ? 1 : 0;
        else
            $compares[] = 0;

        return $compares;

    }

?>
<file_sep># MCGExpression
This is a PHP expression parser and comparison tool, written to grade MathCounts answers for http://github.com/saligrama/mathcountsgrading

Setup
-----

Clone the repository.
```bash
$ git clone http://github.com/saligrama/MCGExpression
```

Usage
-----

In `MCGExpression/main.php`, you'll find these contents.
```php
#!/usr/bin/env php
<?php

    require("new_slice.php");
    require("unary_minus.php");
    require("tokenizer.php");
    require("shunting_yard.php");
    require("compare.php");

    // always run this function first before doing anything else
    // relied upon by tokenizer and shunting_yard
    declare_globals();

?>
```
In this state, the system does nothing. You can add something like this to the end.

```php
$expr1 = "-3-7SQRT(8PI-1)";
$expr2 = "-7SQRT(-1+8PI)-3";

$e1_tok = tokenize($expr1);
$e2_tok = tokenize($expr2);

echo compare(
    shunting_yard($e1_tok[0], $e1_tok[1]),
    shunting_yard($e2_tok[0], $e2_tok[1])
);
```

Run the program:

```bash
$ ./main.php
```

The result from the code above:

    1

You can change the values for `$expr1` and `$expr2` and play around with the system.

Constants and functions can be entered as below:

| Constant/function | Enter as |
| ----------------- | -------- |
| π | `PI` |
| √ | `SQRT` |
| e | `E` |
| i | `I` |
| sin, cos, tan, and other functions | Uppercased text representation |

For more details, please view the `declare_globals()` function in `MCGExpression/tokenizer.php`.
<file_sep><?php

    function fix_minus($input) {

        // get total minus count
        $total_minus_count = get_total_minus_count($input);

        // if there are no minuses return input without modifications
        if ($total_minus_count == 0)
            return $input;

        // get count of fixed minuses
        $fixed_minus_count = get_fixed_minus_count($input);

        // while there are unfixed minus go through and correct them
        while ($fixed_minus_count < $total_minus_count) {

            // get first unfixed minus
            $pos = get_unfixed_minus($input);
            if ($pos !== null) {

                // add plus before the minus if unary minus is not at beginning
                if (add_plus($input, $pos))
                    array_splice($input, $pos, 0, '+');

                // add lparen after minus
                array_splice($input, $pos + (!(add_plus($input, $pos)) ? 1 : 2), 0, '(');

                // complete the rparen
                $input = complete_minus_parens($input, $pos + (!add_plus($input, $pos) ? 2 : 3));

            }
            $fixed_minus_count = get_fixed_minus_count($input);

        }

        return $input;

    }

    // minus is fixed once there is an lparen after it
    // matching rparen is always added before function is run
    function is_fixed($input, $pos) { return ($input[$pos] == '-' && $input[$pos + 1] == '('); }

    // get first unfixed minus in array for correction
    function get_unfixed_minus($input) {
        for ($i = 0, $c = count($input); $i < $c; $i++) {
            if ($input[$i] == '-' && !is_fixed($input, $i)) {
                return $i;
            }
        }
        return null;
    }

    // get number of fixed minuses
    function get_fixed_minus_count($input) {
        $fixed_minus_count = 0;
        for ($i = 0, $c = count($input); $i < $c; $i++) {
            $fixed_minus_count += is_fixed($input, $i) ? 1 : 0;
        }
        return $fixed_minus_count;
    }

    // get total number of minuses
    // PHP builtin array_count_values throws errors if there are no minuses,
    // so we build this simple function to do it
    function get_total_minus_count($input) {
        $total_minus_count = 0;
        for ($i = 0, $c = count($input); $i < $c; $i++) {
            $total_minus_count += ($input[$i] == '-') ? 1 : 0;
        }
        return $total_minus_count;
    }

    // check if a plus should be added before a minus
    // do not add a plus if the minus is the first thing in the array
    // or if it is the first thing after a left parenthesis
    // or if it is the first thing after a lower precedence operator
    function add_plus($input, $pos) {
        return !($pos == 0 ||
                 (isset($input[$pos-1]) && ($input[$pos-1] == '(' ||
                  isset($GLOBALS['operators'][$input[$pos-1]]) &&
                  $GLOBALS['operators'][$input[$pos-1]]['precedence'] < 0)));
    }

    // inject rparen to complete minus operand wrapping
    function complete_minus_parens($input, $op_start) {
        $pos = $op_start;
        // track open parens
        $open_paren_count = 0;
        // track if parens were ever open (for case of minuses in parenthesis)
        $ever_open_paren = false;
        for ($i = $pos, $c = count($input); $i < $c; $i++) {
            // if no parens are open and we hit something with <= precedence as minus
            // complete the rparen
            if ($open_paren_count == 0 && isset($GLOBALS['operators'][$input[$i]]) &&
                $GLOBALS['operators'][$input[$i]]['precedence'] <= 1) {
                array_splice($input, $i, 0, ')');
                break;
            }
            // if we hit the end of the array, complete the rparen
            elseif ($i == max(array_keys($input))) {
                array_splice($input, $i+1, 0, ')');
                break;
            }
            // note if any parens were open
            elseif ($input[$i] == '(') {
                $open_paren_count++;
                $ever_open_paren = true;
            }
            // if we hit an rparen there are two ways to insert the rparen
            elseif($input[$i] == ')') {
                // if there was never a paren open insert the minus rparen
                // before rparen at $i
                if (!$ever_open_paren) {
                    array_splice($input, $i, 0, ')');
                    break;
                }
                // mark that any open paren has been closed
                $open_paren_count--;
                // if an rparen has been closed, insert the minus rparen
                // after rparen at $i
                if ($open_paren_count == 0) {
                    array_splice($input, $i+1, 0, ')');
                    break;
                }
            }
        }

        return $input;

    }

?>
<file_sep><?php

    // modified Shunting-Yard algorithm with support for prefix notation,
    // storing of operand locations, and unary functions
    // see https://en.wikipedia.org/wiki/Shunting-yard_algorithm
    function shunting_yard(array $tokens, $length) {

        $stack = new \SplStack();
        $output = new \SplQueue();

        // iterate through tokens in reverse order to convert to prefix (Polish) notation
        foreach (array_reverse($tokens) as $token) {
            // if token is an operand (number or special constant) add to output queue
            if (is_numeric($token) ||
                preg_match("/" . $GLOBALS["format_regexes"]["special"] . "/", $token)) {
                $output->enqueue([
                    'type' => 'operand',
                    'value' => $token
                ]);
                $last_popped_lparen = 0;
            }
            // if we have an operator push it to the stack while moving existing
            // operators on the stack to output queue
            elseif (isset($GLOBALS["operators"][$token])) {
                $o1 = $token;
                while (has_operator($stack) && ($o2 = $stack->top()) && has_lower_precedence($o1, $o2)) {
                    $c = count($output);
                    $output->enqueue([
                        'type' => 'operator',
                        'symbol' => $stack->pop(),
                        'op1_ndx' => $length - $c, // store metadata for easy comparison
                        'op2_ndx' => getoperand_base($output, $c)
                    ]);
                    $last_popped_lparen = 0;
                }
                $stack->push($o1);
            }
            elseif (')' === $token) {
                $stack->push($token); // wait untill we see an lparen
            }
            elseif ('(' === $token) {
                // if something is on the stack it is either an rparen or an operator
                // we now move the operators to the output queue, again storing metadata
                while (count($stack) > 0 && ')' !== $stack->top()) {
                    $c = count($output);
                    $output->enqueue([
                        'type' => 'operator',
                        'symbol' => $stack->pop(),
                        'op1_ndx' => $length - $c,
                        'op2_ndx' => getoperand_base($output, $c)
                    ]);
                }
                if (count($stack) === 0) {
                    throw new \InvalidArgumentException(sprintf('Mismatched parenthesis in input: %s', json_encode($tokens)));
                }
                // pop off lparen
                $stack->pop();
                $last_popped_lparen = 1;
            }
            // if it's a unary function (including minus) and the last argument
            // found was an lparen we directly move it to the stack while storing metadata
            elseif (preg_match("/" . preg_replace("/(\))/", "|-$1", $GLOBALS["format_regexes"]["function"]) . "/", $token)) {
                if ($last_popped_lparen || $stack->top() == ')') {
                    $c = count($output);
                    $output->enqueue([
                        'type' => 'function',
                        'name' => $token,
                        'op_ndx' => $c - 1
                    ]);
                }
                else {
                    throw new \InvalidArgumentException(sprintf('Function %s does not have parenthesis', $token));
                }
            }
            else {
                throw new \InvalidArgumentException(sprintf('Invalid token: %s', $token));
            }
        }
        // add to queue any last operators remaining in the stack
        while (has_operator($stack)) {
            $c = count($output);
            $output->enqueue([
                'type' => 'operator',
                'symbol' => $stack->pop(),
                'op1_ndx' => $length - $c,
                'op2_ndx' => getoperand_base($output, $c)
            ]);
        }
        if (count($stack) > 0) {
            throw new \InvalidArgumentException(sprintf('Mismatched parenthesis or misplaced number in input: %s', json_encode($tokens)));
        }
        // reverse the queue to make it normal prefix notation
        $pn = array_reverse(iterator_to_array($output));

        // fix all operand locations afer reverse
        // we couldn't do this above since finding operands relies on locations
        // set in the existing queue
        $i = 0;
        while(isset($pn[$i])) {

            if ($pn[$i]["type"] == "operator")
                $pn[$i]["op2_ndx"] = $length - $pn[$i]["op2_ndx"] - 1;
            elseif($pn[$i]["type"] == "function")
                $pn[$i]["op_ndx"] = $length - $pn[$i]["op_ndx"] - 1;

            $i++;

        }

        return $pn;

    }

    // check if there's an operator on the top of the stack
    function has_operator(\SplStack $stack) {
        return count($stack) > 0 && ($top = $stack->top()) && isset($GLOBALS["operators"][$top]);
    }

    // check if precedence of $o1 is less than that of $o2
    function has_lower_precedence($o1, $o2) {
        $op1 = $GLOBALS["operators"][$o1];
        $op2 = $GLOBALS["operators"][$o2];
        return ($op1['associativity'] === 'left'
                && $op1['precedence'] === $op2['precedence'])
                || $op1['precedence'] < $op2['precedence'];
    }


    // finds operands for an operator
    function getoperand_base(\SplQueue $output, $ndx) {

        // if the next item in queue is an operator, we find the end of its second operand
        if ($output[$ndx - 1]["type"] == "operator")
            return end_of_opchain($output, $output[$ndx - 1]["op2_ndx"]) - 1;
        // if it is a unary function, find the end of its other operand
        elseif ($output[$ndx - 1]["type"] == "function")
            return end_of_opchain($output, $output[$ndx - 1]["op_ndx"]) - 1;
        // otherwise if it is a value, return the next item after that value
        else
            return $ndx - 2;

    }

    // iterate until we find a number or special as an operator index (unary function)
    // or the second index of operand (for an operator)
    function end_of_opchain(\SplQueue $output, $ndx) {

        if ($output[$ndx]["type"] == "operator")
            return end_of_opchain($output, $output[$ndx]["op2_ndx"]);
        elseif($output[$ndx]["type"] == "function")
            return end_of_opchain($output, $output[$ndx]["op_ndx"]);
        else
            return $ndx;

    }


?>
