fork download
copy 
  1. <?php
  2.  
  3. set_error_handler(function ($errno, $errstr, $errfile, $errline ) {
  4.     throw new \ErrorException($errstr, $errno, 0, $errfile, $errline);
  5. });
  6.  
  7. class Tokenizer
  8. {
  9. 	public function tokenizeLexems(array $lexems)
  10. 	{
  11. 		$tokens = [];
  12.  
  13. 		foreach ($lexems as $lexem) {
  14. 			if (is_numeric($lexem)) {
  15. 				$fraction = SimpleFraction::createFromDecimal($lexem);
  16. 				$tokens[] = $fraction;
  17. 			} elseif (in_array($lexem, ['+', '-', '/', '*', '^', '(', ')', '#', '$'])) {
  18. 				$operator = OperatorFactory::getOperatorBySign($lexem);
  19. 				$tokens[] = $operator;
  20. 			} else {
  21. 				throw new \Exception(sprintf('Invalid lexem %s given', $lexem));
  22. 			}
  23. 		}
  24.  
  25. 		return $tokens;
  26. 	}
  27. }
  28.  
  29. class Lexer
  30. {
  31. 	public function getLexemsFromInfix($infix)
  32. 	{
  33.         $this->checkInfix($infix);
  34.  
  35.         preg_match_all('/(\d+(\.\d+)?|([\+\-\/\*\^\(\)\$#]))|(\S)/', $infix, $match);
  36.         if ($invalidChars = array_filter($match[4])) {
  37.             throw new InvalidInfixException(sprintf('Ошибка: в выражении недопустимые символы %s', implode(', ', $invalidChars)));
  38.         }
  39. 		$lexems = $match[0];
  40.  
  41. 		return $lexems;
  42. 	}
  43.  
  44. 	private function checkInfix($infix)
  45. 	{
  46.         $this->checkParenthesesIsMatched($infix);
  47.         $this->checkDigitsAndBinaryOperators($infix);
  48.         $this->checkUnaryOperators($infix);
  49. 	}
  50.  
  51.     private function checkParenthesesIsMatched($string)
  52.     {
  53.         $chars = str_split($string);
  54.  
  55.         $depth = 0;
  56.         foreach ($chars as $char) {
  57.             $depth += $char == '(';
  58.             $depth -= $char == ')';
  59.  
  60.             if ($depth < 0) break;
  61.         }
  62.  
  63.         if ($depth !== 0) throw new InvalidInfixException('Ошибка: скобки расставлены неправильно');
  64.     }
  65.  
  66.     private function checkDigitsAndBinaryOperators($infix)
  67.     {
  68.         preg_match_all('/(\d+(\.\d+)?)|([\+\-\*\/\^])/', $infix, $match);
  69.  
  70.         $numbersAmount = count(array_filter($match[1], 'strlen')); // Без 'strlen' ф-я array_filter исключит цифру 0
  71.         $binaryOperatorsAmount = count(array_filter($match[3], 'strlen'));
  72.  
  73.         if ($numbersAmount < 1) {
  74.             throw new InvalidInfixException('Ошибка: в выражении должно быть по меньшей мере одно число');
  75.         }
  76.         if ($numbersAmount != ++$binaryOperatorsAmount) {
  77.             throw new InvalidInfixException('Ошибка: количество бинарных операторов должно быть на один меньше, чем количество чисел');
  78.         }
  79.     }
  80.  
  81.     private function checkUnaryOperators($infix)
  82.     {
  83.         if (preg_match('/(?<!^|\()[#\$]/', $infix)) {
  84.             throw new InvalidInfixException('Ошибка: унарный оператор нужно заключать в скобки, если он не в начале выражения');
  85.         }
  86.     }
  87. }
  88.  
  89. class ShuntingYard
  90. {
  91. 	private $operatorStack;
  92.  
  93. 	public function __construct()
  94. 	{
  95. 		$this->operatorStack = new \SplStack;
  96. 	}
  97.  
  98. 	public function createRpnQueueFromTokens(array $tokens)
  99. 	{
  100.         $outputQueue = new \SplQueue();
  101. 		foreach ($tokens as $token) {
  102. 			if ($token instanceof SimpleFraction) {
  103. 				$outputQueue->enqueue($token);
  104. 			} elseif ($token instanceof AbstractOperator) {
  105. 				if ($this->operatorStack->isEmpty()) {
  106. 					$this->operatorStack->push($token);
  107. 					continue;
  108. 				}
  109.  
  110. 				$operatorTop = $this->operatorStack->top();
  111. 				if (($operatorTop instanceof AbstractOperator)
  112. 					&& (($token->isLeftassociative() && $token->getPrecedence() <= $operatorTop->getPrecedence())
  113.    					|| ($token->isRightAssociative() && $token->getPrecedence() < $operatorTop->getPrecedence()))
  114. 					) {
  115. 						$outputQueue->enqueue($this->operatorStack->pop());
  116. 				}
  117.  
  118. 				$this->operatorStack->push($token);
  119. 			} elseif ($token instanceof LeftParenthesis) {
  120. 				$this->operatorStack->push($token);
  121. 			} elseif ($token instanceof RightParenthesis) {
  122. 				$operatorTop = $this->operatorStack->top();
  123. 				if (!$operatorTop instanceof LeftParenthesis) {
  124. 					$outputQueue->enqueue($this->operatorStack->pop());
  125. 				}
  126. 				$this->operatorStack->pop();
  127. 			} else throw new \Exception(sprintf('Invalid type %s given', gettype($token)));
  128. 		}
  129.  
  130. 		while (!$this->operatorStack->isEmpty()) {
  131. 			$operatorTop = $this->operatorStack->pop();
  132. 			$outputQueue->enqueue($operatorTop);
  133. 		}
  134.  
  135. 		return $outputQueue;
  136. 	}
  137. }
  138.  
  139. class Division extends BinaryOperator
  140. {
  141. 	public static $precedence = 3;
  142. 	public static $isLeftAssociative = true;
  143.  
  144. 	public function operate(SimpleFraction $leftOperand, SimpleFraction $rightOperand)
  145. 	{
  146.         if ($rightOperand->getNumerator() === 0) {
  147.             throw new DivideByZeroException($leftOperand);
  148.         }
  149.  
  150. 		$newRightOperand = $rightOperand->invert();
  151. 		$multiplication = new Multiplication();
  152.  
  153. 		return $multiplication->operate($leftOperand, $newRightOperand);
  154. 	}
  155. }
  156.  
  157.  
  158. abstract class AbstractOperator
  159. {
  160.     public function getPrecedence()
  161.     {
  162.         return static::$precedence;
  163.     }
  164.  
  165.     public function isLeftAssociative()
  166.     {
  167.         return !! static::$isLeftAssociative;
  168.     }
  169.  
  170.     public function isRightAssociative()
  171.     {
  172.         return ! static::$isLeftAssociative;
  173.     }
  174. }
  175.  
  176. class Multiplication extends BinaryOperator
  177. {
  178. 	public static $precedence = 3;
  179. 	public static $isLeftAssociative = true;
  180.  
  181. 	public function operate(SimpleFraction $leftOperand, SimpleFraction $rightOperand)
  182. 	{
  183.         $newNumerator = $leftOperand->getNumerator() * $rightOperand->getNumerator();
  184.         $newDenominator = $leftOperand->getDenominator() * $rightOperand->getDenominator();
  185.  
  186.         return new SimpleFraction($newNumerator, $newDenominator);
  187. 	}
  188. }
  189.  
  190. class OperatorFactory
  191. {
  192. 	public static function getOperatorBySign($sign)
  193. 	{
  194. 		switch ($sign) {
  195. 			case '+': return new Addition();
  196. 			case '-': return new Subtraction();
  197. 			case '*': return new Multiplication();
  198. 			case '/': return new Division();
  199. 			case '^': return new Power();
  200. 			case '(': return new LeftParenthesis();
  201. 			case ')': return new RightParenthesis();
  202.             case '#': return new UnaryNegative();
  203.             case '$': return new UnaryPositive();
  204. 			default: throw new \InvalidArgumentException();
  205. 		}
  206. 	}
  207. }
  208.  
  209. class Power extends BinaryOperator
  210. {
  211. 	public static $precedence = 4;
  212. 	public static $isLeftAssociative = false;
  213.  
  214. 	public function operate(SimpleFraction $leftOperand, SimpleFraction $rightOperand)
  215. 	{
  216.         $powerAsFraction = $rightOperand->getNumerator()/$rightOperand->getDenominator();
  217. 		$newNumerator = pow($leftOperand->getNumerator(), $powerAsFraction);
  218. 		$newDenominator = pow($leftOperand->getDenominator(), $powerAsFraction);
  219.  
  220. 		return new SimpleFraction($newNumerator, $newDenominator);
  221. 	}
  222. }
  223.  
  224. class RightParenthesis {}
  225.  
  226. class Subtraction extends BinaryOperator
  227. {
  228. 	public static $precedence = 2;
  229. 	public static $isLeftAssociative = true;
  230.  
  231. 	public function operate(SimpleFraction $leftOperand, SimpleFraction $rightOperand)
  232. 	{
  233.         $addition = new Addition();
  234.         $unaryNegative = new UnaryNegative();
  235.         $newRightOperand = $unaryNegative->operate($rightOperand);
  236.  
  237. 		return $addition->operate($leftOperand, $newRightOperand);
  238. 	}
  239. }
  240.  
  241. abstract class BinaryOperator extends AbstractOperator
  242. {
  243. 	abstract function operate(SimpleFraction $leftOperand, SimpleFraction $rightOperand);
  244. }
  245.  
  246. class UnaryPositive extends UnaryOperator
  247. {
  248.     public static $precedence = 5;
  249.     public static $isLeftAssociative = false;
  250.  
  251. 	public function operate(SimpleFraction $operand)
  252. 	{
  253.         return $operand;
  254. 	}
  255. }
  256.  
  257. class LeftParenthesis {}
  258.  
  259. class Addition extends BinaryOperator
  260. {
  261. 	public static $precedence = 2;
  262. 	public static $isLeftAssociative = true;
  263.  
  264. 	public function operate(SimpleFraction $leftOperand, SimpleFraction $rightOperand)
  265. 	{
  266. 		if ($rightOperand->getNumerator() === 0) {
  267. 			return $leftOperand;
  268. 		}
  269.  
  270. 		$commonDenominator = $leftOperand->getDenominator() * $rightOperand->getDenominator();
  271. 		$newNumerator = $leftOperand->getNumerator() * $rightOperand->getDenominator();
  272. 		$newNumerator += $leftOperand->getDenominator() * $rightOperand->getNumerator();
  273.  
  274. 		return new SimpleFraction($newNumerator, $commonDenominator);
  275. 	}
  276. }
  277.  
  278. abstract class UnaryOperator extends AbstractOperator
  279. {
  280. 	abstract function operate(SimpleFraction $operand);
  281. }
  282.  
  283. class UnaryNegative extends UnaryOperator
  284. {
  285.     public static $precedence = 5;
  286.     public static $isLeftAssociative = false;
  287.  
  288. 	public function operate(SimpleFraction $operand)
  289. 	{
  290.         $newNumerator = $operand->getNumerator() * (-1);
  291.         $newDenominator = $operand->getDenominator();
  292.  
  293. 		return new SimpleFraction($newNumerator, $newDenominator);
  294. 	}
  295. }
  296.  
  297. class DivideByZeroException extends \Exception
  298. {
  299. 	public function __construct($numerator)
  300. 	{
  301.        parent::__construct(sprintf("Ошибка: (%s/0) делить на ноль нельзя", $numerator));
  302.     }
  303. }
  304.  
  305. class InvalidInfixException extends \Exception {}
  306.  
  307. class MathHelper
  308. {
  309. 	public static function getLeastCommonMultiple($a, $b) {
  310. 		$max = max($a, $b);
  311. 		$min = min($a, $b);
  312.  
  313. 		$lcm = $max;
  314. 		for ($i = 1; $lcm % $min != 0; $i++) {
  315. 			$lcm = $max * $i;
  316. 		}
  317.  
  318. 		return $lcm;
  319. 	}
  320. }
  321.  
  322. class SimpleFraction
  323. {
  324. 	private $numerator; 
  325. 	private $denominator;
  326.  
  327. 	public function __construct($numerator, $denominator = 1)
  328. 	{
  329. 		$this->numerator = $numerator;
  330.         $this->denominator = $denominator;
  331. 		$this->simplify();
  332. 	}
  333.  
  334. 	public static function createFromDecimal($decimal)
  335. 	{
  336.         preg_match_all('/^(\-?\d+)(?:\.(\d+))?$/', (string) $decimal, $matches);
  337.         if (!$matches) throw new \InvalidArgumentException();
  338.         $integerPart = $matches[1][0];
  339.         $fractionalPart = empty($matches[2][0]) ? 0 : $matches[2][0];
  340.         $denominator = pow(10, strlen($fractionalPart));
  341.         $numerator = $integerPart * $denominator + $fractionalPart;
  342.  
  343. 		return new self($numerator, $denominator);
  344. 	}
  345.  
  346.     public function getDenominator()
  347. 	{
  348. 		return $this->denominator;
  349. 	}
  350.  
  351.     public function getNumerator()
  352. 	{
  353. 		return $this->numerator;
  354. 	}
  355.  
  356. 	public function invert()
  357. 	{
  358. 		list($this->denominator, $this->numerator) = [$this->numerator, $this->denominator];
  359.  
  360. 		return $this;
  361. 	}
  362.  
  363. 	public function showAsDecimal()
  364. 	{
  365.         $precision = 20;
  366.  
  367.         return (string) floatval(bcdiv($this->numerator, $this->denominator, $precision));
  368. 	}
  369.  
  370. 	public function __toString()
  371. 	{
  372.         if ($this->numerator === 0) {
  373.             $valueAsString = (string) 0;
  374.         } elseif ($this->denominator == 10) {
  375. 			$valueAsString = (string) $this->showAsDecimal();
  376. 		} elseif ($this->denominator == 1 || $this->denominator == -1) {
  377. 			$valueAsString = (string) ($this->numerator * $this->denominator);
  378. 		} else {
  379. 			$valueAsString = sprintf('%s/%s', $this->numerator, $this->denominator);
  380. 		}
  381.  
  382. 		return $valueAsString;
  383. 	}
  384.  
  385. 	private function simplify()
  386. 	{
  387. 		if ($this->numerator === 0) return;
  388. 		$lcm = MathHelper::getLeastCommonMultiple($this->numerator, $this->denominator);
  389. 		$oldNumerator = $this->numerator;
  390. 		$this->numerator = $lcm / $this->denominator;
  391. 		$this->denominator = $lcm / $oldNumerator;
  392. 	}
  393. }
  394.  
  395. class RpnQueueEvaluator
  396. {
  397. 	private $stack;
  398.  
  399. 	public function __construct()
  400. 	{
  401. 		$this->stack = new \SplStack;
  402. 	}
  403.  
  404. 	public function evaluate(\SplQueue $tokens)
  405. 	{
  406.         foreach ($tokens as $token) {
  407.             if ($token instanceof SimpleFraction) {
  408.                 $this->stack->push($token);
  409.             } elseif ($token instanceof AbstractOperator) {
  410.                 if ($token instanceof BinaryOperator) {
  411.                     $rightOperand = $this->stack->pop();
  412.                     $leftOperand = $this->stack->pop();
  413.                     $fraction = $token->operate($leftOperand, $rightOperand);
  414.                 } elseif ($token instanceof UnaryOperator) {
  415.                     $operand = $this->stack->pop();
  416.                     $fraction = $token->operate($operand);
  417.                 } else throw new \Exception(sprintf('Invalid type %s given', gettype($token)));
  418.                 $this->stack->push($fraction);
  419.             } else {
  420.                 throw new \InvalidArgumentException();
  421.             }
  422.         }
  423.  
  424. 		return $this->stack->top();
  425. 	}
  426. }
  427.  
  428. $infix_correctAnswer = [
  429.     '3-(#2)' => '5',
  430.     '($2)' => '2',
  431.     '$(#2)' => '-2',
  432.     '#(#1)' => '1',
  433.     '(5+7)*(#3-(#1))' => '-24',
  434.     '3+#2' => 'InvalidInfix',
  435.     '#($($(#3)))' => '3',
  436.     '(9/1) ^ (1/2)' => '3',
  437.     '2-(#2)' => '4',
  438.     '(#2)*(#3)' => '6',
  439.     '10/(#1)*(#2)' => '20',
  440.     '(#3)-(#3)' => '0',
  441.     '2+4-(#2)' => '8',
  442.     '0 - (#3)' => '3',
  443.     '1 - 3' => '-2',
  444.     '0 - 3' => '-3',
  445.     '0 / 0' => 'DivideByZero',
  446.     '0/2' => '0',
  447.     '(2 + 6) / (1 - 1)' => 'DivideByZero',
  448. 	'9 ^ 0' => '1',
  449. 	'9 ^ 2 ^ 0' => '9',
  450.     '17654/342' => '8827/171',
  451. 	'4 - 3' => ' 1',
  452. 	'2 + (#3)' => '-1',
  453. 	'4 * 5' => '20',
  454. 	'6/4' => '3/2',
  455. 	'1.2 + 1/2' => '1.7',
  456. 	'1/(#3)' => '-1/3',
  457. 	'0.5 + 0.2' => '0.7',
  458. 	'2/3 ^ 2' => '2/9',
  459.     '3 ^ 2 ^ 2' => '81',
  460.     '(((' => 'InvalidInfix',
  461.     '(1+2) * (4-2))' => 'InvalidInfix',
  462.     '+ +' => 'InvalidInfix',
  463.     '#3' => '-3',
  464.     '-3' => 'InvalidInfix',
  465.     '+3-' => 'InvalidInfix',
  466.     '1 2 3' => 'InvalidInfix',
  467.     '>34%; + 3w' => 'InvalidInfix',
  468. ];
  469.  
  470. $lexer = new Lexer();
  471. $tokenizer = new Tokenizer();
  472. $shuntingYard = new ShuntingYard();
  473. $rpnQueueEvaluator = new RpnQueueEvaluator();
  474.  
  475. echo "\n# - унарный минус, $ - унарный  плюс\n" . str_pad("Выражение в инфиксной нотации", 61) . str_pad("Ожидается", 31) . "Получено";
  476. foreach ($infix_correctAnswer as $infix => $correctAnswer) {
  477.     echo sprintf("\n%30s %13s ", $infix, $correctAnswer);
  478.     try {
  479.         $lexems = $lexer->getLexemsFromInfix($infix);
  480.         $tokens = $tokenizer->tokenizeLexems($lexems);
  481.         $rpnQueue = $shuntingYard->createRpnQueueFromTokens($tokens);
  482.         $result = $rpnQueueEvaluator->evaluate($rpnQueue);
  483.         echo sprintf('%20s', $result);
  484.     } catch (InvalidInfixException $e) {
  485.         echo $e->getMessage();
  486.     } catch (DivideByZeroException $e) {
  487.         echo $e->getMessage();
  488.     }
  489. }
  490.  
