<?php
abstract class AbstractOperator{
    
    const ASSOCIATIVE_LEFT = 0;
    const ASSOCIATIVE_RIGHT = 1;
    
    private $associative_map = array(
        self::ASSOCIATIVE_LEFT,
        self::ASSOCIATIVE_RIGHT
    );
    
    protected $priority = null;
    protected $token = null;
    protected $operands_count = null;
    protected $associative = null;
    
    final public function __construct()
    {
        
    }
    
    abstract protected function doExecute(array $operands);
    
    public function execute(array $operands)
    {
        if (count($operands) != $this->getOperandsCount()){
            throw new Exception('Operands count must be equal ' . $this->getOperandsCount());
        }
        $operands = array_values($operands);
        return $this->doExecute($operands);
    }
    
    public function getAssociative()
    {
        if (is_null($this->associative)){
            throw new Exception('Associative is empty');
        }
        if (!in_array($this->associative, $this->associative_map)){
            throw new Exception('Invalid associative value'); 
        }
        return $this->associative;
    }
    
    public function getOperandsCount()
    {
        if (is_null($this->operands_count)){
            throw new Exception('Operands count is empty');
        }
        return $this->operands_count;
    }
    
    public function comparePriority(AbstractOperator $operator){
        if (is_null($this->priority)){
            throw new Exception('Priority is empty');
        }
        $num = $this->priority - $operator->priority;
        return ($num > 0) ? 1 : (($num < 0) ? -1 : 0);
    }
    
    public function __toString()
    {
        if (is_null($this->token)){
            throw new Exception('Token is empty');
        }
        return $this->token;
    }
}

class PowOperator extends AbstractOperator{
    
    protected $priority = 2;
    protected $token = '^';
    protected $operands_count = 2;
    protected $associative = parent::ASSOCIATIVE_RIGHT;
    
    protected function doExecute(array $operands){
        return pow($operands[0], $operands[1]);
    }
    
}

class AddOperator extends AbstractOperator{
    
    protected $priority = 0;
    protected $token = '+';
    protected $operands_count = 2;
    protected $associative = parent::ASSOCIATIVE_LEFT;
    
    protected function doExecute(array $operands){
        return $operands[0] + $operands[1];
    }
    
}

class SubOperator extends AbstractOperator{
    
    protected $priority = 0;
    protected $token = '-';
    protected $operands_count = 2;
    protected $associative = parent::ASSOCIATIVE_LEFT;
    
    protected function doExecute(array $operands){
        return $operands[0] - $operands[1];
    }   
}

class MulOperator extends AbstractOperator{
    
    protected $priority = 1;
    protected $token = '*';
    protected $operands_count = 2;
    protected $associative = parent::ASSOCIATIVE_LEFT;
    
    protected function doExecute(array $operands){
        return $operands[0] * $operands[1];
    }   
}

class DivOperator extends AbstractOperator{
    
    protected $priority = 1;
    protected $token = '/';
    protected $operands_count = 2;
    protected $associative = parent::ASSOCIATIVE_LEFT;
    
    protected function doExecute(array $operands){
        if ($operands[1] == 0){
            throw new Exception('Division by zero');
        }
        return $operands[0] / $operands[1];
    }   
}

abstract class OperatorFactory{
    
    private static $operators = array(
        '+' => 'add',
        '-' => 'sub',
        '*' => 'mul',
        '/' => 'div',
        '^' => 'pow'
    );
    
    public static function getTokens()
    {
        return array_keys(self::$operators);
    }
    
    public static function getOperator($token)
    {
        if (!array_key_exists($token, self::$operators)){
            return $token;
        }
        
        $class = ucfirst(self::$operators[$token]) . 'Operator';
        if (!class_exists($class)){
            throw new Exception('Operator class "' . $class . '" not found.');
        }
        
        $operator = new $class();
        if (!($operator instanceof AbstractOperator)){
            throw new Exception('Operator class "' . $class . '" must be instance of AbstractOperator and instance of ' . get_class($operator) . ' given.');
        }
        
        return $operator;
    }
}

class Infix2Postfix{
    
    private $postfix = array();
    private $stack = array();

    public function process($infix){
        $infix = (string) $infix;
        
        $operators = OperatorFactory::getTokens();
        $operators = array_map('preg_quote', $operators);
        $operators ='(' . implode(')|(', $operators) . ')';
        $pattern = '#(\\d+(\.?\\d+|\\d*))|(\()|(\))|' . $operators . '#';
        $tokens = array();
        preg_match_all($pattern, $infix, $tokens);
        
        $tokens = array_map( array('OperatorFactory', 'getOperator'), $tokens[0]);
        
        foreach ($tokens as $token){
            if (is_numeric($token)){
                $this->postfix[] = $token;
            }
            elseif ($token == '('){
                array_unshift($this->stack, $token);
            }
            elseif ($token == ')'){
                $tmp = '';
                while ($tmp <> '('){
                    if (count($this->stack) == 0){
                        throw new Exception('Parse error.');
                    }
                    $tmp = array_shift($this->stack);
                    if ($tmp != '('){
                        $this->postfix[] = $tmp;
                    }
                }
            }
            elseif ($token instanceof AbstractOperator){
                while ($this->stack[0] instanceof AbstractOperator){
                    if ($token->comparePriority($this->stack[0]) == 1 && $this->stack[0]->getAssociative() == AbstractOperator::ASSOCIATIVE_LEFT){
                        break;
                    }
                    if ($token->comparePriority($this->stack[0]) >= 0 && $this->stack[0]->getAssociative() == AbstractOperator::ASSOCIATIVE_RIGHT){
                        break;
                    }
                    $this->postfix[] = array_shift($this->stack);
                }
                array_unshift($this->stack, $token);
            }
        }
        foreach ($this->stack as $token){
            if (!($token instanceof AbstractOperator)){
                throw new Exception('Parse error.');
            }
            $this->postfix[] = $token;
        }
        return $this->postfix;
    }
}

class ComputeInfix{
    
    public function compute($str)
    {
        $parser = new Infix2Postfix();
        $postfix = $parser->process($str);
        $stack = array();
        foreach ($postfix as $token){
            if (is_numeric($token)){
                array_unshift($stack, $token);
            }
            elseif ($token instanceof AbstractOperator){
                $params = array();
                for ($i = 1; $i <= $token->getOperandsCount(); $i++){
                    if (count($stack) == 0){
                        $params[] = 0;
                    }
                    else{
                        $params[] = array_shift($stack);
                    }
                }
                $result = $token->execute(array_reverse($params));
                array_unshift($stack, $result);
            }
        }
        $result = array_shift($stack);
        return $result;
    }
}

$t = new ComputeInfix();
print_r($t->compute('(22.43 - 45) + 2 ^ 3'));
?>