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