Success #stdin #stdout 0.04s 52480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
# - унарный минус, $ - унарный  плюс
Выражение в инфиксной нотации      Ожидается             Получено
                        3-(#2)             5                    5
                          ($2)             2                    2
                         $(#2)            -2                   -2
                         #(#1)             1                    1
               (5+7)*(#3-(#1))           -24                  -24
                          3+#2  InvalidInfix Ошибка: унарный оператор нужно заключать в скобки, если он не в начале выражения
                   #($($(#3)))             3                    3
                 (9/1) ^ (1/2)             3                    3
                        2-(#2)             4                    4
                     (#2)*(#3)             6                    6
                  10/(#1)*(#2)            20                   20
                     (#3)-(#3)             0                    0
                      2+4-(#2)             8                    8
                      0 - (#3)             3                    3
                         1 - 3            -2                   -2
                         0 - 3            -3                   -3
                         0 / 0  DivideByZero Ошибка: (0/0) делить на ноль нельзя
                           0/2             0                    0
             (2 + 6) / (1 - 1)  DivideByZero Ошибка: (8/0) делить на ноль нельзя
                         9 ^ 0             1                    1
                     9 ^ 2 ^ 0             9                    9
                     17654/342      8827/171             8827/171
                         4 - 3             1                    1
                      2 + (#3)            -1                   -1
                         4 * 5            20                   20
                           6/4           3/2                  3/2
                     1.2 + 1/2           1.7                  1.7
                        1/(#3)          -1/3                 1/-3
                     0.5 + 0.2           0.7                  0.7
                       2/3 ^ 2           2/9                  2/9
                     3 ^ 2 ^ 2            81                   81
                           (((  InvalidInfix Ошибка: скобки расставлены неправильно
                (1+2) * (4-2))  InvalidInfix Ошибка: скобки расставлены неправильно
                           + +  InvalidInfix Ошибка: в выражении должно быть по меньшей мере одно число
                            #3            -3                   -3
                            -3  InvalidInfix Ошибка: количество бинарных операторов должно быть на один меньше, чем количество чисел
                           +3-  InvalidInfix Ошибка: количество бинарных операторов должно быть на один меньше, чем количество чисел
                         1 2 3  InvalidInfix Ошибка: количество бинарных операторов должно быть на один меньше, чем количество чисел
                    >34%; + 3w  InvalidInfix Ошибка: в выражении недопустимые символы >, %, ;, w
https://ideone.com/cBTzfZ
language:
PHP (php 7.3.5)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!