<?php

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

bcscale(50); // Количество знаков после запятой по умолчанию

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

class NegativeBaseRootException extends \Exception
{
	public function __construct($base)
	{
       parent::__construct(sprintf("Нельзя получить вещественный корень отрицательного числа %s", $base));
    }
}

class InvalidInfixException extends \Exception {}

class Parser
{
    public function getTokensFromInfix($infix)
    {
        $tokensQueue = new \SplQueue();
        $lexems = $this->getLexemsFromInfix($infix);
        $binaryOperatorsCount = 0;
        $operandsCount = 0;
        $parenthesisDeep = 0;

        foreach ($lexems as $lexem) {
            if (is_numeric($lexem)) {
                $tokensQueue->push(SimpleFraction::createFromDecimal($lexem));
                $operandsCount++;
            } elseif (in_array($lexem, ['+', '-'])) {
                if ($tokensQueue->isEmpty() || $tokensQueue->top() instanceof LeftParenthesis) {
                    $tokensQueue->push(OperationFactory::getUnaryBySign($lexem));
                } elseif ($tokensQueue->top() instanceof SimpleFraction || $tokensQueue->top() instanceof RightParenthesis) {
                    $tokensQueue->push(OperationFactory::getBinaryBySign($lexem));
                    $binaryOperatorsCount++;
                } else {
                    throw new InvalidInfixException(sprintf('В выражении встречаются подряд несколько операторов'));
                }
            } elseif (in_array($lexem, ['*', '/', '^'])) {
                $tokensQueue->push(OperationFactory::getBinaryBySign($lexem));
                $binaryOperatorsCount++;
            } elseif ($lexem === '(') {
                $tokensQueue->push(new LeftParenthesis());
                $parenthesisDeep--;
            } elseif ($lexem === ')') {
                $tokensQueue->push(new RightParenthesis());
                $parenthesisDeep++;
            } else {
                throw new InvalidInfixException(sprintf('Нераспознанная лексема %s', $lexem));
            }
        }

        if ($operandsCount !== ++$binaryOperatorsCount) {
            throw new InvalidInfixException('Количество бинарных операторов должно быть на один меньше, чем количество чисел');
        }
        if ($parenthesisDeep !== 0) {
            throw new InvalidInfixException('Неправильно расставлены скобки');
        }

        return $tokensQueue;
    }

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

        return $lexems;
    }
}

class ShuntingYard
{
	private $operatorStack;

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

