function ctools_math_expr::nfx

Convert infix to postfix notation.

Parameters

string $expr: The expression to convert.

Return value

array|bool The expression as an ordered list of postfix action tokens.

File

includes/math-expr.inc, line 410

Class

ctools_math_expr

ctools_math_expr Class.

Code

private function nfx($expr) {
    $index = 0;
    $stack = new ctools_math_expr_stack();
    // Postfix form of expression, to be passed to pfx().
    $output = array();
    // @todo: Because the expr can contain string operands, using strtolower here is a bug.
    $expr = trim(strtolower($expr));
    // We use this in syntax-checking the expression and determining when
    // '-' is a negation.
    $expecting_op = FALSE;
    while (TRUE) {
        $op = substr($expr, $index, 1);
        // Get the first character at the current index, and if the second
        // character is an =, add it to our op as well (accounts for <=).
        if (substr($expr, $index + 1, 1) === '=') {
            $op = substr($expr, $index, 2);
            $index++;
        }
        // Find out if we're currently at the beginning of a number/variable/
        // function/parenthesis/operand.
        $ex = preg_match('/^([a-z]\\w*\\(?|\\d+(?:\\.\\d*)?|\\.\\d+|\\()/', (string) substr($expr, $index), $match);
        // Is it a negation instead of a minus?
        if ($op === '-' and !$expecting_op) {
            // Put a negation on the stack.
            $stack->push('_');
            $index++;
        }
        elseif ($op == '_') {
            return $this->trigger("illegal character '_'");
        }
        elseif ((isset($this->ops[$op]) || $ex) && $expecting_op) {
            // Are we expecting an operator but have a num, var, func, or
            // open-paren?
            if ($ex) {
                $op = '*';
                // It's an implicit multiplication.
                $index--;
            }
            // Heart of the algorithm:
            while ($stack->count() > 0 && ($o2 = $stack->last()) && isset($this->ops[$o2]) && (!empty($this->ops[$op]['right']) ? $this->ops[$op]['precedence'] < $this->ops[$o2]['precedence'] : $this->ops[$op]['precedence'] <= $this->ops[$o2]['precedence'])) {
                // Pop stuff off the stack into the output.
                $output[] = $stack->pop();
            }
            // Many thanks: http://en.wikipedia.org/wiki/Reverse_Polish_notation#The_algorithm_in_detail
            // finally put OUR operator onto the stack.
            $stack->push($op);
            $index++;
            $expecting_op = FALSE;
        }
        elseif ($op === ')') {
            // Pop off the stack back to the last '('.
            while (($o2 = $stack->pop()) !== '(') {
                if (is_null($o2)) {
                    return $this->trigger("unexpected ')'");
                }
                else {
                    $output[] = $o2;
                }
            }
            // Did we just close a function?
            if (preg_match("/^([a-z]\\w*)\\(\$/", (string) $stack->last(2), $matches)) {
                // Get the function name.
                $fnn = $matches[1];
                // See how many arguments there were (cleverly stored on the stack,
                // thank you).
                $arg_count = $stack->pop();
                // Pop the function and push onto the output.
                $output[] = $stack->pop();
                // Check the argument count:
                if (isset($this->funcs[$fnn])) {
                    $fdef = $this->funcs[$fnn];
                    $max_arguments = isset($fdef['max arguments']) ? $fdef['max arguments'] : $fdef['arguments'];
                    if ($arg_count > $max_arguments) {
                        return $this->trigger("too many arguments ({$arg_count} given, {$max_arguments} expected)");
                    }
                }
                elseif (array_key_exists($fnn, $this->userfuncs)) {
                    $fdef = $this->userfuncs[$fnn];
                    if ($arg_count !== count($fdef['args'])) {
                        return $this->trigger("wrong number of arguments ({$arg_count} given, " . count($fdef['args']) . ' expected)');
                    }
                }
                else {
                    // Did we somehow push a non-function on the stack? this should
                    // never happen.
                    return $this->trigger('internal error');
                }
            }
            $index++;
        }
        elseif ($op === ',' && $expecting_op) {
            $index++;
            $expecting_op = FALSE;
        }
        elseif ($op === '(' && !$expecting_op) {
            $stack->push('(');
            $index++;
        }
        elseif ($ex && !$expecting_op) {
            // Make sure there was a function.
            if (preg_match("/^([a-z]\\w*)\\(\$/", (string) $stack->last(3), $matches)) {
                // Pop the argument expression stuff and push onto the output:
                while (($o2 = $stack->pop()) !== '(') {
                    // Oops, never had a '('.
                    if (is_null($o2)) {
                        return $this->trigger("unexpected argument in {$expr} {$o2}");
                    }
                    else {
                        $output[] = $o2;
                    }
                }
                // Increment the argument count.
                $stack->push($stack->pop() + 1);
                // Put the ( back on, we'll need to pop back to it again.
                $stack->push('(');
            }
            // Do we now have a function/variable/number?
            $expecting_op = TRUE;
            $val = (string) $match[1];
            if (preg_match("/^([a-z]\\w*)\\(\$/", $val, $matches)) {
                // May be func, or variable w/ implicit multiplication against
                // parentheses...
                if (isset($this->funcs[$matches[1]]) or array_key_exists($matches[1], $this->userfuncs)) {
                    $stack->push($val);
                    $stack->push(0);
                    $stack->push('(');
                    $expecting_op = FALSE;
                }
                else {
                    $val = $matches[1];
                    $output[] = $val;
                }
            }
            else {
                $output[] = $val;
            }
            $index += strlen($val);
        }
        elseif ($op === ')') {
            // Miscellaneous error checking.
            return $this->trigger("unexpected ')'");
        }
        elseif (isset($this->ops[$op]) and !$expecting_op) {
            return $this->trigger("unexpected operator '{$op}'");
        }
        elseif ($op === '"') {
            // Fetch a quoted string.
            $string = (string) substr($expr, $index);
            if (preg_match('/"[^"\\\\]*(?:\\\\.[^"\\\\]*)*"/s', $string, $matches)) {
                $string = $matches[0];
                // Trim the quotes off:
                $output[] = $string;
                $index += strlen($string);
                $expecting_op = TRUE;
            }
            else {
                return $this->trigger('open quote without close quote.');
            }
        }
        else {
            // I don't even want to know what you did to get here.
            return $this->trigger("an unexpected error occurred at {$op}");
        }
        if ($index === strlen($expr)) {
            if (isset($this->ops[$op])) {
                // Did we end with an operator? bad.
                return $this->trigger("operator '{$op}' lacks operand");
            }
            else {
                break;
            }
        }
        // Step the index past whitespace (pretty much turns whitespace into
        // implicit multiplication if no operator is there).
        while (substr($expr, $index, 1) === ' ') {
            $index++;
        }
    }
    // Pop everything off the stack and push onto output:
    while (!is_null($op = $stack->pop())) {
        // If there are (s on the stack, ()s were unbalanced.
        if ($op === '(') {
            return $this->trigger("expecting ')'");
        }
        $output[] = $op;
    }
    return $output;
}