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. abstract class AbstractOperator
  158. {
  159.     public function getPrecedence()
  160.     {
  161.         return static::$precedence;
  162.     }
  163.  
  164.     public function isLeftAssociative()
  165.     {
  166.         return !! static::$isLeftAssociative;
  167.     }
  168.  
  169.     public function isRightAssociative()
  170.     {
  171.         return ! static::$isLeftAssociative;
  172.     }
  173. }
  174.  
  175. class Multiplication extends BinaryOperator
  176. {
  177. 	public static $precedence = 3;
  178. 	public static $isLeftAssociative = true;
  179.  
  180. 	public function operate(SimpleFraction $leftOperand, SimpleFraction $rightOperand)
  181. 	{
  182.         $newNumerator = $leftOperand->getNumerator() * $rightOperand->getNumerator();
  183.         $newDenominator = $leftOperand->getDenominator() * $rightOperand->getDenominator();
  184.  
  185.         return new SimpleFraction($newNumerator, $newDenominator);
  186. 	}
  187. }
  188.  
  189. class OperatorFactory
  190. {
  191. 	public static function getOperatorBySign($sign)
  192. 	{
  193. 		switch ($sign) {
  194. 			case '+': return new Addition();
  195. 			case '-': return new Subtraction();
  196. 			case '*': return new Multiplication();
  197. 			case '/': return new Division();
  198. 			case '^': return new Power();
  199. 			case '(': return new LeftParenthesis();
  200. 			case ')': return new RightParenthesis();
  201.             case '#': return new UnaryNegative();
  202.             case '$': return new UnaryPositive();
  203. 			default: throw new \InvalidArgumentException();
  204. 		}
  205. 	}
  206. }
  207.  
  208. class Power extends BinaryOperator
  209. {
  210. 	public static $precedence = 4;
  211. 	public static $isLeftAssociative = false;
  212.  
  213. 	public function operate(SimpleFraction $leftOperand, SimpleFraction $rightOperand)
  214. 	{
  215.         $powerAsFraction = $rightOperand->getNumerator()/$rightOperand->getDenominator();
  216. 		$newNumerator = pow($leftOperand->getNumerator(), $powerAsFraction);
  217. 		$newDenominator = pow($leftOperand->getDenominator(), $powerAsFraction);
  218.  
  219. 		return new SimpleFraction($newNumerator, $newDenominator);
  220. 	}
  221. }
  222.  
  223. class LeftParenthesis {}
  224. class RightParenthesis {}
  225. class Subtraction extends BinaryOperator
  226. {
  227. 	public static $precedence = 2;
  228. 	public static $isLeftAssociative = true;
  229.  
  230. 	public function operate(SimpleFraction $leftOperand, SimpleFraction $rightOperand)
  231. 	{
  232.         $addition = new Addition();
  233.         $unaryNegative = new UnaryNegative();
  234.         $newRightOperand = $unaryNegative->operate($rightOperand);
  235.  
  236. 		return $addition->operate($leftOperand, $newRightOperand);
  237. 	}
  238. }
  239.  
  240. abstract class BinaryOperator extends AbstractOperator
  241. {
  242. 	abstract function operate(SimpleFraction $leftOperand, SimpleFraction $rightOperand);
  243. }
  244.  
  245. class UnaryPositive extends UnaryOperator
  246. {
  247.     public static $precedence = 5;
  248.     public static $isLeftAssociative = false;
  249.  
  250. 	public function operate(SimpleFraction $operand)
  251. 	{
  252.         return $operand;
  253. 	}
  254. }
  255.  
  256. class Addition extends BinaryOperator
  257. {
  258. 	public static $precedence = 2;
  259. 	public static $isLeftAssociative = true;
  260.  
  261. 	public function operate(SimpleFraction $leftOperand, SimpleFraction $rightOperand)
  262. 	{
  263. 		if ($rightOperand->getNumerator() === 0) {
  264. 			return $leftOperand;
  265. 		}
  266.  
  267. 		$commonDenominator = $leftOperand->getDenominator() * $rightOperand->getDenominator();
  268. 		$newNumerator = $leftOperand->getNumerator() * $rightOperand->getDenominator();
  269. 		$newNumerator += $leftOperand->getDenominator() * $rightOperand->getNumerator();
  270.  
  271.  
  272. 		return new SimpleFraction($newNumerator, $commonDenominator);
  273. 	}
  274. }
  275.  
  276. abstract class UnaryOperator extends AbstractOperator
  277. {
  278. 	abstract function operate(SimpleFraction $operand);
  279. }
  280.  
  281. class UnaryNegative extends UnaryOperator
  282. {
  283.     public static $precedence = 5;
  284.     public static $isLeftAssociative = false;
  285.  
  286. 	public function operate(SimpleFraction $operand)
  287. 	{
  288.         $newNumerator = $operand->getNumerator() * (-1);
  289.         $newDenominator = $operand->getDenominator();
  290.  
  291. 		return new SimpleFraction($newNumerator, $newDenominator);
  292. 	}
  293. }
  294.  
  295. class DivideByZeroException extends \Exception
  296. {
  297. 	public function __construct($numerator)
  298. 	{
  299.        parent::__construct(sprintf("Ошибка: (%s/0) делить на ноль нельзя", $numerator));
  300.     }
  301. }
  302.  
  303. class InvalidInfixException extends \Exception {}
  304. class MathHelper
  305. {
  306. 	public static function getLeastCommonMultiple($a, $b) {
  307. 		$max = max($a, $b);
  308. 		$min = min($a, $b);
  309.  
  310. 		$lcm = $max;
  311. 		for ($i = 1; $lcm % $min != 0; $i++) {
  312. 			$lcm = $max * $i;
  313. 		}
  314.  
  315. 		return $lcm;
  316. 	}
  317. }
  318.  
  319. class SimpleFraction
  320. {
  321. 	private $numerator; 
  322. 	private $denominator;
  323.  
  324. 	public function __construct($numerator, $denominator = 1)
  325. 	{
  326. 		$this->numerator = $numerator;
  327.         $this->denominator = $denominator;
  328. 		$this->simplify();
  329. 	}
  330.  
  331. 	public static function createFromDecimal($decimal)
  332. 	{
  333.         preg_match_all('/^(\-?\d+)(?:\.(\d+))?$/', (string) $decimal, $matches);
  334.         if (!$matches) throw new \InvalidArgumentException();
  335.         $integerPart = $matches[1][0];
  336.         $fractionalPart = empty($matches[2][0]) ? 0 : $matches[2][0];
  337.         $denominator = pow(10, strlen($fractionalPart));
  338.         $numerator = $integerPart * $denominator + $fractionalPart;
  339.  
  340. 		return new self($numerator, $denominator);
  341. 	}
  342.  
  343.     public function getDenominator()
  344. 	{
  345. 		return $this->denominator;
  346. 	}
  347.  
  348.     public function getNumerator()
  349. 	{
  350. 		return $this->numerator;
  351. 	}
  352.  
  353. 	public function invert()
  354. 	{
  355. 		list($this->denominator, $this->numerator) = [$this->numerator, $this->denominator];
  356.  
  357. 		return $this;
  358. 	}
  359.  
  360. 	public function showAsDecimal()
  361. 	{
  362.         $precision = 20;
  363.  
  364.         return (string) floatval(bcdiv($this->numerator, $this->denominator, $precision));
  365. 	}
  366.  
  367. 	public function __toString()
  368. 	{
  369.         if ($this->numerator === 0) {
  370.             $valueAsString = (string) 0;
  371.         } elseif ($this->denominator == 10) {
  372. 			$valueAsString = (string) $this->showAsDecimal();
  373. 		} elseif ($this->denominator == 1 || $this->denominator == -1) {
  374. 			$valueAsString = (string) ($this->numerator * $this->denominator);
  375. 		} else {
  376. 			$valueAsString = sprintf('%s/%s', $this->numerator, $this->denominator);
  377. 		}
  378.  
  379. 		return $valueAsString;
  380. 	}
  381.  
  382. 	private function simplify()
  383. 	{
  384. 		if ($this->numerator === 0) return;
  385. 		$lcm = MathHelper::getLeastCommonMultiple($this->numerator, $this->denominator);
  386. 		$oldNumerator = $this->numerator;
  387. 		$this->numerator = $lcm / $this->denominator;
  388. 		$this->denominator = $lcm / $oldNumerator;
  389. 	}
  390. }
  391.  
  392. class RpnQueueEvaluator
  393. {
  394. 	private $stack;
  395.  
  396. 	public function __construct()
  397. 	{
  398. 		$this->stack = new \SplStack;
  399. 	}
  400.  
  401. 	public function evaluate(\SplQueue $tokens)
  402. 	{
  403.         foreach ($tokens as $token) {
  404.             if ($token instanceof SimpleFraction) {
  405.                 $this->stack->push($token);
  406.             } elseif ($token instanceof AbstractOperator) {
  407.                 if ($token instanceof BinaryOperator) {
  408.                     $rightOperand = $this->stack->pop();
  409.                     $leftOperand = $this->stack->pop();
  410.                     $fraction = $token->operate($leftOperand, $rightOperand);
  411.                 } elseif ($token instanceof UnaryOperator) {
  412.                     $operand = $this->stack->pop();
  413.                     $fraction = $token->operate($operand);
  414.                 } else throw new \Exception(sprintf('Invalid type %s given', gettype($token)));
  415.                 $this->stack->push($fraction);
  416.             } else {
  417.                 throw new \InvalidArgumentException();
  418.             }
  419.         }
  420.  
  421. 		return $this->stack->top();
  422. 	}
  423. }
  424.  
  425. $infix_correctAnswer = [
  426.     '3-(#2)' => '5',
  427.     '($2)' => '2',
  428.     '$(#2)' => '-2',
  429.     '#(#1)' => '1',
  430.     '(5+7)*(#3-(#1))' => '-24',
  431.     '3+#2' => 'InvalidInfix',
  432.     '#($($(#3)))' => '3',
  433.     '(9/1) ^ (1/2)' => '3',
  434.     '2-(#2)' => '4',
  435.     '(#2)*(#3)' => '6',
  436.     '10/(#1)*(#2)' => '20',
  437.     '(#3)-(#3)' => '0',
  438.     '2+4-(#2)' => '8',
  439.     '0 - (#3)' => '3',
  440.     '1 - 3' => '-2',
  441.     '0 - 3' => '-3',
  442.     '0 / 0' => 'DivideByZero',
  443.     '0/2' => '0',
  444.     '(2 + 6) / (1 - 1)' => 'DivideByZero',
  445. 	'9 ^ 0' => '1',
  446. 	'9 ^ 2 ^ 0' => '9',
  447.     '17654/342' => '8827/171',
  448. 	'4 - 3' => ' 1',
  449. 	'2 + (#3)' => '-1',
  450. 	'4 * 5' => '20',
  451. 	'6/4' => '3/2',
  452. 	'1.2 + 1/2' => '1.7',
  453. 	'1/(#3)' => '-1/3',
  454. 	'0.5 + 0.2' => '0.7',
  455. 	'2/3 ^ 2' => '2/9',
  456.     '3 ^ 2 ^ 2' => '81',
  457.     '(((' => 'InvalidInfix',
  458.     '(1+2) * (4-2))' => 'InvalidInfix',
  459.     '+ +' => 'InvalidInfix',
  460.     '#3' => '-3',
  461.     '-3' => 'InvalidInfix',
  462.     '+3-' => 'InvalidInfix',
  463.     '1 2 3' => 'InvalidInfix',
  464.     '>34%; + 3w' => 'InvalidInfix',
  465. ];
  466.  
  467. $lexer = new Lexer();
  468. $tokenizer = new Tokenizer();
  469. $shuntingYard = new ShuntingYard();
  470. $rpnQueueEvaluator = new RpnQueueEvaluator();
  471.  
  472. echo "\n# - унарный минус, $ - унарный  плюс\n" . str_pad("Выражение в инфиксной нотации", 61) . str_pad("Ожидается", 31) . "Получено";
  473. foreach ($infix_correctAnswer as $infix => $correctAnswer) {
  474.     echo sprintf("\n%30s %13s ", $infix, $correctAnswer);
  475.     try {
  476.         $lexems = $lexer->getLexemsFromInfix($infix);
  477.         $tokens = $tokenizer->tokenizeLexems($lexems);
  478.         $rpnQueue = $shuntingYard->createRpnQueueFromTokens($tokens);
  479.         try {
  480.             $result = $rpnQueueEvaluator->evaluate($rpnQueue);
  481.             echo sprintf('%20s', $result);
  482.         } catch (DivideByZeroException $e) {
  483.             echo $e->getMessage();
  484.         }
  485.     } catch (InvalidInfixException $e) {
  486.         echo $e->getMessage();
  487.     }
  488. }
  489.  
Success #stdin #stdout 0.04s 52432KB
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/1sNagN
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!