<?php
/**
 * Equation Operating System Classes.
 *
 * This class was created for the safe parsing of mathematical equations
 * in PHP.  There is a need for a way to successfully parse equations
 * in PHP that do NOT require the use of `eval`.  `eval` at its core
 * opens the system using it to so many security vulnerabilities it is oft
 * suggested /never/ to use it, and for good reason.  This class set will
 * successfully take an equation, parse it, and provide solutions to the
 * developer.  It is a safe way to evaluate expressions without putting
 * the system at risk.
 *
 *
 * @author Jon Lawrence <jlawrence11@gmail.com>
 * @copyright Copyright ©2005-2015, Jon Lawrence
 * @license http://opensource.org/licenses/LGPL-2.1 LGPL 2.1 License
 * @version 3.0.0
 */

namespace jlawrence\eos;


/**
 * Equation Operating System (EOS) Parser
 *
 * A class that can safely parse mathematical equations.  Re-written portions
 * from version 2.x to be extend-able with custom functions.
 *
 * @author Jon Lawrence <jlawrence11@gmail.com>
 * @copyright Copyright ©2005-2015, Jon Lawrence
 * @license http://opensource.org/licenses/LGPL-2.1 LGPL 2.1 License
 * @version 3.0.0
 */
class Parser {

    /**
     * @var string Infix equation
     * Public so advanced/user-defined/etc can access it when throwing exceptions.
     */
    public static $inFix;

    /**
     * @var array Opening and closing selectors
     */
    protected static $SEP = array(
        'open' => array('(', '['),
        'close' => array(')', ']')
    );

    // Top precedence following operator - not in use
    protected static $SGL = array('!');

    // Order of operations arrays follow
    protected static $ST = array('^', '!');
    protected static $ST1 = array('/', '*', '%');
    protected static $ST2 = array('+', '-');

    /**
     * @var array Allowed functions
     */
    protected static $FNC = array(
        'sin', 'cos', 'tan',
        'csc', 'sec', 'cot',
        'abs', 'ln', 'sqrt'
    );

    /**
     * @var array Advanced functions container
     */
    protected static $AFNC = array();

    /**
     * Initialize
     */
    public static function init() {
        if (empty(self::$AFNC)) {
            //No advanced functions yet, so this function has not run, do so now.
            self::$AFNC = AdvancedFunctions::map();
        }
    }

    /**
     * Add Advanced Function Class
     *
     * Adds a function class to the parser for user/programmer defined
     * functions that can be parsed with the parser.  For example
     * class structure see jlawrence\eos\AdvancedFunctions.
     * Class must be static, and must have a function named 'map'
     *
     * @param string $class Fully Qualified String to class (must include namespace)
     * @return bool True on success
     * @throws \Exception When the added class doesn't have the 'map' function or doesn't exist.
     *
     * @codeCoverageIgnore
     */
    public static function addFunctionClass($class)
    {
        self::init();
        if(is_callable("{$class}::map")) {
            $a = call_user_func($class.'::map');
            self::$AFNC = array_merge($a, self::$AFNC);
        } else {
            throw new \Exception("{$class}::map() is not callable");
        }
        return true;
    }

    /**
     * Check Infix for opening closing pair matches.
     *
     * This function is meant to solely check to make sure every opening
     * statement has a matching closing one, and throws an exception if
     * it doesn't.
     *
     * @param string $infix Equation to check
     * @throws \Exception if malformed.
     * @return Bool true if passes - throws an exception if not.
     */
    private static function checkInfix($infix) {
        self::init();
        if(trim($infix) == "") {
            throw new \Exception("No Equation given", Math::E_NO_EQ);
        }
        //Make sure we have the same number of '(' as we do ')'
        // and the same # of '[' as we do ']'
        if(substr_count($infix, '(') != substr_count($infix, ')')) {
            throw new \Exception("Mismatched parenthesis in ". self::$inFix, Math::E_NO_SET);
        } elseif(substr_count($infix, '[') != substr_count($infix, ']')) {
            throw new \Exception("Mismatched brackets in '". self::$inFix, Math::E_NO_SET);
        }
        return true;
    }

