<?php

set_error_handler(function ($errno, $errstr, $errfile, $errline ) {
    throw new \ErrorException($errstr, $errno, 0, $errfile, $errline);
});

class Tokenizer
{
	public function tokenizeLexems(array $lexems)
	{
		$tokens = [];

		foreach ($lexems as $lexem) {
			if (is_numeric($lexem)) {
				$fraction = SimpleFraction::createFromDecimal($lexem);
				$tokens[] = $fraction;
			} elseif (in_array($lexem, ['+', '-', '/', '*', '^', '(', ')', '#', '$'])) {
				$operator = OperatorFactory::getOperatorBySign($lexem);
				$tokens[] = $operator;
			} else {
				throw new \Exception(sprintf('Invalid lexem %s given', $lexem));
			}
		}

		return $tokens;
	}
}

class Lexer
{
	public function getLexemsFromInfix($infix)
	{
        $this->checkInfix($infix);

        preg_match_all('/(\d+(\.\d+)?|([\+\-\/\*\^\(\)\$#]))|(\S)/', $infix, $match);
        if ($invalidChars = array_filter($match[4])) {
            throw new InvalidInfixException(sprintf('Ошибка: в выражении недопустимые символы %s', implode(', ', $invalidChars)));
        }
		$lexems = $match[0];

		return $lexems;
	}

	private function checkInfix($infix)
	{
        $this->checkParenthesesIsMatched($infix);
        $this->checkDigitsAndBinaryOperators($infix);
        $this->checkUnaryOperators($infix);
	}

    private function checkParenthesesIsMatched($string)
    {
        $chars = str_split($string);

        $depth = 0;
        foreach ($chars as $char) {
            $depth += $char == '(';
            $depth -= $char == ')';

            if ($depth < 0) break;
        }

        if ($depth !== 0) throw new InvalidInfixException('Ошибка: скобки расставлены неправильно');
    }

    private function checkDigitsAndBinaryOperators($infix)
    {
        preg_match_all('/(\d+(\.\d+)?)|([\+\-\*\/\^])/', $infix, $match);

        $numbersAmount = count(array_filter($match[1], 'strlen')); // Без 'strlen' ф-я array_filter исключит цифру 0
        $binaryOperatorsAmount = count(array_filter($match[3], 'strlen'));

        if ($numbersAmount < 1) {
            throw new InvalidInfixException('Ошибка: в выражении должно быть по меньшей мере одно число');
        }
        if ($numbersAmount != ++$binaryOperatorsAmount) {
            throw new InvalidInfixException('Ошибка: количество бинарных операторов должно быть на один меньше, чем количество чисел');
        }
    }

    private function checkUnaryOperators($infix)
    {
        if (preg_match('/(?<!^|\()[#\$]/', $infix)) {
            throw new InvalidInfixException('Ошибка: унарный оператор нужно заключать в скобки, если он не в начале выражения');
        }
    }
}

class ShuntingYard
{
	private $operatorStack;

	public function __construct()
	{
		$this->operatorStack = new \SplStack;
	}

	public function createRpnQueueFromTokens(array $tokens)
	{
        $outputQueue = new \SplQueue();
		foreach ($tokens as $token) {
			if ($token instanceof SimpleFraction) {
				$outputQueue->enqueue($token);
			} elseif ($token instanceof AbstractOperator) {
				if ($this->operatorStack->isEmpty()) {
					$this->operatorStack->push($token);
					continue;
				}

				$operatorTop = $this->operatorStack->top();
				if (($operatorTop instanceof AbstractOperator)
					&& (($token->isLeftassociative() && $token->getPrecedence() <= $operatorTop->getPrecedence())
   					|| ($token->isRightAssociative() && $token->getPrecedence() < $operatorTop->getPrecedence()))
					) {
						$outputQueue->enqueue($this->operatorStack->pop());
				}

				$this->operatorStack->push($token);
			} elseif ($token instanceof LeftParenthesis) {
				$this->operatorStack->push($token);
			} elseif ($token instanceof RightParenthesis) {
				$operatorTop = $this->operatorStack->top();
				if (!$operatorTop instanceof LeftParenthesis) {
					$outputQueue->enqueue($this->operatorStack->pop());
				}
				$this->operatorStack->pop();
			} else throw new \Exception(sprintf('Invalid type %s given', gettype($token)));
		}

		while (!$this->operatorStack->isEmpty()) {
			$operatorTop = $this->operatorStack->pop();
			$outputQueue->enqueue($operatorTop);
		}

		return $outputQueue;
	}
}

class Division extends BinaryOperator
{
	public static $precedence = 3;
	public static $isLeftAssociative = true;

	public function operate(SimpleFraction $leftOperand, SimpleFraction $rightOperand)
	{
        if ($rightOperand->getNumerator() === 0) {
            throw new DivideByZeroException($leftOperand);
        }

		$newRightOperand = $rightOperand->invert();
		$multiplication = new Multiplication();

		return $multiplication->operate($leftOperand, $newRightOperand);
	}
}