	public function createRpnQueueFromTokens(\SplQueue $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();
            if ($operatorTop instanceof LeftParenthesis || $operatorTop instanceof RightParenthesis) {
                throw new InvalidInfixException('Mismatched parentheses');
            }
			$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 = MathHelper::mul($leftOperand->getNumerator(), $rightOperand->getNumerator());
        $newDenominator = MathHelper::mul($leftOperand->getDenominator(), $rightOperand->getDenominator());
        $isPrecise = $leftOperand->isAccurate() && $rightOperand->isAccurate();

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

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

	public function operate(SimpleFraction $leftOperand, SimpleFraction $rightOperand)
	{
        // Происходит попытка получить корень отрицательного числа
        if ($leftOperand->getSign() === SimpleFraction::SIGN_MINUS && !$rightOperand->isInteger()) {
            throw new NegativeBaseRootException($leftOperand);
        }

        // Происходит попытка возвести в отрицательную степень
        if ($rightOperand->getSign() === SimpleFraction::SIGN_MINUS) {
            $newDenominator = $this->operate($leftOperand, $rightOperand->changeSign());
            $result = (new Division())->operate(SimpleFraction::createFromDecimal('1'), $newDenominator);

            return $result;
        }

        // Если возводим в целую степень, то можно использовать bcpow
        if ($rightOperand->isInteger()) {
            $newNumerator = MathHelper::pow($leftOperand->getNumerator(), $rightOperand->getNumerator());
            $newDenominator = MathHelper::pow($leftOperand->getDenominator(), $rightOperand->getDenominator());
            $isAccuracy = $leftOperand->isAccurate() && $rightOperand->isAccurate();
        } else {
            $powerAsFraction = $rightOperand->getNumerator() / $rightOperand->getDenominator();
            $newNumerator = pow($leftOperand->getNumerator(), $powerAsFraction);
            $newDenominator = pow($leftOperand->getDenominator(), $powerAsFraction);

            // Определение точности дроби на основе результатов bcpow и pow
            if ((MathHelper::pow($newNumerator, $rightOperand->getDenominator())
                !== (string) pow($newNumerator, $rightOperand->getDenominator()))
            ) {
                $isAccuracy = false;
                // Из $newNumerator и $newDenumerator нельзя создать дробь, так как эти переменные содержат неточные десятичные дроби
                $inaccuracyDecimal = $newNumerator / $newDenominator;

                return SimpleFraction::createFromDecimal($inaccuracyDecimal, $isAccuracy);
            } else {
                $isAccuracy = true;
            }
        }

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

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 LeftParenthesis {}
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 = MathHelper::mul($leftOperand->getDenominator(), $rightOperand->getDenominator());
		$newNumerator = MathHelper::add(
            MathHelper::mul($leftOperand->getDenominator(), $rightOperand->getNumerator()),
            MathHelper::mul($leftOperand->getNumerator(), $rightOperand->getDenominator())
        );
        $isAccurate = $leftOperand->isAccurate() && $rightOperand->isAccurate();

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

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)
	{
        $newSimpleFraction = $operand->changeSign();

		return $newSimpleFraction;
	}
}

class OperationFactory
{
    public static function getBinaryBySign($sign)
    {
        switch ($sign) {
            case '+': return new Addition();
            case '-': return new Subtraction();
            case '*': return new Multiplication();
            case '/': return new Division();
            case '^': return new Power();
            default:
                throw new \Exception(sprintf('Binary operation %s is not presented', $sign));
        }
    }

    public static function getUnaryBySign($sign)
    {
        switch ($sign) {
            case '+': return new UnaryPositive();
            case '-': return new UnaryNegative();
            default:
                throw new \Exception(sprintf('Unary operation %s is not presented', $sign));
        }
    }
}

class MathHelper
{
    public static function getGreatestCommonDivisor($a, $b)
    {
        $gcd = gmp_gcd($a, $b);

        return gmp_strval($gcd);
    }

    // Удаляет лишние нули после дробной части, которые возникли из-за bcscale(50)
    public static function removeTrailingZeros($decimal)
    {
        $decimal = (string) $decimal;
        if (strpos($decimal, '.') === false) {
            return $decimal;
        }

        return preg_replace('/\.?0+$/', '', $decimal);
    }

    public static function div($leftString, $rightString)
    {
        return self::removeTrailingZeros(bcdiv($leftString, $rightString));
    }

    public static function mul($leftString, $rightString)
    {
        return self::removeTrailingZeros(bcmul($leftString, $rightString));
    }

    public static function add($leftString, $rightString)
    {
        return self::removeTrailingZeros(bcadd($leftString, $rightString));
    }

    public static function sub($leftString, $rightString)
    {
        return self::removeTrailingZeros(bcsub($leftString, $rightString));
    }

    public static function pow($leftString, $rightString)
    {
        return self::removeTrailingZeros(bcpow($leftString, $rightString));
    }
}

class SimpleFraction
{
	private $numerator;
	private $denominator;
    // Флаг точности
    private $isAccurate;

    const SIGN_PLUS = '+';
    const SIGN_MINUS = '-';
    const SIGN_INACCURATE = '~';
    const SIGN_ACCURATE = '';

	public function __construct($numerator, $denominator = 1, $isAccurate = true)
	{
		$this->numerator = MathHelper::removeTrailingZeros($numerator);
        $this->denominator = MathHelper::removeTrailingZeros($denominator);
        $this->isAccurate = $isAccurate;
		$this->simplify();
	}

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

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

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

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

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

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

		return $this;
	}

    public function getSign()
    {
        return (strpos($this->numerator, '-') === 0) ? self::SIGN_MINUS : self::SIGN_PLUS;
    }

    public function changeSign()
    {
        $this->numerator = MathHelper::mul($this->numerator, '-1');

        return $this;
    }

