首页 » 工作 » 方法 » 正文

PHP根据数字的字符表达式计算出结果(转换成逆波兰式再求解)[转]

发布者:站点默认
2013/10/30 浏览数(1,600) 分类:方法 PHP根据数字的字符表达式计算出结果(转换成逆波兰式再求解)[转]已关闭评论

这个简单的计算器采用的是逆波兰式来做的,仅支持加减乘除四种运算,纯粹个人练习记录一下,还望多多支持。

用法

require 'Calc.php';
$calc = new Calc('(1+9)/2');
echo $result = $calc->calculate();

将算术表达式转换成逆波兰式

1、建立运算符栈stackOperator用于运算符的存储,压入’@’;建立逆波兰式存储栈stackOut,并置空。

2、预处理表达式,正、负号前加0(如果一个加号(减号)出现在最前面或左括号后面,则该加号(减号)为正负号) 。

3、顺序扫描表达式,如果当前字符是数字(优先级为0的符号),则直接入栈stackOut;如果当前字符为运算符或括号(优先级不为0的符号),则判断第4点 。

4、若当前运算符为'(‘,直接入栈stackOperator;
若为’)’,出栈(stackOperator)并顺序输出运算符直到遇到第一个'(‘,遇到的第一个'(‘ 出栈(stackOperator)但不输出;

若为四则运算符,比较栈顶元素与当前元素的优先级:

如果栈顶元素运算符优先级 >= 当前元素的优先级, 出栈并顺序输出运算符直到栈顶元素优先级<当前元素优先级,然后将当前元素入栈(stackOperator); 如果栈顶元素的优先级>当前元素的优先级,直接入栈(stackOperator)。

5、重复第3点直到表达式扫描完毕。

6、顺序出栈(stackOperator)并将输出的元素压入栈stackOut,直到栈顶元素为’@’。

计算逆波兰式

1、准备一个栈stack,并置空。

2、顺序读取(从栈底到栈顶)栈stackOut,碰到操作数,入栈stack。

3、碰到操作符,stack弹出两个元素,运算并将运算结果入栈stack。

4、重复执行2~3步骤,栈stack即是表达式结果。

实现代码

/**
 * php简单实现算术表达式转换成逆波兰式,并求解。
 * 仅支持加减乘除四种运算
 * @author joe, joenali@163.com
 * @date 2013-01-17
 * <pre>
 *  require 'Calc.php';
 *  $calc = new Calc('(1+9)/2');
 *  echo $calc->getExpression();
 *  echo $calc->calculate();
 * </pre>
 */
class Calc {

    protected $_stackOperator = array('@');
    protected $_stackOut = array();
    protected $_operator = array('@', '(', ')', '+', '-', '*', '/');
    protected $_priority = array('@' => 0, '(' => 10, ')' => 10, '+' => 20, '-' => 20, '*' => 30, '/' => 30);

    public function __construct($expression) {
        $this->convert($expression);
    }

    /**
     * 解析字符串表达式
     * 解析字符串表达式,将数字和运算符分离,用数组存储
     * @param string $expression
     * @return array
     */
    protected function expressionParase($expression) {
        $arr = str_split($expression);
        $data = $tmp = array();
        do {
            $item = array_shift($arr);
            if (in_array($item, $this->_operator)) {
                if ($tmp) {
                    array_push($data, implode('', $tmp));
                    $tmp = array();
                }
                array_push($data, $item);
            } else {
                array_push($tmp, $item);
            }

        } while(count($arr));
        array_push($data, implode('', $tmp));
        return $data;
    }

    /**
     * 生成逆波兰式
     * @param string $expression
     */
    protected function convert($expression) {
        foreach ($this->expressionParase($expression) as $char) {
            if (preg_match("/^[0-9]+$/", $char)) {
                array_push($this->_stackOut, $char);
            } else if (in_array($char, $this->_operator)) {
                if ('(' == $char) {
                    array_push($this->_stackOperator, $char);
                } else if (')' == $char) {
                    while (count($this->_stackOperator) > 1) {
                        $drop = array_pop($this->_stackOperator);
                        if ('(' == $drop) {
                            break;
                        } else {
                            array_push($this->_stackOut, $drop);
                        }
                    }
                } else {
                    while (count($this->_stackOperator)) {
                        $oTop = end($this->_stackOperator);
                        if ($this->_priority[$char] > $this->_priority[$oTop]) {
                            array_push($this->_stackOperator, $char);
                            break;
                        } else {
                           $drop = array_pop($this->_stackOperator);
                            array_push($this->_stackOut, $drop);
                        }
                    }
                }
            }
        }

        while (count($this->_stackOperator)) {
            $drop = array_pop($this->_stackOperator);
            if ('@' == $drop) {
                break;
            } else {
                array_push($this->_stackOut, $drop);
            }
        }
    }

    /**
     * 获取逆波兰式
     * @return string
     */
    public function getExpression() {
        return implode('', $this->_stackOut);
    }

    /**
     * 计算逆波兰式
     * @return int
     */
    public function calculate() {
        $stack = array();
        foreach ($this->_stackOut as $char) {
            if (preg_match("/^[0-9]+$/", $char)) {
                array_push($stack, $char);
            } else if (in_array($char, $this->_operator)) {
                $b = array_pop($stack);
                $a = array_pop($stack);

                array_push($stack, $this->operator($a, $b, $char));
            }
        }

        return end($stack);
    }

    protected function operator($a, $b, $o) {
        switch ($o) {
            case '+':
                return intval($a) + intval($b);
                break;
            case '+':
                return intval($a) + intval($b);
                break;
            case '-':
                return intval($a) - intval($b);
                break;
            case '*':
                return intval($a) * intval($b);
                break;
            case '/':
                return intval($a) / intval($b);
                break;
        }
    }
}

另一版:

<?php
$str = '1+1/2';
echo calc($str);
function calc($expression = ''){
	$_stackOperator = array('@');
	$_stackOut = array(); // 获取逆波兰式
	$_operator = array('@', '(', ')', '+', '-', '*', '/');
	$_priority = array('@' => 0, '(' => 10, ')' => 10, '+' => 20, '-' => 20, '*' => 30, '/' => 30);
	// 分离运算符和数字
	$arr = str_split($expression);
	$data = $tmp = array();
	do {
		$item = array_shift($arr);
		if (in_array($item, $_operator)) {
			if ($tmp) {
				 array_push($data, implode('', $tmp));
				 $tmp = array();
			}
			array_push($data, $item);
		} else {
			array_push($tmp, $item);
		}

	} while(count($arr));
	array_push($data, implode('', $tmp));
	// 生成逆波兰式
	foreach ($data as $char) {
		if (preg_match("/^[0-9]+$/", $char)) {
			array_push($_stackOut, $char);
		} else if (in_array($char, $_operator)) {
			if ('(' == $char) {
				 array_push($_stackOperator, $char);
			} else if (')' == $char) {
				 while (count($_stackOperator) > 1) {
						$drop = array_pop($_stackOperator);
						if ('(' == $drop) {
							break;
						} else {
							array_push($_stackOut, $drop);
						}
				 }
			} else {
				 while (count($_stackOperator)) {
						$oTop = end($_stackOperator);
						if ($_priority[$char] > $_priority[$oTop]) {
							array_push($_stackOperator, $char);
							break;
						} else {
							$drop = array_pop($_stackOperator);
							array_push($_stackOut, $drop);
						}
				 }
			}
		}
	}
	while (count($_stackOperator)) {
		$drop = array_pop($_stackOperator);
		if ('@' == $drop) {
			break;
		} else {
			array_push($_stackOut, $drop);
		}
	}
	// 计算逆波兰式
	$stack = array();
	foreach ($_stackOut as $char) {
		if (preg_match("/^[0-9]+$/", $char)) {
			array_push($stack, $char);
		} else if (in_array($char, $_operator)) {
			$b = array_pop($stack);
			$a = array_pop($stack);
			switch ($char) {
				case '+':
					array_push($stack, intval($a) + intval($b));
					break;
				case '+':
					array_push($stack, intval($a) + intval($b));
					break;
				case '-':
					array_push($stack, intval($a) - intval($b));
					break;
				case '*':
					array_push($stack, intval($a) * intval($b));
					break;
				case '/':
					array_push($stack, intval($a) / intval($b));
					break;
			}
		}
	}
	return end($stack);
}
?>

转自:http://my.oschina.net/u/566545/blog/103030

点击返回顶部
  1. 留言
  2. 联系方式