abstract class AbstractOperator
{
    public function getPrecedence()
    {
        return static::$precedence;
    }

    public function isLeftAssociative()
    {
        return !! static::$isLeftAssociative;
    }

    public function isRightAssociative()
    {
        return ! static::$isLeftAssociative;
    }
}

class Multiplication extends BinaryOperator
{
	public static $precedence = 3;
	public static $isLeftAssociative = true;

	public function operate(SimpleFraction $leftOperand, SimpleFraction $rightOperand)
	{
        $newNumerator = $leftOperand->getNumerator() * $rightOperand->getNumerator();
        $newDenominator = $leftOperand->getDenominator() * $rightOperand->getDenominator();

        return new SimpleFraction($newNumerator, $newDenominator);
	}
}

class OperatorFactory
{
	public static function getOperatorBySign($sign)
	{
		switch ($sign) {
			case '+': return new Addition();
			case '-': return new Subtraction();
			case '*': return new Multiplication();
			case '/': return new Division();
			case '^': return new Power();
			case '(': return new LeftParenthesis();
			case ')': return new RightParenthesis();
            case '#': return new UnaryNegative();
            case '$': return new UnaryPositive();
			default: throw new \InvalidArgumentException();
		}
	}
}

class Power extends BinaryOperator
{
	public static $precedence = 4;
	public static $isLeftAssociative = false;

	public function operate(SimpleFraction $leftOperand, SimpleFraction $rightOperand)
	{
        $powerAsFraction = $rightOperand->getNumerator()/$rightOperand->getDenominator();
		$newNumerator = pow($leftOperand->getNumerator(), $powerAsFraction);
		$newDenominator = pow($leftOperand->getDenominator(), $powerAsFraction);

		return new SimpleFraction($newNumerator, $newDenominator);
	}
}

class LeftParenthesis {}
class RightParenthesis {}
class Subtraction extends BinaryOperator
{
	public static $precedence = 2;
	public static $isLeftAssociative = true;

	public function operate(SimpleFraction $leftOperand, SimpleFraction $rightOperand)
	{
        $addition = new Addition();
        $unaryNegative = new UnaryNegative();
        $newRightOperand = $unaryNegative->operate($rightOperand);

		return $addition->operate($leftOperand, $newRightOperand);
	}
}

abstract class BinaryOperator extends AbstractOperator
{
	abstract function operate(SimpleFraction $leftOperand, SimpleFraction $rightOperand);
}

class UnaryPositive extends UnaryOperator
{
    public static $precedence = 5;
    public static $isLeftAssociative = false;

	public function operate(SimpleFraction $operand)
	{
        return $operand;
	}
}

class Addition extends BinaryOperator
{
	public static $precedence = 2;
	public static $isLeftAssociative = true;

	public function operate(SimpleFraction $leftOperand, SimpleFraction $rightOperand)
	{
		if ($rightOperand->getNumerator() === 0) {
			return $leftOperand;
		}

		$commonDenominator = $leftOperand->getDenominator() * $rightOperand->getDenominator();
		$newNumerator = $leftOperand->getNumerator() * $rightOperand->getDenominator();
		$newNumerator += $leftOperand->getDenominator() * $rightOperand->getNumerator();


		return new SimpleFraction($newNumerator, $commonDenominator);
	}
}

abstract class UnaryOperator extends AbstractOperator
{
	abstract function operate(SimpleFraction $operand);
}

class UnaryNegative extends UnaryOperator
{
    public static $precedence = 5;
    public static $isLeftAssociative = false;

	public function operate(SimpleFraction $operand)
	{
        $newNumerator = $operand->getNumerator() * (-1);
        $newDenominator = $operand->getDenominator();

		return new SimpleFraction($newNumerator, $newDenominator);
	}
}

class DivideByZeroException extends \Exception
{
	public function __construct($numerator)
	{
       parent::__construct(sprintf("Ошибка: (%s/0) делить на ноль нельзя", $numerator));
    }
}

class InvalidInfixException extends \Exception {}
class MathHelper
{
	public static function getLeastCommonMultiple($a, $b) {
		$max = max($a, $b);
		$min = min($a, $b);

		$lcm = $max;
		for ($i = 1; $lcm % $min != 0; $i++) {
			$lcm = $max * $i;
		}

		return $lcm;
	}
}

class SimpleFraction
{
	private $numerator; 
	private $denominator;

	public function __construct($numerator, $denominator = 1)
	{
		$this->numerator = $numerator;
        $this->denominator = $denominator;
		$this->simplify();
	}

	public static function createFromDecimal($decimal)
	{
        preg_match_all('/^(\-?\d+)(?:\.(\d+))?$/', (string) $decimal, $matches);
        if (!$matches) throw new \InvalidArgumentException();
        $integerPart = $matches[1][0];
        $fractionalPart = empty($matches[2][0]) ? 0 : $matches[2][0];
        $denominator = pow(10, strlen($fractionalPart));
        $numerator = $integerPart * $denominator + $fractionalPart;

		return new self($numerator, $denominator);
	}

