diff options
| -rw-r--r-- | NXP/Classes/Func.php | 41 | ||||
| -rw-r--r-- | NXP/Classes/Operand.php | 85 | ||||
| -rw-r--r-- | NXP/Classes/Token.php | 53 | ||||
| -rw-r--r-- | NXP/Classes/TokenParser.php | 159 | ||||
| -rw-r--r-- | NXP/MathExecutor.php | 298 | ||||
| -rw-r--r-- | NXP/Tests/MathTest.php | 4 | ||||
| -rw-r--r-- | test.php | 3 |
7 files changed, 513 insertions, 130 deletions
diff --git a/NXP/Classes/Func.php b/NXP/Classes/Func.php new file mode 100644 index 0000000..b3e5b93 --- /dev/null +++ b/NXP/Classes/Func.php @@ -0,0 +1,41 @@ +<?php +/** + * Author: Alexander "NeonXP" Kiryukhin + * Date: 17.03.13 + * Time: 4:30 + */ + +namespace NXP\Classes; + + +class Func { + /** + * @var string + */ + private $name; + + /** + * @var callable + */ + private $callback; + + /** + * @param $name + * @param $callback + */ + function __construct($name, $callback) + { + $this->name = $name; + $this->callback = $callback; + } + + public function getName() + { + return $this->name; + } + + public function getCallback() + { + return $this->callback; + } +}
\ No newline at end of file diff --git a/NXP/Classes/Operand.php b/NXP/Classes/Operand.php new file mode 100644 index 0000000..3329679 --- /dev/null +++ b/NXP/Classes/Operand.php @@ -0,0 +1,85 @@ +<?php +/** + * Author: Alexander "NeonXP" Kiryukhin + * Date: 17.03.13 + * Time: 4:27 + */ + +namespace NXP\Classes; + + +class Operand { + const LEFT_ASSOCIATED = 'LEFT_ASSOCIATED'; + const RIGHT_ASSOCIATED = 'RIGHT_ASSOCIATED'; + const ASSOCIATED = 'ASSOCIATED'; + + const UNARY = 'UNARY'; + const BINARY = 'BINARY'; + + /** + * @var string + */ + private $symbol; + + /** + * @var int + */ + private $priority; + + /** + * @var string + */ + private $association; + + /** + * @var string + */ + private $type; + + /** + * @var callable + */ + private $callback; + + /** + * @param $symbol + * @param $priority + * @param $association + * @param $type + * @param $callback + */ + function __construct($symbol, $priority, $association, $type, $callback) + { + $this->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; + } + +}
\ No newline at end of file diff --git a/NXP/Classes/Token.php b/NXP/Classes/Token.php new file mode 100644 index 0000000..28bc736 --- /dev/null +++ b/NXP/Classes/Token.php @@ -0,0 +1,53 @@ +<?php +/** + * Author: Alexander "NeonXP" Kiryukhin + * Date: 17.03.13 + * Time: 3:23 + */ + +namespace NXP\Classes; + + +class Token { + + const NOTHING = 'NOTHING'; + const STRING = 'STRING'; + const NUMBER = 'NUMBER'; + const OPERATOR = 'OPERATOR'; + const LEFT_BRACKET = 'LEFT_BRACKET'; + const RIGHT_BRACKET = 'RIGHT_BRACKET'; + const FUNC = 'FUNC'; + + /** + * @var string + */ + protected $value; + + /** + * @var string + */ + protected $type; + + function __construct($type, $value) + { + $this->type = $type; + $this->value = $value; + } + + /** + * @return string + */ + public function getType() + { + return $this->type; + } + + /** + * @return string + */ + public function getValue() + { + return $this->value; + } + +}
\ No newline at end of file diff --git a/NXP/Classes/TokenParser.php b/NXP/Classes/TokenParser.php new file mode 100644 index 0000000..7b9255f --- /dev/null +++ b/NXP/Classes/TokenParser.php @@ -0,0 +1,159 @@ +<?php +/** + * Author: Alexander "NeonXP" Kiryukhin + * Date: 17.03.13 + * Time: 2:45 + */ + +namespace NXP\Classes; + + +class TokenParser { + const DIGIT = 'DIGIT'; + const CHAR = 'CHAR'; + const SPECIAL_CHAR = 'SPECIAL_CHAR'; + const LEFT_BRACKET = 'LEFT_BRACKET'; + const RIGHT_BRACKET = 'RIGHT_BRACKET'; + const SPACE = 'SPACE'; + + private $terms = [ + self::DIGIT => '[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 = [ + Token::NOTHING => [ + 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 => [ + 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 => [ + 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 => [ + 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 => [ + 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 => [ + 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 => [ + 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; + + function __construct() + { + $this->queue = new \SplQueue(); + } + + /** + * Tokenize math expression + * @param $expression + * @return \SplQueue + * @throws \Exception + */ + public function tokenize($expression) + { + $oldState = null; + for ($i=0; $i<strlen($expression); $i++) { + $char = substr($expression, $i, 1); + $class = $this->getSymbolType($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 = ''; + } + } +}
\ No newline at end of file diff --git a/NXP/MathExecutor.php b/NXP/MathExecutor.php index d7eaf82..cb1c7b5 100644 --- a/NXP/MathExecutor.php +++ b/NXP/MathExecutor.php @@ -6,48 +6,69 @@ */ namespace NXP; +use NXP\Classes\Func; +use NXP\Classes\Operand; +use NXP\Classes\Token; +use NXP\Classes\TokenParser; + /** * Class MathExecutor * @package NXP */ class MathExecutor { - const LEFT_ASSOCIATED = 'LEFT_ASSOCIATED'; - const RIGHT_ASSOCIATED = 'RIGHT_ASSOCIATED'; - const NOT_ASSOCIATED = 'NOT_ASSOCIATED'; - const UNARY = 'UNARY'; - const BINARY = 'BINARY'; private $operators = [ ]; + private $functions = [ ]; + + private $variables = [ ]; + + /** + * @var \SplStack + */ + private $stack; + + /** + * @var \SplQueue + */ + private $queue; + /** * Base math operators */ public function __construct() { - $this->addOperator('+', 1, function ($op1, $op2) { return $op1 + $op2; }); - $this->addOperator('-', 1, function ($op1, $op2) { return $op1 - $op2; }); - $this->addOperator('*', 2, function ($op1, $op2) { return $op1 * $op2; }); - $this->addOperator('/', 2, function ($op1, $op2) { return $op1 / $op2; }); - $this->addOperator('^', 3, function ($op1, $op2) { return pow($op1, $op2); }); + $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 custom operator - * @param string $name - * @param int $priority - * @param callable $callback - * @param string $association - * @param string $type - */ - public function addOperator($name, $priority, callable $callback, $association = self::LEFT_ASSOCIATED, $type = self::BINARY) + public function addOperator(Operand $operator) + { + $this->operators[$operator->getSymbol()] = $operator; + } + + public function addFunction(Func $function) + { + $this->functions[$function->getName()] = $function->getCallback(); + } + + public function setVar($variable, $value) { - $this->operators[$name] = [ - 'priority' => $priority, - 'association' => $association, - 'type' => $type, - 'callback' => $callback - ]; + if (!is_numeric($value)) { + throw new \Exception("Variable value must be a number"); + } + $this->variables[$variable] = $value; } /** @@ -66,132 +87,151 @@ class MathExecutor { /** * Convert expression from normal expression form to RPN * @param $expression - * @return array + * @return \SplQueue * @throws \Exception */ protected function convertToReversePolishNotation($expression) { - $stack = new \SplStack(); - $queue = []; - $currentNumber = ''; - - for ($i = 0; $i < strlen($expression); $i++) - { - $char = substr($expression, $i, 1); - if (is_numeric($char) || (($char == '.') && (strpos($currentNumber, '.')===false))) { - $currentNumber .= $char; - } elseif ($currentNumber!='') { - $queue = $this->insertNumberToQueue($currentNumber, $queue); - $currentNumber = ''; - } - if (array_key_exists($char, $this->operators)) { - while ($this->o1HasLowerPriority($char, $stack)) { - $queue[] = $stack->pop(); - } - $stack->push($char); - } - if ($char == '(') { - $stack->push($char); - } - if ($char == ')') { - if ($currentNumber!='') { - $queue = $this->insertNumberToQueue($currentNumber, $queue); - $currentNumber = ''; - } - while (($stackChar = $stack->pop()) != '(') { - $queue[] = $stackChar; - } - /** - * @TODO parse functions here - */ - } - } + $this->stack = new \SplStack(); + $this->queue = new \SplQueue(); + + $tokenParser = new TokenParser(); + $input = $tokenParser->tokenize($expression); - if ($currentNumber!='') { - $queue = $this->insertNumberToQueue($currentNumber, $queue); + foreach ($input as $token) { + $this->categorizeToken($token); } - while (!$stack->isEmpty()) { - $queue[] = ($char = $stack->pop()); - if (!array_key_exists($char, $this->operators)) { - throw new \Exception('Opening bracket has no closing bracket'); + 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 $queue; + return $this->queue; } - /** - * Calculate value of expression - * @param array $expression - * @return int|float - * @throws \Exception - */ - protected function calculateReversePolishNotation(array $expression) + private function categorizeToken(Token $token) { - $stack = new \SplStack(); - foreach ($expression as $element) { - if (is_numeric($element)) { - $stack->push($element); - } elseif (array_key_exists($element, $this->operators)) { - $operator = $this->operators[$element]; - switch ($operator['type']) { - case self::BINARY: - $op2 = $stack->pop(); - $op1 = $stack->pop(); - $operatorResult = $operator['callback']($op1, $op2); - break; - case self::UNARY: - $op = $stack->pop(); - $operatorResult = $operator['callback']($op); - break; - default: - throw new \Exception('Incorrect type'); + 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); } - $stack->push($operatorResult); - } - } - $result = $stack->pop(); - if (!$stack->isEmpty()) { - throw new \Exception('Incorrect expression'); - } + break; - return $result; - } + case Token::LEFT_BRACKET: + $this->stack->push($token); + break; - /** - * @param $char - * @param $stack - * @return bool - */ - private function o1HasLowerPriority($char, \SplStack $stack) { - if (($stack->isEmpty()) || ($stack->top() == '(')) { - return false; - } - $stackTopAssociation = $this->operators[$stack->top()]['association']; - $stackTopPriority = $this->operators[$stack->top()]['priority']; - $charPriority = $this->operators[$char]['priority']; + 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)) { + $string = $this->stack->pop()->getValue(); + if (!array_key_exists($string, $this->functions)) { + throw new \Exception('Unknown function'); + } + $this->queue->push(new Token(Token::FUNC, $string)); + } + break; + case Token::OPERATOR: + if (!array_key_exists($token->getValue(), $this->operators)) { + throw new \Exception("Unknown operator '{$token->getValue()}'"); + } + + $this->proceedOperator($token); + $this->stack->push($token); + break; - return - (($stackTopAssociation != self::LEFT_ASSOCIATED) && ($stackTopPriority > $charPriority)) || - (($stackTopAssociation == self::LEFT_ASSOCIATED) && ($stackTopPriority >= $charPriority)); + default: + throw new \Exception('Unknown token'); + } } - /** - * @param string $currentNumber - * @param array $queue - * @return array - */ - private function insertNumberToQueue($currentNumber, $queue) + private function proceedOperator($token) { - if ($currentNumber[0]=='.') { - $currentNumber = '0'.$currentNumber; + if (!array_key_exists($token->getValue(), $this->operators)) { + throw new \Exception('Unknown operator'); + } + /** @var Operand $operator */ + $operator = $this->operators[$token->getValue()]; + while (!$this->stack->isEmpty()) { + $top = $this->stack->top(); + if ($top->getType() == Token::OPERATOR) { + $priority = $this->operators[$top->getValue()]->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; + } } - $currentNumber = trim($currentNumber, '.'); - $queue[] = $currentNumber; - - return $queue; } + protected function calculateReversePolishNotation(\SplQueue $expression) + { + $this->stack = new \SplStack(); + /** @val 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, ($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, ($callback($arg)))); + break; + default: + throw new \Exception('Unknown token'); + } + } + $result = $this->stack->pop()->getValue(); + if (!$this->stack->isEmpty()) { + throw new \Exception('Incorrect expression'); + } + + return $result; + } }
\ No newline at end of file diff --git a/NXP/Tests/MathTest.php b/NXP/Tests/MathTest.php index 6ab67ee..6bfcf55 100644 --- a/NXP/Tests/MathTest.php +++ b/NXP/Tests/MathTest.php @@ -12,6 +12,10 @@ class MathTest extends \PHPUnit_Framework_TestCase { public function setup() { require '../MathExecutor.php'; + require '../Classes/Func.php'; + require '../Classes/Operand.php'; + require '../Classes/Token.php'; + require '../Classes/TokenParser.php'; } public function testCalculating() { @@ -8,4 +8,5 @@ require "vendor/autoload.php"; $e = new \NXP\MathExecutor(); -print $e->execute("1 + 2 * (2 - (4+10))^2");
\ No newline at end of file +$r = $e->execute("1 + 2 * (2 - (4+10))^2"); +var_dump($r); |