<?php

function isPossible($toCheck){
	$toCheck=substr($toCheck, 1, -1);
	$pars = 0;
	for($i=0; $i<strlen($toCheck); $i++){
		if($toCheck[$i]=="(") $pars++;
		if($toCheck[$i]==")") $pars--;
		if($pars<0) return false;
	}
	return true;
}

function trimpars($toTrim){
	$len = strlen($toTrim);
	if($toTrim[0]=="(" && $toTrim[$len-1]==")"){
		if(isPossible($toTrim)) $toTrim = substr($toTrim, 1, -1);
	}
	return $toTrim;
}

class TreeCalc {
	public $left;
	public $right;
	private $value;
	private $leaf;
	
	public function __construct(){
		$this->left = null;
		$this->right = null;
		$this->value = null;
		$this->leaf = false;				
	}
	
	public function isLeaf(){
		return $this->leaf;
	}
	
	public function getValue(){
		return $this->value;
	}
	
	private function tokenize($inputString){
		$pars = 0;
		$weight = -1;				
		$tok = -1;
		$op = "";
		for($i=0; $i<strlen($inputString); $i++){
			switch($inputString[$i]){
				case "(" : 
					$pars++;
					break;
				case ")" : 
					$pars--;
					break;
				case "+": 
					if($pars>0) break;
					if($weight < 10){
						$tok = $i;
						$op = "+";
						$weight = 10;
					}
					break;
				case "-":
					if($pars>0) break;
					if($weight < 10){
						$tok = $i;
						$op = "-";
						$weight = 10;
					}
					break;
				case "*":
					if($pars>0) break;
					if($weight < 5){
						$tok = $i;
						$op = "*";
						$weight = 5;
					}
					break;
				case "/":
					if($pars>0) break;
					if($weight < 5){
						$tok = $i;
						$op = "/";
						$weight = 5;
					}
					break;
				case "^":
					if($pars>0) break;
					if($weight < 1){
						$tok = $i;
						$op = "^";
						$weight = 1;
					}
					break;
			}
		}
		if($weight==-1){
			$this->leaf = true;
			$this->value = $inputString;
			return;
		}
		$this->value=$op;
		$leftString = substr($inputString, 0, $tok);
		$leftString = trim($leftString);
		$leftString = trimpars($leftString);
		
		$rightString = substr($inputString, $tok+1);
		$rightString = trim($rightString);
		$rightString = trimpars($rightString);
		
		$this->left = new TreeCalc();
		$this->left->tokenize($leftString);
		$this->right = new TreeCalc();
		$this->right->tokenize($rightString);
	}
	
	public function debugPrint(){
		echo $this->value;
		if($this->left != null) $this->left->debugPrint();
		if($this->right != null) $this->right->debugPrint();
	}
	
	private function compute(){
		if($this->isLeaf()) return;
		if($this->left->isLeaf()==false){
			$this->left->compute();
		}
		if($this->right->isLeaf()==false){
			$this->right->compute();
		}
		switch($this->value){
			case "+":
				$this->value = $this->left->getValue() + $this->right->getvalue();
				break;
			case "-":
				$this->value = $this->left->getValue() - $this->right->getValue();
				break;
			case "*":
				$this->value = $this->left->getValue() * $this->right->getValue();
				break;
			case "/":
				$this->value = $this->left->getValue() / $this->right->getValue();
				break;
			case "^":
				$this->value = pow($this->left->getValue(), $this->right->getValue());
				break;
		}
		$this->leaf = true;
		$this->left = null;
		$this->right = null;
	}
	
	public function calculate($toCalc){
		$this->tokenize($toCalc);
		$this->compute();
		return $this->getValue();
	}
}


$test = new TreeCalc();
echo $test->calculate("3*2^(2+3)+((2+2)*2)-1");