    /**
     * Infix to Postfix
     *
     * Converts an infix (standard) equation to postfix (RPN) notation.
     * Sets the internal variable $this->postFix for the Parser::solvePF()
     * function to use.
     *
     * @link http://en.wikipedia.org/wiki/Infix_notation Infix Notation
     * @link http://en.wikipedia.org/wiki/Reverse_Polish_notation Reverse Polish Notation
     * @param string $infix A standard notation equation
     * @throws \Exception When parenthesis are mismatched
     * @return array Fully formed RPN Stack
     */
    public static function in2post($infix) {
        // if an equation was not passed, use the one that was passed in the constructor
        //$infix = (isset($infix)) ? $infix : $this->inFix;

        //check to make sure 'valid' equation
        self::checkInfix($infix);
        $pf = array();
        $ops = new Stack();
        //$vars = new Stack();

        // remove all white-space
        $infix = preg_replace("/\s/", "", $infix);

        // Create postfix array index
        $pfIndex = 0;

        //what was the last character? (useful for discerning between a sign for negation and subtraction)
        $lChar = '';

        //loop through all the characters and start doing stuff ^^
        for($i=0;$i<strlen($infix);$i++) {
            // pull out 1 character from the string
            $chr = substr($infix, $i, 1);

            // if the character is numerical
            if(preg_match('/[0-9.]/i', $chr)) {
                // if the previous character was not a '-' or a number
                if((!preg_match('/[0-9.]/i', $lChar) && ($lChar != "")) && (isset($pf[$pfIndex]) && ($pf[$pfIndex]!="-")))
                    $pfIndex++;	// increase the index so as not to overlap anything
                // Add the number character to the array
                if(isset($pf[$pfIndex])) {
                    $pf[$pfIndex] .= $chr;
                } else {
                    $pf[$pfIndex] = $chr;
                }

            }
            // If the character opens a set e.g. '(' or '['
            elseif(in_array($chr, self::$SEP['open'])) {
                // if the last character was a number, place an assumed '*' on the stack
                if(preg_match('/[0-9.]/i', $lChar))
                    $ops->push('*');

                $ops->push($chr);
            }
            // if the character closes a set e.g. ')' or ']'
            elseif(in_array($chr, self::$SEP['close'])) {
                // find what set it was i.e. matches ')' with '(' or ']' with '['
                $key = array_search($chr, self::$SEP['close']);
                // while the operator on the stack isn't the matching pair...pop it off
                while($ops->peek() != self::$SEP['open'][$key]) {
                    $nchr = $ops->pop();
                    if($nchr)
                        $pf[++$pfIndex] = $nchr;
                    else {
                        //Should NEVER get here...
                        // @codeCoverageIgnoreStart
                        throw new \Exception("Error while searching for '". self::$SEP['open'][$key] ."' in ". self::$inFix, Math::E_NO_SET);
                        // @codeCoverageIgnoreEnd
                    }
                }
                $ops->pop();
            }
            // If a special operator that has precedence over everything else
            elseif(in_array($chr, self::$ST)) {
                while(in_array($ops->peek(), self::$ST))
                    $pf[++$pfIndex] = $ops->pop();
                $ops->push($chr);
                $pfIndex++;
            }
            // Any other operator other than '+' and '-'
            elseif(in_array($chr, self::$ST1)) {
                while(in_array($ops->peek(), self::$ST1) || in_array($ops->peek(), self::$ST))
                    $pf[++$pfIndex] = $ops->pop();

                $ops->push($chr);
                $pfIndex++;
            }
            // if a '+' or '-'
            elseif(in_array($chr, self::$ST2)) {
                // if it is a '-' and the character before it was an operator or nothingness (e.g. it negates a number)
                if((in_array($lChar, array_merge(self::$ST1, self::$ST2, self::$ST, self::$SEP['open'])) || $lChar=="") && $chr=="-") {
                    // increase the index because there is no reason that it shouldn't..
                    $pfIndex++;
                    $pf[$pfIndex] = $chr;
                }
                // Otherwise it will function like a normal operator
                else {
                    while(in_array($ops->peek(), array_merge(self::$ST1, self::$ST2, self::$ST)))
                        $pf[++$pfIndex] = $ops->pop();
                    $ops->push($chr);
                    $pfIndex++;
                }
            }
            // make sure we record this character to be referred to by the next one
            $lChar = $chr;
        }
        // if there is anything on the stack after we are done...add it to the back of the RPN array
        while(($tmp = $ops->pop()) !== false)
            $pf[++$pfIndex] = $tmp;

        // re-index the array at 0
        $pf = array_values($pf);

        // set the private variable for later use if needed
        //self::$postFix = $pf;

        // return the RPN array in case developer wants to use it for some insane reason (bug testing ;] )
        // Also... because we pass it right in to the RPN solver.  So I guess there's that too.
        return $pf;
    }

