fork(1) download
copy 
  1. <?php
  2.  
  3. set_exception_handler(function (Exception $e) {
  4. 	$e->getMessage();
  5. 	$e->getCode();
  6. 	$e->getFile();
  7. 	$e->getLine();
  8. 	$e->getTrace();
  9. });
  10.  
  11. set_error_handler(function ($errno, $errstr, $errfile, $errline ) {
  12.     throw new \ErrorException($errstr, $errno, 0, $errfile, $errline);
  13. });
  14.  
  15. class Addition extends ArithmeticOperator
  16. {
  17. 	public static $precedence = 2;
  18. 	public static $isLeftAssociative = true;
  19.  
  20. 	public function operate(SimpleFraction $leftOperand, SimpleFraction $rightOperand)
  21. 	{
  22. 		if ($rightOperand->getNumerator() === 0) {
  23. 			return $leftOperand;
  24. 		}
  25.  
  26. 		$commonDenumerator = $leftOperand->getDenumerator() * $rightOperand->getDenumerator();
  27. 		$resultNumerator = $leftOperand->getNumerator() * $rightOperand->getDenumerator();
  28. 		$resultNumerator += $leftOperand->getDenumerator() * $rightOperand->getNumerator();
  29.  
  30. 		return new SimpleFraction($resultNumerator, $commonDenumerator);
  31. 	}
  32. }
  33.  
  34. abstract class ArithmeticOperator
  35. {
  36. 	public function getPrecedence()
  37. 	{
  38. 		return static::$precedence;
  39. 	}
  40.  
  41. 	public function isLeftAssociative()
  42. 	{
  43. 		return !! static::$isLeftAssociative;
  44. 	}
  45.  
  46. 	public function isRightAssociative()
  47. 	{
  48. 		return ! static::$isLeftAssociative;
  49. 	}
  50.  
  51. 	abstract function operate(SimpleFraction $leftOperand, SimpleFraction $rightOperand);
  52. }
  53.  
  54. class DivideByZeroException extends Exception
  55. {
  56. 	public function __construct($numerator)
  57. 	{
  58. 		echo sprintf("Ошибка: (%s/0) делить на ноль нельзя", $numerator);
  59. 	}
  60. }
  61.  
  62. class Division extends ArithmeticOperator
  63. {
  64. 	public static $precedence = 3;
  65. 	public static $isLeftAssociative = true;
  66.  
  67. 	public function operate(SimpleFraction $leftOperand, SimpleFraction $rightOperand)
  68. 	{
  69. 		if ($rightOperand->getNumerator() === 0) {
  70. 			throw new DivideByZeroException($leftOperand);
  71. 		}
  72.  
  73. 		$multiplication = new Multiplication();
  74. 		return $multiplication->operate($leftOperand, $rightOperand->invert());
  75. 	}
  76. }
  77.  
  78. class LeftParenthesis {}
  79.  
  80. class Lexer
  81. {
  82. 	public function getLexemsFromInfix($infix)
  83. 	{
  84. 		if (!$this->isValidInfix($infix)) throw new InvalidArgumentException();
  85.  
  86. 		preg_match_all('/(-?\d+(\.\d+)?|([\+\-\/\*\^\(\)]))/', $infix, $match);
  87. 		$lexems = $match[0];
  88.  
  89. 		return $lexems;
  90. 	}
  91.  
  92. 	private function isValidInfix($infix)
  93. 	{
  94. 		return true;
  95. 	}
  96. }
  97.  
  98. class MathHelper
  99. {
  100. 	public static function getLeastCommonMultiple($a, $b) {
  101. 		$max = max($a, $b);
  102. 		$min = min($a, $b);
  103.  
  104. 		$lcm = $max;
  105. 		for ($i = 1; $lcm % $min != 0; $i++) { 
  106. 			$lcm = $max * $i;
  107. 		}
  108.  
  109. 		return $lcm;
  110. 	}
  111. }
  112.  
  113. class Multiplication extends ArithmeticOperator
  114. {
  115. 	public static $precedence = 3;
  116. 	public static $isLeftAssociative = true;
  117.  
  118. 	public function operate(SimpleFraction $leftOperand, SimpleFraction $rightOperand)
  119. 	{
  120. 		$newNumerator = $leftOperand->getNumerator() * $rightOperand->getNumerator();
  121. 		$newDenumerator = $leftOperand->getDenumerator() * $rightOperand->getDenumerator();
  122.  
  123. 		return new SimpleFraction($newNumerator, $newDenumerator);
  124. 	}
  125. }
  126.  
  127. class OperatorFactory
  128. {
  129. 	public static function getOperatorBySign($sign)
  130. 	{
  131. 		switch ($sign) {
  132. 			case '+': return new Addition();
  133. 			case '-': return new Substraction();
  134. 			case '*': return new Multiplication();
  135. 			case '/': return new Division();
  136. 			case '^': return new Power();
  137. 			case '(': return new LeftParenthesis();
  138. 			case ')': return new RightParenthesis();
  139. 			default: throw new InvalidArgumentException();
  140. 		}
  141. 	}
  142. }
  143.  
  144. class Power extends ArithmeticOperator
  145. {
  146. 	public static $precedence = 4;
  147. 	public static $isLeftAssociative = false;
  148.  
  149. 	public function operate(SimpleFraction $leftOperand, SimpleFraction $rightOperand)
  150. 	{
  151. 		$newNumerator = pow($leftOperand->getNumerator(), $rightOperand->getNumerator());
  152. 		$newDenumerator = pow($leftOperand->getDenumerator(), $rightOperand->getNumerator());
  153.  
  154. 		return new SimpleFraction($newNumerator, $newDenumerator);
  155. 	}
  156. }
  157.  
  158. class RightParenthesis {}
  159.  
  160. class RpnQueueEvaluator
  161. {
  162. 	private $stack;
  163.  
  164. 	public function __construct(SplStack $stack)
  165. 	{
  166. 		$this->stack = $stack;
  167. 	}
  168.  
  169. 	public function evaluate(SplQueue $tokens)
  170. 	{
  171. 		foreach ($tokens as $token) {
  172. 			if ($token instanceof SimpleFraction) {
  173. 				$this->stack->push($token);
  174. 			} elseif ($token instanceof ArithmeticOperator) {
  175. 				$rightOperand = $this->stack->pop();
  176. 				$leftOperand  = $this->stack->pop();
  177. 				$fraction = $token->operate($leftOperand, $rightOperand);
  178. 				$this->stack->push($fraction);
  179. 			} else {
  180. 				throw new InvalidArgumentException();
  181. 			}
  182. 		}
  183.  
  184. 		return $this->stack->top();
  185. 	}
  186. }
  187.  
  188. class ShuntingYard
  189. {
  190. 	private $operatorStack;
  191. 	private $outputQueue;
  192.  
  193. 	public function __construct(SplStack $operatorStack, SplQueue $outputQueue)
  194. 	{
  195. 		$this->operatorStack = $operatorStack;
  196. 		$this->outputQueue = $outputQueue;
  197. 	}
  198.  
  199. 	public function createRpnQueueFromTokens(array $tokens)
  200. 	{
  201. 		foreach ($tokens as $token) {
  202. 			if ($token instanceof SimpleFraction) {
  203. 				$this->outputQueue->enqueue($token);
  204. 			} elseif ($token instanceof ArithmeticOperator) {
  205. 				if ($this->operatorStack->isEmpty()) {
  206. 					$this->operatorStack->push($token);
  207. 					continue;
  208. 				}
  209.  
  210. 				$operatorTop = $this->operatorStack->top();
  211. 				if (($operatorTop instanceof ArithmeticOperator)
  212. 					&& (($token->isLeftassociative() && $token->getPrecedence() <= $operatorTop->getPrecedence())
  213.    					|| ($token->isRightAssociative() && $token->getPrecedence() < $operatorTop->getPrecedence()))
  214. 					) {
  215. 						$this->outputQueue->enqueue($this->operatorStack->pop());
  216. 				}
  217.  
  218. 				$this->operatorStack->push($token);
  219. 			} elseif ($token instanceof LeftParenthesis) {
  220. 				$this->operatorStack->push($token);
  221. 			} elseif ($token instanceof RightParenthesis) {
  222. 				$operatorTop = $this->operatorStack->top();
  223. 				if (!$operatorTop instanceof LeftParenthesis) {
  224. 					$this->outputQueue->enqueue($this->operatorStack->pop());
  225. 				}
  226. 				$this->operatorStack->pop();
  227. 			}
  228. 		}
  229.  
  230. 		while (!$this->operatorStack->isEmpty()) {
  231. 			$operatorTop = $this->operatorStack->pop();
  232. 			if ($operatorTop instanceof LeftParenthesis || $operatorTop instanceof RightParenthesis) {
  233. 				throw new Exception('Mismatched parentheses');
  234. 			}
  235. 			$this->outputQueue->enqueue($operatorTop);
  236. 		}
  237.  
  238. 		return $this->outputQueue;
  239. 	}
  240. }
  241.  
  242. class SimpleFraction
  243. {
  244. 	private $numerator; 
  245. 	private $denumerator;
  246.  
  247. 	public function __construct($numerator, $denumerator = 1)
  248. 	{
  249. 		$this->numerator = $numerator;
  250. 		$this->denumerator = $denumerator;
  251. 		$this->simplify();
  252. 	}
  253.  
  254. 	public static function createFromDecimal($decimal)
  255. 	{
  256. 		preg_match_all('/^(-?\d+)(?:\.(\d+))?$/', (string) $decimal, $matches);
  257.  
  258. 		if (!$matches) throw new InvalidArgumentException();
  259. 		$integerPart = $matches[1][0];
  260. 		$fractionalPart = empty($matches[2][0]) ? 0 : $matches[2][0];
  261.  
  262. 		$numerator = $integerPart * 10 + $fractionalPart;
  263. 		$denumerator = 10;
  264.  
  265. 		return new self($numerator, $denumerator);
  266. 	}
  267.  
  268. 	public function getDenumerator()
  269. 	{
  270. 		return $this->denumerator;
  271. 	}
  272.  
  273. 	public function getNumerator()
  274. 	{
  275. 		return $this->numerator;	
  276. 	}
  277.  
  278. 	public function changeSign()
  279. 	{
  280. 		$this->numerator *= -1;
  281.  
  282. 		return $this;
  283. 	}
  284.  
  285. 	public function invert()
  286. 	{
  287. 		list($this->denumerator, $this->numerator) = [$this->numerator, $this->denumerator];
  288.  
  289. 		return $this;
  290. 	}
  291.  
  292. 	public function showAsDecimal()
  293. 	{
  294. 		$result = $this->numerator / $this->denumerator;
  295.  
  296. 		if (is_int($result)) {
  297. 			$valueAsString = sprintf('%s', $result);
  298. 		} else {
  299. 			list($integerPart, $fractionalPart) = explode('.', (string) $result);
  300. 			$valueAsString = sprintf('%s.%s', $integerPart, $fractionalPart);
  301. 		}
  302.  
  303. 		return $valueAsString;
  304. 	}
  305.  
  306. 	public function __toString()
  307. 	{
  308. 		if ($this->denumerator == 10) {
  309. 			$valueAsString = sprintf('%s', $this->showAsDecimal());
  310. 		} elseif ($this->denumerator == 1 || $this->denumerator == -1) {
  311. 			$valueAsString = sprintf('%s', $this->numerator * $this->denumerator);
  312. 		} else {
  313. 			$valueAsString = sprintf('%s/%s', $this->numerator, $this->denumerator);
  314. 		}
  315.  
  316. 		return $valueAsString;
  317. 	}
  318.  
  319. 	private function simplify()
  320. 	{
  321. 		if ($this->numerator === 0) return;
  322. 		$lcm = MathHelper::getLeastCommonMultiple($this->numerator, $this->denumerator);
  323. 		$oldNumerator = $this->numerator;
  324. 		$this->numerator = $lcm / $this->denumerator;
  325. 		$this->denumerator = $lcm / $oldNumerator;
  326. 	}
  327. }
  328.  
  329. class Substraction extends ArithmeticOperator
  330. {
  331. 	public static $precedence = 2;
  332. 	public static $isLeftAssociative = true;
  333.  
  334. 	public function operate(SimpleFraction $leftOperand, SimpleFraction $rightOperand)
  335. 	{
  336. 		$addition = new Addition();
  337.  
  338. 		return $addition->operate($leftOperand, $rightOperand->changeSign());
  339. 	}
  340. }
  341.  
  342. class Tokenizer
  343. {
  344. 	public function tokenizeLexems(array $lexems)
  345. 	{
  346. 		$tokens = [];
  347.  
  348. 		foreach ($lexems as $lexem) {
  349. 			if (is_numeric($lexem)) {
  350. 				$fraction = SimpleFraction::createFromDecimal($lexem);
  351. 				$tokens[] = $fraction;
  352. 			} elseif (in_array($lexem, ['+', '-', '/', '*', '^', '(', ')'])) {
  353. 				$operator = OperatorFactory::getOperatorBySign($lexem);
  354. 				$tokens[] = $operator;
  355. 			} else {
  356. 				throw new Exception(sprintf('Invalid lexem %s given', $lexem));
  357. 			}
  358. 		}
  359.  
  360. 		return $tokens;
  361. 	}
  362. }
  363.  
  364. $infix_correctAnswer = [
  365. 	'2 + 3' => '5',
  366. 	'4 - 3' => ' 1',
  367. 	'2 + (-3)' => '-1',
  368. 	'4 * 5' => '20',
  369. 	'6/4' => '3/2',
  370. 	'1.2 + 1/2' => '1.7',
  371. 	'1/(-3)   ' => '-1/3',
  372. 	'0.5 + 0.2' => '0.7',
  373. 	'3 ^ 2 ^ 2' => '81',
  374. 	'17654/342' => '8827/171',
  375. 	'2/3 ^ 2' =>  '2/9',
  376. 	'(2/3) ^ 2' => '4/9',
  377. 	'(2 + 3) / (2 - 2)' => 'Ошибка',
  378. ];
  379.  
  380. $lexer = new Lexer();
  381. $tokenizer = new Tokenizer();
  382. $shuntingYard = new ShuntingYard(new SplStack, new SplQueue);
  383. $rpnQueueEvaluator = new RpnQueueEvaluator(new SplStack);
  384.  
  385. foreach ($infix_correctAnswer as $infix => $correctAnswer) {
  386. 	$lexems = $lexer->getLexemsFromInfix($infix);
  387. 	$tokens = $tokenizer->tokenizeLexems($lexems);
  388. 	$rpnQueue = $shuntingYard->createRpnQueueFromTokens($tokens);
  389. 	echo sprintf("\n%20s ожидается: %10s, получено ", $infix, $correctAnswer);
  390. 	$result = $rpnQueueEvaluator->evaluate($rpnQueue);
  391. 	echo sprintf('%10s', $result);
  392. }
  393.  
Success #stdin #stdout 0.03s 52432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
               2 + 3 ожидается:          5, получено          5
               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
           3 ^ 2 ^ 2 ожидается:         81, получено         81
           17654/342 ожидается:   8827/171, получено   8827/171
             2/3 ^ 2 ожидается:        2/9, получено        2/9
           (2/3) ^ 2 ожидается:        4/9, получено        4/9
   (2 + 3) / (2 - 2) ожидается: Ошибка, получено Ошибка: (5/0) делить на ноль нельзя
https://ideone.com/a4aeZ4
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!