• 热门专题

PHP计算后序表达式(逆波兰式)

作者:leo108's   发布日期:2013-03-12 15:20:59
Tag标签:PHP  表达式  逆波兰式  
  • 百度谷歌搜索无果,之好自己造一次轮子。

    function rpn2value($str){
        $arr = explode(',',$str);
        $stack = array();
        $len = count($arr);
        for($i=0;$i<$len;$i++){
            if(is_numeric($arr[$i])){
                array_push($stack,$arr[$i]);
            }else{
                $op = $arr[$i];
                $right = array_pop($stack);
                $left = array_pop($stack);
                eval("\$re = $left $op $right;");
                array_push($stack,$re);
            }   
        }
        return $stack[0];
    }

    使用方法:

     

    $str = "1,2,3,+,*,4,-,5,+,7,*";
    echo rpn2value($str);

    另附中序转后序代码,版权归原作者所有


    /**
     * math_rpn
     *
     * 实现逆波兰式算法
     *
     * @author   sparkHuang 260558820@qq.com
     * @version  RPN 1.0.0
     *
     */
    class math_rpn {
        //初始的计算表达式
        private $_expression = '';
        //处理后的逆波兰表达式
        private $_rpnexp = array();
        //模拟栈结构的数组 www.it165.net
        private $_stack  = array('#');
        //正则判断
        //private $_reg    = '/^([A-Za-z0-9\(\)\+\-\*\/])*$/';
        //优先级
        private $_priority = array('#' => 0, '(' => 10, '+' => 20, '-' => 20, '*' => 30, '/' => 30);
        //四则运算
        private $_operator = array('(', '+', '-', '*', '/', ')');
        public function __construct($expression) {
            $this->_init($expression);
        }
        private function _init($expression) {
            $this->_expression = $expression;
        }
        public function exp2rpn() {
            $len = strlen($this->_expression);
            for($i = 0; $i < $len; $i++) {
                $char = substr($this->_expression, $i, 1);
                if ($char == '(') {
                    $this->_stack[] = $char;
                    continue;
                } else if ( ! in_array($char, $this->_operator)) {
                    $this->_rpnexp[] = $char;
                    continue;
                } else if ($char == ')') {
                    for($j = count($this->_stack); $j >= 0; $j--) {
                        $tmp = array_pop($this->_stack);
                        if ($tmp == "(") {
                            break;
                        } else {
                            $this->_rpnexp[] = $tmp;
                        }
                    }
                    continue;
                } else if ($this->_priority[$char] <= $this->_priority[end($this->_stack)]) {
                    $this->_rpnexp[] = array_pop($this->_stack);
                    $this->_stack[]  = $char;
                    continue;
                } else {
                    $this->_stack[] = $char;
                    continue;
                }
            }
            for($i = count($this->_stack); $i >= 0; $i--) {
                if (end($this->_stack) == '#') break;
                $this->_rpnexp[] = array_pop($this->_stack);
            }
            return $this->_rpnexp;
        }
    }
    //测试实例
    $expression = "(A*(B+C)-E+F)*G";
    var_dump($expression);
    $mathrpn = new math_rpn($expression);
    var_dump($mathrpn->exp2rpn());

     

About IT165 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规