fork(76) download
  1. <?php
  2. abstract class AbstractOperator{
  3.  
  4. const ASSOCIATIVE_LEFT = 0;
  5. const ASSOCIATIVE_RIGHT = 1;
  6.  
  7. private $associative_map = array(
  8. self::ASSOCIATIVE_LEFT,
  9. self::ASSOCIATIVE_RIGHT
  10. );
  11.  
  12. protected $priority = null;
  13. protected $token = null;
  14. protected $operands_count = null;
  15. protected $associative = null;
  16.  
  17. final public function __construct()
  18. {
  19.  
  20. }
  21.  
  22. abstract protected function doExecute(array $operands);
  23.  
  24. public function execute(array $operands)
  25. {
  26. if (count($operands) != $this->getOperandsCount()){
  27. throw new Exception('Operands count must be equal ' . $this->getOperandsCount());
  28. }
  29. $operands = array_values($operands);
  30. return $this->doExecute($operands);
  31. }
  32.  
  33. public function getAssociative()
  34. {
  35. if (is_null($this->associative)){
  36. throw new Exception('Associative is empty');
  37. }
  38. if (!in_array($this->associative, $this->associative_map)){
  39. throw new Exception('Invalid associative value');
  40. }
  41. return $this->associative;
  42. }
  43.  
  44. public function getOperandsCount()
  45. {
  46. if (is_null($this->operands_count)){
  47. throw new Exception('Operands count is empty');
  48. }
  49. return $this->operands_count;
  50. }
  51.  
  52. public function comparePriority(AbstractOperator $operator){
  53. if (is_null($this->priority)){
  54. throw new Exception('Priority is empty');
  55. }
  56. $num = $this->priority - $operator->priority;
  57. return ($num > 0) ? 1 : (($num < 0) ? -1 : 0);
  58. }
  59.  
  60. public function __toString()
  61. {
  62. if (is_null($this->token)){
  63. throw new Exception('Token is empty');
  64. }
  65. return $this->token;
  66. }
  67. }
  68.  
  69. class PowOperator extends AbstractOperator{
  70.  
  71. protected $priority = 2;
  72. protected $token = '^';
  73. protected $operands_count = 2;
  74. protected $associative = parent::ASSOCIATIVE_RIGHT;
  75.  
  76. protected function doExecute(array $operands){
  77. return pow($operands[0], $operands[1]);
  78. }
  79.  
  80. }
  81.  
  82. class AddOperator extends AbstractOperator{
  83.  
  84. protected $priority = 0;
  85. protected $token = '+';
  86. protected $operands_count = 2;
  87. protected $associative = parent::ASSOCIATIVE_LEFT;
  88.  
  89. protected function doExecute(array $operands){
  90. return $operands[0] + $operands[1];
  91. }
  92.  
  93. }
  94.  
  95. class SubOperator extends AbstractOperator{
  96.  
  97. protected $priority = 0;
  98. protected $token = '-';
  99. protected $operands_count = 2;
  100. protected $associative = parent::ASSOCIATIVE_LEFT;
  101.  
  102. protected function doExecute(array $operands){
  103. return $operands[0] - $operands[1];
  104. }
  105. }
  106.  
  107. class MulOperator extends AbstractOperator{
  108.  
  109. protected $priority = 1;
  110. protected $token = '*';
  111. protected $operands_count = 2;
  112. protected $associative = parent::ASSOCIATIVE_LEFT;
  113.  
  114. protected function doExecute(array $operands){
  115. return $operands[0] * $operands[1];
  116. }
  117. }
  118.  
  119. class DivOperator extends AbstractOperator{
  120.  
  121. protected $priority = 1;
  122. protected $token = '/';
  123. protected $operands_count = 2;
  124. protected $associative = parent::ASSOCIATIVE_LEFT;
  125.  
  126. protected function doExecute(array $operands){
  127. if ($operands[1] == 0){
  128. throw new Exception('Division by zero');
  129. }
  130. return $operands[0] / $operands[1];
  131. }
  132. }
  133.  
  134. abstract class OperatorFactory{
  135.  
  136. private static $operators = array(
  137. '+' => 'add',
  138. '-' => 'sub',
  139. '*' => 'mul',
  140. '/' => 'div',
  141. '^' => 'pow'
  142. );
  143.  
  144. public static function getTokens()
  145. {
  146. return array_keys(self::$operators);
  147. }
  148.  
  149. public static function getOperator($token)
  150. {
  151. if (!array_key_exists($token, self::$operators)){
  152. return $token;
  153. }
  154.  
  155. $class = ucfirst(self::$operators[$token]) . 'Operator';
  156. if (!class_exists($class)){
  157. throw new Exception('Operator class "' . $class . '" not found.');
  158. }
  159.  
  160. $operator = new $class();
  161. if (!($operator instanceof AbstractOperator)){
  162. throw new Exception('Operator class "' . $class . '" must be instance of AbstractOperator and instance of ' . get_class($operator) . ' given.');
  163. }
  164.  
  165. return $operator;
  166. }
  167. }
  168.  
  169. class Infix2Postfix{
  170.  
  171. private $postfix = array();
  172. private $stack = array();
  173.  
  174. public function process($infix){
  175. $infix = (string) $infix;
  176.  
  177. $operators = OperatorFactory::getTokens();
  178. $operators = array_map('preg_quote', $operators);
  179. $operators ='(' . implode(')|(', $operators) . ')';
  180. $pattern = '#(\\d+(\.?\\d+|\\d*))|(\()|(\))|' . $operators . '#';
  181. $tokens = array();
  182. preg_match_all($pattern, $infix, $tokens);
  183.  
  184. $tokens = array_map( array('OperatorFactory', 'getOperator'), $tokens[0]);
  185.  
  186. foreach ($tokens as $token){
  187. if (is_numeric($token)){
  188. $this->postfix[] = $token;
  189. }
  190. elseif ($token == '('){
  191. array_unshift($this->stack, $token);
  192. }
  193. elseif ($token == ')'){
  194. $tmp = '';
  195. while ($tmp <> '('){
  196. if (count($this->stack) == 0){
  197. throw new Exception('Parse error.');
  198. }
  199. $tmp = array_shift($this->stack);
  200. if ($tmp != '('){
  201. $this->postfix[] = $tmp;
  202. }
  203. }
  204. }
  205. elseif ($token instanceof AbstractOperator){
  206. while ($this->stack[0] instanceof AbstractOperator){
  207. if ($token->comparePriority($this->stack[0]) == 1 && $this->stack[0]->getAssociative() == AbstractOperator::ASSOCIATIVE_LEFT){
  208. break;
  209. }
  210. if ($token->comparePriority($this->stack[0]) >= 0 && $this->stack[0]->getAssociative() == AbstractOperator::ASSOCIATIVE_RIGHT){
  211. break;
  212. }
  213. $this->postfix[] = array_shift($this->stack);
  214. }
  215. array_unshift($this->stack, $token);
  216. }
  217. }
  218. foreach ($this->stack as $token){
  219. if (!($token instanceof AbstractOperator)){
  220. throw new Exception('Parse error.');
  221. }
  222. $this->postfix[] = $token;
  223. }
  224. return $this->postfix;
  225. }
  226. }
  227.  
  228. class ComputeInfix{
  229.  
  230. public function compute($str)
  231. {
  232. $parser = new Infix2Postfix();
  233. $postfix = $parser->process($str);
  234. $stack = array();
  235. foreach ($postfix as $token){
  236. if (is_numeric($token)){
  237. array_unshift($stack, $token);
  238. }
  239. elseif ($token instanceof AbstractOperator){
  240. $params = array();
  241. for ($i = 1; $i <= $token->getOperandsCount(); $i++){
  242. if (count($stack) == 0){
  243. $params[] = 0;
  244. }
  245. else{
  246. $params[] = array_shift($stack);
  247. }
  248. }
  249. $result = $token->execute(array_reverse($params));
  250. array_unshift($stack, $result);
  251. }
  252. }
  253. $result = array_shift($stack);
  254. return $result;
  255. }
  256. }
  257.  
  258. $t = new ComputeInfix();
  259. print_r($t->compute('(22.43 - 45) + 2 ^ 3'));
  260. ?>
Success #stdin #stdout 0.02s 13112KB
stdin
Standard input is empty
stdout
-14.57