    /**
     * Solve Postfix (RPN)
     *
     * This function will solve a RPN array. Default action is to solve
     * the RPN array stored in the class from Parser::in2post(), can take
     * an array input to solve as well, though default action is preferred.
     *
     * @link http://en.wikipedia.org/wiki/Reverse_Polish_notation Postix Notation
     * @param array $pfArray RPN formatted array. Optional.
     * @throws \Exception on division by 0
     * @return float Result of the operation.
     */
    public static function solvePF($pfArray) {
        $pf = $pfArray;

        // create our temporary function variables
        $temp = array();
        //$tot = 0;
        $hold = 0;

        // Loop through each number/operator
        for($i=0;$i<count($pf); $i++) {
            // If the string isn't an operator, add it to the temp var as a holding place
            if(!in_array($pf[$i], array_merge(self::$ST, self::$ST1, self::$ST2))) {
                $temp[$hold++] = $pf[$i];
            }
            // ...Otherwise perform the operator on the last two numbers
            else {
                switch ($pf[$i]) {
                    case '+':
                        $temp[$hold-2] = $temp[$hold-2] + $temp[$hold-1];
                        break;
                    case '-':
                        $temp[$hold-2] = $temp[$hold-2] - $temp[$hold-1];
                        break;
                    case '*':
                        $temp[$hold-2] = $temp[$hold-2] * $temp[$hold-1];
                        break;
                    case '/':
                        if($temp[$hold-1] == 0) {
                            throw new \Exception("Division by 0 on: '{$temp[$hold-2]} / {$temp[$hold-1]}' in ". self::$inFix, Math::E_DIV_ZERO);
                        }
                        $temp[$hold-2] = $temp[$hold-2] / $temp[$hold-1];
                        break;
                    case '^':
                        $temp[$hold-2] = pow($temp[$hold-2], $temp[$hold-1]);
                        break;
                    case '!':
                        $temp[$hold-1] = self::factorial($temp[$hold-1]);
                        $hold++;
                        break;
                    case '%':
                        if($temp[$hold-1] == 0) {
                            throw new \Exception("Division by 0 on: '{$temp[$hold-2]} % {$temp[$hold-1]}' in ". self::$inFix, Math::E_DIV_ZERO);
                        }
                        $temp[$hold-2] = bcmod($temp[$hold-2], $temp[$hold-1]);
                        break;
                }
                // Decrease the hold var to one above where the last number is
                $hold = $hold-1;
            }
        }

        // return the last number in the array
        return $temp[$hold-1];
    }


    /**
     * Solve
     *
     * This function is called by the user to solve an equation within the parser system
     * No internal functions or added advanced functions should ever call this. Sets
     * the internal $infix variable for use in thrown exceptions. The variable array must
     * be in the format of 'variable' => value. If variable array is scalar (ie 5), all
     * variables will be replaced with it.
     *
     * @param string $equation Equation to Solve
     * @param array|double $values variable values
     * @return float Answer to the equation
     */
    public static function solve($equation, $values = null) {
        if(is_array($equation)) {
            return self::solvePF($equation);
        } else {
            self::$inFix = $equation;
            return self::solveIF($equation, $values);
        }
    }