    public function getDenominator()
	{
		return $this->denominator;
	}

    public function getNumerator()
	{
		return $this->numerator;
	}

	public function invert()
	{
		list($this->denominator, $this->numerator) = [$this->numerator, $this->denominator];

		return $this;
	}

	public function showAsDecimal()
	{
        $precision = 20;

        return (string) floatval(bcdiv($this->numerator, $this->denominator, $precision));
	}

	public function __toString()
	{
        if ($this->numerator === 0) {
            $valueAsString = (string) 0;
        } elseif ($this->denominator == 10) {
			$valueAsString = (string) $this->showAsDecimal();
		} elseif ($this->denominator == 1 || $this->denominator == -1) {
			$valueAsString = (string) ($this->numerator * $this->denominator);
		} else {
			$valueAsString = sprintf('%s/%s', $this->numerator, $this->denominator);
		}

		return $valueAsString;
	}

	private function simplify()
	{
		if ($this->numerator === 0) return;
		$lcm = MathHelper::getLeastCommonMultiple($this->numerator, $this->denominator);
		$oldNumerator = $this->numerator;
		$this->numerator = $lcm / $this->denominator;
		$this->denominator = $lcm / $oldNumerator;
	}
}

class RpnQueueEvaluator
{
	private $stack;

	public function __construct()
	{
		$this->stack = new \SplStack;
	}

	public function evaluate(\SplQueue $tokens)
	{
        foreach ($tokens as $token) {
            if ($token instanceof SimpleFraction) {
                $this->stack->push($token);
            } elseif ($token instanceof AbstractOperator) {
                if ($token instanceof BinaryOperator) {
                    $rightOperand = $this->stack->pop();
                    $leftOperand = $this->stack->pop();
                    $fraction = $token->operate($leftOperand, $rightOperand);
                } elseif ($token instanceof UnaryOperator) {
                    $operand = $this->stack->pop();
                    $fraction = $token->operate($operand);
                } else throw new \Exception(sprintf('Invalid type %s given', gettype($token)));
                $this->stack->push($fraction);
            } else {
                throw new \InvalidArgumentException();
            }
        }

		return $this->stack->top();
	}
}

$infix_correctAnswer = [
    '3-(#2)' => '5',
    '($2)' => '2',
    '$(#2)' => '-2',
    '#(#1)' => '1',
    '(5+7)*(#3-(#1))' => '-24',
    '3+#2' => 'InvalidInfix',
    '#($($(#3)))' => '3',
    '(9/1) ^ (1/2)' => '3',
    '2-(#2)' => '4',
    '(#2)*(#3)' => '6',
    '10/(#1)*(#2)' => '20',
    '(#3)-(#3)' => '0',
    '2+4-(#2)' => '8',
    '0 - (#3)' => '3',
    '1 - 3' => '-2',
    '0 - 3' => '-3',
    '0 / 0' => 'DivideByZero',
    '0/2' => '0',
    '(2 + 6) / (1 - 1)' => 'DivideByZero',
	'9 ^ 0' => '1',
	'9 ^ 2 ^ 0' => '9',
    '17654/342' => '8827/171',
	'4 - 3' => ' 1',
	'2 + (#3)' => '-1',
	'4 * 5' => '20',
	'6/4' => '3/2',
	'1.2 + 1/2' => '1.7',
	'1/(#3)' => '-1/3',
	'0.5 + 0.2' => '0.7',
	'2/3 ^ 2' => '2/9',
    '3 ^ 2 ^ 2' => '81',
    '(((' => 'InvalidInfix',
    '(1+2) * (4-2))' => 'InvalidInfix',
    '+ +' => 'InvalidInfix',
    '#3' => '-3',
    '-3' => 'InvalidInfix',
    '+3-' => 'InvalidInfix',
    '1 2 3' => 'InvalidInfix',
    '>34%; + 3w' => 'InvalidInfix',
];

$lexer = new Lexer();
$tokenizer = new Tokenizer();
$shuntingYard = new ShuntingYard();
$rpnQueueEvaluator = new RpnQueueEvaluator();

echo "\n# - унарный минус, $ - унарный  плюс\n" . str_pad("Выражение в инфиксной нотации", 61) . str_pad("Ожидается", 31) . "Получено";
foreach ($infix_correctAnswer as $infix => $correctAnswer) {
    echo sprintf("\n%30s %13s ", $infix, $correctAnswer);
    try {
        $lexems = $lexer->getLexemsFromInfix($infix);
        $tokens = $tokenizer->tokenizeLexems($lexems);
        $rpnQueue = $shuntingYard->createRpnQueueFromTokens($tokens);
        try {
            $result = $rpnQueueEvaluator->evaluate($rpnQueue);
            echo sprintf('%20s', $result);
        } catch (DivideByZeroException $e) {
            echo $e->getMessage();
        }
    } catch (InvalidInfixException $e) {
        echo $e->getMessage();
    }
}