From eb9c3651614dd5e5aef067880092e9f622c264df Mon Sep 17 00:00:00 2001 From: zhukv Date: Sat, 3 Aug 2013 13:47:47 +0300 Subject: Fix to PSR standart, fix tokenizer, fix function executor. --- src/NXP/Classes/Func.php | 45 +++ src/NXP/Classes/Operand.php | 89 +++++ src/NXP/Classes/Token.php | 56 +++ src/NXP/Classes/TokenParser.php | 165 +++++++++ src/NXP/Exception/IncorrectExpressionException.php | 19 + src/NXP/Exception/MathExecutorException.php | 19 + src/NXP/Exception/UnknownFunctionException.php | 19 + src/NXP/Exception/UnknownOperatorException.php | 19 + src/NXP/Exception/UnknownTokenException.php | 19 + src/NXP/MathExecutor.php | 393 +++++++++++++++++++++ 10 files changed, 843 insertions(+) create mode 100644 src/NXP/Classes/Func.php create mode 100644 src/NXP/Classes/Operand.php create mode 100644 src/NXP/Classes/Token.php create mode 100644 src/NXP/Classes/TokenParser.php create mode 100644 src/NXP/Exception/IncorrectExpressionException.php create mode 100644 src/NXP/Exception/MathExecutorException.php create mode 100644 src/NXP/Exception/UnknownFunctionException.php create mode 100644 src/NXP/Exception/UnknownOperatorException.php create mode 100644 src/NXP/Exception/UnknownTokenException.php create mode 100644 src/NXP/MathExecutor.php (limited to 'src/NXP') diff --git a/src/NXP/Classes/Func.php b/src/NXP/Classes/Func.php new file mode 100644 index 0000000..e8c0fa2 --- /dev/null +++ b/src/NXP/Classes/Func.php @@ -0,0 +1,45 @@ +name = $name; + $this->callback = $callback; + } + + public function getName() + { + return $this->name; + } + + public function getCallback() + { + return $this->callback; + } +} diff --git a/src/NXP/Classes/Operand.php b/src/NXP/Classes/Operand.php new file mode 100644 index 0000000..fae0c69 --- /dev/null +++ b/src/NXP/Classes/Operand.php @@ -0,0 +1,89 @@ +association = $association; + $this->symbol = $symbol; + $this->type = $type; + $this->priority = $priority; + $this->callback = $callback; + } + + public function getAssociation() + { + return $this->association; + } + + public function getSymbol() + { + return $this->symbol; + } + + public function getType() + { + return $this->type; + } + + public function getCallback() + { + return $this->callback; + } + + public function getPriority() + { + return $this->priority; + } + +} diff --git a/src/NXP/Classes/Token.php b/src/NXP/Classes/Token.php new file mode 100644 index 0000000..bbcd5bc --- /dev/null +++ b/src/NXP/Classes/Token.php @@ -0,0 +1,56 @@ +type = $type; + $this->value = $value; + } + + /** + * @return string + */ + public function getType() + { + return $this->type; + } + + /** + * @return string + */ + public function getValue() + { + return $this->value; + } + +} diff --git a/src/NXP/Classes/TokenParser.php b/src/NXP/Classes/TokenParser.php new file mode 100644 index 0000000..f498184 --- /dev/null +++ b/src/NXP/Classes/TokenParser.php @@ -0,0 +1,165 @@ + '[0-9\.]', + self::CHAR => '[a-z_]', + self::SPECIAL_CHAR => '[\!\@\#\$\%\^\&\*\/\|\-\+\=\~]', + self::LEFT_BRACKET => '\(', + self::RIGHT_BRACKET => '\)', + self::SPACE => '\s' + ); + + const ERROR_STATE = 'ERROR_STATE'; + + private $transitions = array( + Token::NOTHING => array( + self::DIGIT => Token::NUMBER, + self::CHAR => Token::STRING, + self::SPECIAL_CHAR => Token::OPERATOR, + self::LEFT_BRACKET => Token::LEFT_BRACKET, + self::RIGHT_BRACKET => Token::RIGHT_BRACKET, + self::SPACE => Token::NOTHING + ), + Token::STRING => array( + self::DIGIT => Token::STRING, + self::CHAR => Token::STRING, + self::SPECIAL_CHAR => Token::OPERATOR, + self::LEFT_BRACKET => Token::LEFT_BRACKET, + self::RIGHT_BRACKET => Token::RIGHT_BRACKET, + self::SPACE => Token::NOTHING + ), + Token::NUMBER => array( + self::DIGIT => Token::NUMBER, + self::CHAR => self::ERROR_STATE, + self::SPECIAL_CHAR => Token::OPERATOR, + self::LEFT_BRACKET => Token::LEFT_BRACKET, + self::RIGHT_BRACKET => Token::RIGHT_BRACKET, + self::SPACE => Token::NOTHING + ), + Token::OPERATOR => array( + self::DIGIT => Token::NUMBER, + self::CHAR => Token::STRING, + self::SPECIAL_CHAR => Token::OPERATOR, + self::LEFT_BRACKET => Token::LEFT_BRACKET, + self::RIGHT_BRACKET => Token::RIGHT_BRACKET, + self::SPACE => Token::NOTHING + ), + self::ERROR_STATE => array( + self::DIGIT => self::ERROR_STATE, + self::CHAR => self::ERROR_STATE, + self::SPECIAL_CHAR => self::ERROR_STATE, + self::LEFT_BRACKET => self::ERROR_STATE, + self::RIGHT_BRACKET => self::ERROR_STATE, + self::SPACE => self::ERROR_STATE + ), + Token::LEFT_BRACKET => array( + self::DIGIT => Token::NUMBER, + self::CHAR => Token::STRING, + self::SPECIAL_CHAR => Token::OPERATOR, + self::LEFT_BRACKET => Token::LEFT_BRACKET, + self::RIGHT_BRACKET => Token::RIGHT_BRACKET, + self::SPACE => Token::NOTHING + ), + Token::RIGHT_BRACKET => array( + self::DIGIT => Token::NUMBER, + self::CHAR => Token::STRING, + self::SPECIAL_CHAR => Token::OPERATOR, + self::LEFT_BRACKET => Token::LEFT_BRACKET, + self::RIGHT_BRACKET => Token::RIGHT_BRACKET, + self::SPACE => Token::NOTHING + ), + ); + + private $accumulator = ''; + + private $state = Token::NOTHING; + + private $queue = null; + + public function __construct() + { + $this->queue = new \SplQueue(); + } + + /** + * Tokenize math expression + * @param $expression + * @return \SplQueue + * @throws \Exception + */ + public function tokenize($expression) + { + $oldState = null; + for ($i=0; $igetSymbolType($char); + $oldState = $this->state; + $this->state = $this->transitions[$this->state][$class]; + if ($this->state == self::ERROR_STATE) { + throw new \Exception("Parse expression error at $i column (symbol '$char')"); + } + $this->addToQueue($oldState); + $this->accumulator .= $char; + } + if (!empty($this->accumulator)) { + $token = new Token($this->state, $this->accumulator); + $this->queue->push($token); + } + + return $this->queue; + } + + /** + * @param $symbol + * @return string + * @throws \Exception + */ + private function getSymbolType($symbol) + { + foreach ($this->terms as $class => $regex) { + if (preg_match("/$regex/i", $symbol)) { + return $class; + } + } + + throw new \Exception("Unknown char '$symbol'"); + } + + /** + * @param $oldState + */ + private function addToQueue($oldState) + { + if ($oldState == Token::NOTHING) { + $this->accumulator = ''; + + return; + } + + if (($this->state != $oldState) || ($oldState == Token::LEFT_BRACKET) || ($oldState == Token::RIGHT_BRACKET)) { + $token = new Token($oldState, $this->accumulator); + $this->queue->push($token); + $this->accumulator = ''; + } + } +} diff --git a/src/NXP/Exception/IncorrectExpressionException.php b/src/NXP/Exception/IncorrectExpressionException.php new file mode 100644 index 0000000..ad5bc42 --- /dev/null +++ b/src/NXP/Exception/IncorrectExpressionException.php @@ -0,0 +1,19 @@ + + */ +class IncorrectExpressionException extends \Exception +{ +} diff --git a/src/NXP/Exception/MathExecutorException.php b/src/NXP/Exception/MathExecutorException.php new file mode 100644 index 0000000..0e3ea84 --- /dev/null +++ b/src/NXP/Exception/MathExecutorException.php @@ -0,0 +1,19 @@ + + */ +abstract class MathExecutorException extends \Exception +{ +} diff --git a/src/NXP/Exception/UnknownFunctionException.php b/src/NXP/Exception/UnknownFunctionException.php new file mode 100644 index 0000000..5bb3658 --- /dev/null +++ b/src/NXP/Exception/UnknownFunctionException.php @@ -0,0 +1,19 @@ + + */ +class UnknownFunctionException extends \Exception +{ +} diff --git a/src/NXP/Exception/UnknownOperatorException.php b/src/NXP/Exception/UnknownOperatorException.php new file mode 100644 index 0000000..b6617c3 --- /dev/null +++ b/src/NXP/Exception/UnknownOperatorException.php @@ -0,0 +1,19 @@ + + */ +class UnknownOperatorException extends \Exception +{ +} diff --git a/src/NXP/Exception/UnknownTokenException.php b/src/NXP/Exception/UnknownTokenException.php new file mode 100644 index 0000000..b8a593f --- /dev/null +++ b/src/NXP/Exception/UnknownTokenException.php @@ -0,0 +1,19 @@ + + */ +class UnknownTokenException extends \Exception +{ +} diff --git a/src/NXP/MathExecutor.php b/src/NXP/MathExecutor.php new file mode 100644 index 0000000..482b4b7 --- /dev/null +++ b/src/NXP/MathExecutor.php @@ -0,0 +1,393 @@ +addDefaults(); + } + + public function __clone() + { + $this->variables = array(); + $this->operators = array(); + $this->functions = array(); + + $this->addDefaults(); + } + + /** + * Set default operands and functions + */ + protected function addDefaults() + { + $this->addOperator(new Operand('+', 1, Operand::LEFT_ASSOCIATED, Operand::BINARY, function ($op1, $op2) { return $op1+$op2; })); + $this->addOperator(new Operand('-', 1, Operand::LEFT_ASSOCIATED, Operand::BINARY, function ($op1, $op2) { return $op1-$op2; })); + $this->addOperator(new Operand('*', 2, Operand::LEFT_ASSOCIATED, Operand::BINARY, function ($op1, $op2) { return $op1*$op2; })); + $this->addOperator(new Operand('/', 2, Operand::LEFT_ASSOCIATED, Operand::BINARY, function ($op1, $op2) { return $op1/$op2; })); + $this->addOperator(new Operand('^', 3, Operand::LEFT_ASSOCIATED, Operand::BINARY, function ($op1, $op2) { return pow($op1,$op2); })); + + $this->addFunction(new Func('sin', function ($arg) { return sin($arg); })); + $this->addFunction(new Func('cos', function ($arg) { return cos($arg); })); + $this->addFunction(new Func('tn', function ($arg) { return tan($arg); })); + $this->addFunction(new Func('asin', function ($arg) { return asin($arg); })); + $this->addFunction(new Func('acos', function ($arg) { return acos($arg); })); + $this->addFunction(new Func('atn', function ($arg) { return atan($arg); })); + } + + /** + * Add operator to executor + * + * @param Operand $operator + * @return MathExecutor + */ + public function addOperator(Operand $operator) + { + $this->operators[$operator->getSymbol()] = $operator; + + return $this; + } + + /** + * Add function to executor + * + * @param string $name + * @param callable $function + * @return MathExecutor + */ + public function addFunction($name, callable $function = null) + { + if ($name instanceof Func) { + $this->functions[$name->getName()] = $name->getCallback(); + } else { + $this->functions[$name] = $function; + } + + return $this; + } + + /** + * Add variable to executor + * + * @param string $variable + * @param integer|float $value + * @throws \Exception + * @return MathExecutor + */ + public function setVar($variable, $value) + { + if (!is_numeric($value)) { + throw new \Exception("Variable value must be a number"); + } + + $this->variables[$variable] = $value; + + return $this; + } + + /** + * Add variables to executor + * + * @param array $variables + * @param bool $clear Clear previous variables + * @return MathExecutor + */ + public function setVars(array $variables, $clear = true) + { + if ($clear) { + $this->removeVars(); + } + + foreach ($variables as $name => $value) { + $this->setVar($name, $value); + } + + return $this; + } + + /** + * Remove variable from executor + * + * @param string $variable + * @return MathExecutor + */ + public function removeVar($variable) + { + unset ($this->variables[$variable]); + + return $this; + } + + /** + * Remove all variables + */ + public function removeVars() + { + $this->variables = array(); + + return $this; + } + + /** + * Execute expression + * + * @param $expression + * @return int|float + */ + public function execute($expression) + { + $reversePolishNotation = $this->convertToReversePolishNotation($expression); + $result = $this->calculateReversePolishNotation($reversePolishNotation); + + return $result; + } + + /** + * Convert expression from normal expression form to RPN + * + * @param $expression + * @return \SplQueue + * @throws \Exception + */ + private function convertToReversePolishNotation($expression) + { + $this->stack = new \SplStack(); + $this->queue = new \SplQueue(); + + $tokenParser = new TokenParser(); + $input = $tokenParser->tokenize($expression); + + foreach ($input as $token) { + $this->categorizeToken($token); + } + + while (!$this->stack->isEmpty()) { + $token = $this->stack->pop(); + + if ($token->getType() != Token::OPERATOR) { + throw new \Exception('Opening bracket without closing bracket'); + } + + $this->queue->push($token); + } + + return $this->queue; + } + + /** + * @param Token $token + * @throws \Exception + */ + private function categorizeToken(Token $token) + { + switch ($token->getType()) { + case Token::NUMBER : + $this->queue->push($token); + break; + + case Token::STRING: + if (array_key_exists($token->getValue(), $this->variables)) { + $this->queue->push(new Token(Token::NUMBER, $this->variables[$token->getValue()])); + } else { + $this->stack->push($token); + } + break; + + case Token::LEFT_BRACKET: + $this->stack->push($token); + break; + + case Token::RIGHT_BRACKET: + $previousToken = $this->stack->pop(); + while (!$this->stack->isEmpty() && ($previousToken->getType() != Token::LEFT_BRACKET)) { + $this->queue->push($previousToken); + $previousToken = $this->stack->pop(); + } + if ((!$this->stack->isEmpty()) && ($this->stack->top()->getType() == Token::STRING)) { + $funcName = $this->stack->pop()->getValue(); + if (!array_key_exists($funcName, $this->functions)) { + throw new UnknownFunctionException(sprintf( + 'Unknown function: "%s".', + $funcName + )); + } + $this->queue->push(new Token(Token::FUNC, $funcName)); + } + break; + + case Token::OPERATOR: + if (!array_key_exists($token->getValue(), $this->operators)) { + throw new UnknownOperatorException(sprintf( + 'Unknown operator: "%s".', + $token->getValue() + )); + } + + $this->proceedOperator($token); + $this->stack->push($token); + break; + + default: + throw new UnknownTokenException(sprintf( + 'Unknown token: "%s".', + $token->getValue() + )); + } + } + + /** + * @param $token + * @throws \Exception + */ + private function proceedOperator(Token $token) + { + if (!array_key_exists($token->getValue(), $this->operators)) { + throw new UnknownOperatorException(sprintf( + 'Unknown operator: "%s".', + $token->getValue() + )); + } + + /** @var Operand $operator */ + $operator = $this->operators[$token->getValue()]; + + while (!$this->stack->isEmpty()) { + $top = $this->stack->top(); + + if ($top->getType() == Token::OPERATOR) { + /** @var Operand $operator */ + $operator = $this->operators[$top->getValue()]; + $priority = $operator->getPriority(); + if ( $operator->getAssociation() == Operand::RIGHT_ASSOCIATED) { + if (($priority > $operator->getPriority())) { + $this->queue->push($this->stack->pop()); + } else { + return; + } + } else { + if (($priority >= $operator->getPriority())) { + $this->queue->push($this->stack->pop()); + } else { + return; + } + } + } elseif ($top->getType() == Token::STRING) { + $this->queue->push($this->stack->pop()); + } else { + return; + } + } + } + + /** + * @param \SplQueue $expression + * @return mixed + * @throws \Exception + */ + private function calculateReversePolishNotation(\SplQueue $expression) + { + $this->stack = new \SplStack(); + /** @var Token $token */ + foreach ($expression as $token) { + switch ($token->getType()) { + case Token::NUMBER : + $this->stack->push($token); + break; + + case Token::OPERATOR: + /** @var Operand $operator */ + $operator = $this->operators[$token->getValue()]; + if ($operator->getType() == Operand::BINARY) { + $arg2 = $this->stack->pop()->getValue(); + $arg1 = $this->stack->pop()->getValue(); + } else { + $arg2 = null; + $arg1 = $this->stack->pop()->getValue(); + } + $callback = $operator->getCallback(); + + $this->stack->push(new Token(Token::NUMBER, (call_user_func($callback, $arg1, $arg2)))); + break; + + case Token::FUNC: + /** @var Func $function */ + $callback = $this->functions[$token->getValue()]; + $arg = $this->stack->pop()->getValue(); + $this->stack->push(new Token(Token::NUMBER, (call_user_func($callback, $arg)))); + break; + + default: + throw new UnknownTokenException(sprintf( + 'Unknown token: "%s".', + $token->getValue() + )); + } + } + + $result = $this->stack->pop()->getValue(); + + if (!$this->stack->isEmpty()) { + throw new IncorrectExpressionException('Incorrect expression.'); + } + + return $result; + } +} -- cgit v1.2.3