    /**
     * Solve Infix (Standard) Notation Equation
     *
     * Will take a standard equation with optional variables and solve it.
     * This function is the one for programmers making modules for this
     * package should call as it does not set the internal variable for
     * the equation.  This should not be used by the programmer/user that
     * is using this package to solve equations.
     *
     * @param string $infix Standard Equation to solve
     * @param string|array $vArray Variable replacement
     * @throws \Exception On division by zero or NaN
     * @return float Solved equation
     */
    public static function solveIF($infix, $vArray = null) {
        //Check to make sure a 'valid' expression
        self::checkInfix($infix);

        //$ops = new Stack();
        //$vars = new Stack();
        $hand = null;

        //remove all white-space
        $infix = preg_replace("/\s/", "", $infix);

        $infix = self::checkAdvancedInput($infix,$vArray);

        // Finds all the 'functions' within the equation and calculates them
        //Nested parenthesis are now a go!
        while((preg_match("/(". implode("|", self::$FNC) . ")\(((?:[^()]|\((?2)\))*+)\)/", $infix, $match)) != 0) {
            $func = self::solveIF($match[2], $vArray);
            switch($match[1]) {
                case "cos":
                    $ans = Trig::cos($func);
                    break;
                case "sin":
                    $ans = Trig::sin($func);
                    break;
                case "tan":
                    $ans = Trig::tan($func);
                    break;
                case "sec":
                    $ans = Trig::sec($func);
                    break;
                case "csc":
                    $ans = Trig::csc($func);
                    break;
                case "cot":
                    $ans = Trig::cot($func);
                    break;
                case "abs":
                    $ans = abs($func);
                    break;
                case "ln":
                    $ans = log($func);
                    if(is_nan($ans) || is_infinite($ans)) {
                        throw new \Exception("Result of 'ln({$func}) = {$ans}' is either infinite or a non-number in ". self::$inFix, Math::E_NAN);
                    }
                    break;
                case "sqrt":
                    if($func < 0) {
                        throw new \Exception("Result of 'sqrt({$func}) = i' in ". self::$inFix .".  We can't handle imaginary numbers", Math::E_NAN);
                    }
                    $ans = sqrt($func);
                    break;
                // @codeCoverageIgnoreStart
                default:
                    $ans = 0;
                    break;
                // @codeCoverageIgnoreEnd
            }
            $infix = str_replace($match[0], "({$ans})", $infix);
        }

        //replace scientific notation with normal notation (2e-9 to 2*10^-9)
        $infix = preg_replace('/([\d])([eE])(-?\d)/', '$1*10^$3', $infix);

        $infix = self::replaceVars($infix, $vArray);

        return self::solvePF(self::in2post($infix));
    }

    /**
     * checkAdvancedInput
     *
     * Will take the input from `Parser::solveIF()` and solve all the advanced functions
     * that exist within it, returning it to the function when done for further
     * processing.
     *
     * @param string $input Check for advanced functions, recursively go through them.
     * @param array|int|null $vArray Variables from user-input
     * @return string The input with all advanced functions solved for.
     */
    protected static function checkAdvancedInput($input, $vArray)
    {
        $infix = $input;
        //Advanced/User-defined functions
        while((preg_match("/(". implode("|", array_keys(self::$AFNC)) . ")\(((?:[^()]|\((?2)\))*+)\)/", $infix, $match)) != 0) {
            $method = self::$AFNC[$match[1]];
            if(stripos($match[2], '(') !== false) {
                $match[2] = self::checkAdvancedInput($match[2], $vArray);
            }
            $ans = call_user_func($method, $match[2], $vArray);
            $infix = str_replace($match[0], "({$ans})", $infix);
        }
        return $infix;
    }