    // Можно ли дробь представить в виде целого числа
    public function isInteger()
    {
        return !! ($this->denominator === '1' || $this->numerator === '0');
    }

	public function showAsDecimal()
	{
        return sprintf('%s%s',
            $this->getPrecisionSign(),
            MathHelper::div($this->numerator, $this->denominator)
        );
	}

    private function getPrecisionSign()
    {
        return ($this->isAccurate()) ? self::SIGN_ACCURATE : self::SIGN_INACCURATE;
    }

	public function __toString()
	{
        if ($this->numerator === '0') {
            $valueAsString = '0';
        } elseif (preg_match('/^10*$/', $this->denominator)) {
            // Если знаменатель - любая целая степень 10-и, то показать дробь как целое число
			$valueAsString = $this->showAsDecimal();
		} else {
			$valueAsString = sprintf('%s/%s',
                $this->numerator,
                $this->denominator
            );
		}

		return $valueAsString;
	}

	private function simplify()
	{
		if ($this->numerator === '0') {
            return;
        }

        // Упрощение дроби с использованием НОД
		$gcd = MathHelper::getGreatestCommonDivisor($this->numerator, $this->denominator);
        $this->numerator = MathHelper::div($this->numerator, $gcd);
        $this->denominator = MathHelper::div($this->denominator, $gcd);

        // Если знаменатель отрицательный - перенести минус в числитель
        if (strpos($this->denominator, '-') === 0) {
            $this->denominator = substr($this->denominator, 1);
            $this->numerator = MathHelper::mul($this->numerator, '-1');
        }
	}
}

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 = [
    '1/1000' => '0.001',
    '100/1' => '100',
     '123456789123456789123456789/100' => '1234567891234567891234567.89',
    '1230/100' => '12.3',
    '2^(1/2)' => SimpleFraction::SIGN_INACCURATE . pow(2, 1/2),
    '-2 ^ 2' => '4',
    '-2 ^ (-1/2)' => 'NegativeBaseRoot',
    '8 ^ (-2/3)' => '1/4',
    '16 ^ 0.75' => '8',
    '(9/1) ^ (1/2)' => '3',
    '2/3 ^ 2' => '2/9',
    '3 ^ 2 ^ 2' => '81',
    '9 ^ 0' => '1',
    '9 ^ 2 ^ 0' => '9',
    '3-(-2)' => '5',
    '(+2)' => '2',
    '+(-2)' => '-2',
    '-(-1)' => '1',
    '(5+7)*(-3-(-1))' => '-24',
    '3+-2' => 'InvalidInfix',
    '-(+(+(-3)))' => '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',
    '(2 + 6) / (1 - 1)' => 'DivideByZero',
    '0 / 0' => 'DivideByZero',
    '-0' => '0',
    '0/2' => '0',
    '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',
    '(((' => 'InvalidInfix',
    '(1+2) * (4-2))' => 'InvalidInfix',
    '+ +' => 'InvalidInfix',
    '-3' => '-3',
    '+3-' => 'InvalidInfix',
    '1 2 3' => 'InvalidInfix',
    '>34%; + 3w' => 'InvalidInfix',
    '1)' => 'InvalidInfix',
    '0.000000000000000000000000001 + 0.000000000000000000000000002' => '0.000000000000000000000000003',
];

$parser = new Parser;
$shuntingYard = new ShuntingYard;
$rpnQueueEvaluator = new RpnQueueEvaluator;

echo sprintf('Выражение в инфиксной нотации %7s Ожидается %11s Получено', '', '');
foreach ($infix_correctAnswer as $infix => $correctAnswer) {
    echo sprintf("\n%29s %17s ", $infix, $correctAnswer);
    try {
        $tokenQueue = $parser->getTokensFromInfix($infix);
        $rpnQueue = $shuntingYard->createRpnQueueFromTokens($tokenQueue);
        $result = $rpnQueueEvaluator->evaluate($rpnQueue);
        echo sprintf('%20s', $result);
    } catch (InvalidInfixException $e) {
        echo $e->getMessage();
    } catch (DivideByZeroException $e) {
        echo $e->getMessage();
    } catch (NegativeBaseRootException $e) {
        echo $e->getMessage();
    }
}