    /**
     * @param string $infix
     * @param array $vArray
     * @return string
     * @throws \Exception
     */
    protected static function replaceVars($infix, $vArray)
    {
        //Remove old '$' and '&' signis so the regex works properly.
        $infix = preg_replace('/[$&]/', "", $infix);
        //Find all the variables that were passed and replaces them
        while((preg_match('/([^a-zA-Z]){0,1}([a-zA-Z]+)([^a-zA-Z]){0,1}/', $infix, $match)) != 0) {

            //remove notices by defining if undefined.
            if(!isset($match[3])) {
                $match[3] = "";
            }

            // Ensure that the variable has an operator or something of that sort in front and back - if it doesn't, add an implied '*'
            if((!in_array($match[1], array_merge(self::$ST, self::$ST1, self::$ST2, self::$SEP['open'])) && $match[1] != "") || is_numeric($match[1])) //$this->SEP['close'] removed
                $front = "*";
            else
                $front = "";

            if((!in_array($match[3], array_merge(self::$ST, self::$ST1, self::$ST2, self::$SEP['close'])) && $match[3] != "") || is_numeric($match[3])) //$this->SEP['open'] removed
                $back = "*";
            else
                $back = "";

            //Make sure that the variable does have a replacement
            //First check for pi and e variables that wll automatically be replaced
            if(in_array(strtolower($match[2]), array('pi', 'e'))) {
                $t = (strtolower($match[2])=='pi') ? pi() : exp(1);
                $infix = str_replace($match[0], $match[1] . $front. $t. $back . $match[3], $infix);
            } elseif(!isset($vArray[$match[2]]) && (!is_array($vArray != "") && !is_numeric($vArray) && 0 !== $vArray)) {
                throw new \Exception("Variable replacement does not exist for '". $match[2] ."' in ". self::$inFix .".", Math::E_NO_VAR);
            } elseif(!isset($vArray[$match[2]]) && (!is_array($vArray != "") && is_numeric($vArray))) {
                $infix = str_replace($match[0], $match[1] . $front. $vArray. $back . $match[3], $infix);
            } elseif(isset($vArray[$match[2]])) {
                $infix = str_replace($match[0], $match[1] . $front. $vArray[$match[2]]. $back . $match[3], $infix);
            }
        }

        return $infix;
    }

    /**
     * Solve factorial (!)
     *
     * Will take an integer and solve for it's factorial. Eg.
     * `5!` will become `1*2*3*4*5` = `120`
     * DONE:
     *    Solve for non-integer factorials  2015/07/02
     *
     * @param float $num Non-negative real number to get factorial of
     * @throws \Exception if number is at or less than 0
     * @return float Solved factorial
     */
    protected static function factorial($num) {
        if($num < 0) {
            throw new \Exception("Factorial Error: Factorials don't exist for numbers < 0 in ". self::$inFix, Math::E_NAN);
        }
        //A non-integer!  Gamma that sucker up!
        if(intval($num) != $num) {
            return self::gamma($num + 1);
        }

        $tot = 1;
        for($i=1;$i<=$num;$i++) {
            $tot *= $i;
        }

        return $tot;
    }

    /**
     * Gamma Function
     *
     * Because we can. This function exists as a catch-all for different
     * numerical approx. of gamma if I decide to add any past Lanczos'.
     *
     * @param $z Number to compute gamma from
     * @return float The gamma (hopefully, I'll test it after writing the code)
     */
    public static function gamma($z)
    {
        return self::laGamma($z);
    }

    /**
     * Lanczos Approximation
     *
     * The Lanczos Approximation method of finding gamma values
     *
     * @link http://www.rskey.org/CMS/index.php/the-library/11
     * @link http://algolist.manual.ru/maths/count_fast/gamma_function.php
     * @link https://en.wikipedia.org/wiki/Lanczos_approximation
     * @param $z Number to obtain the gamma of
     * @return float Answer
     */
    protected static function laGamma($z)
    {
        // Set up coefficients
        $p = array(
            0 => 1.000000000190015,
            1 => 76.18009172947146,
            2 => -86.50532032941677,
            3 => 24.01409824083091,
            4 => -1.231739572450155,
            5 => 1.208650973866179E-3,
            6 => -5.395239384953E-6
        );

        // Formula:
        // ((sqrt(2pi)/z)(p[0]+sum(p[n]/(z+n), 1, 6)))(z+5.5)^(z+0.5)*e^(-(z+5.5))

        // Break it down now...
        $g1 = sqrt(2*pi())/$z;

        // Next comes our summation
        $g2 =0;
        for($n=1;$n<=6;$n++) {
            $g2 += $p[$n]/($z+$n);
        }

        // Don't forget to add p[0] to it...
        $g2 += $p[0];
        $g3 = pow($z+5.5, $z + .5);
        $g4 = exp(-($z+5.5));

        //now just multiply them all together
        $gamma = $g1 * $g2 * $g3 * $g4;

        return $gamma;
    }
}