Fork me on GitHub

标签 栈 下的文章

PHP实现四则运算表达式求值(逆波兰表示法)

PHP实现四则运算表达式求值(逆波兰表示法)

中缀表达式:1+(3+(5*6)/4-2*8)
后缀表达式(逆波兰):1 3 5 6 * 4 / + 2 8 * - +

class Calculator
{
    public function execute($express)
    {
        //中缀表达式转后缀表达式
        $back = $this->midToBack($express);
        //计算后缀表达式
        return $this->calculateBack($back);
    }

    /**
     * 计算后缀表达式
     * 规则:
     * 从左到右遍历表达式的每个数字和符号,遇到数字就进栈,遇到符号就将栈顶两个数字出栈,进行运算,运算结果进栈,一直到最终获得结果
     *
     * @param $backExpress
     */
    private function calculateBack(array $backExpress)
    {
        $stack = [];
        foreach ($backExpress as $be){
            if(is_numeric($be)){
                $stack[] = $be;
            }else{
                $o2 = array_pop($stack);
                $o1 = array_pop($stack);
                switch ($be){
                    case '+':
                        $stack[] = $o1 + $o2;
                        break;
                    case '-':
                        $stack[] = $o1 - $o2;
                        break;
                    case '*':
                        $stack[] = $o1 * $o2;
                        break;
                    case '/':
                        $stack[] = (float)$o1 / (float)$o2;
                        break;
                    default:
                }
            }
        }
        return array_pop($stack);
    }

    /**
     * 规则:
     * 从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即成为后缀表达式的一部分。
     * 若是符号,则判断其与栈顶符号的优先级,是右括号则依次出栈直到左括号为止;或是栈顶符号高于等于当前符号优先级,则栈顶符号依次出栈直到
     * 栈顶符号优先级小于当前符号为止,然后将当前符号入栈;遍历结束后检查栈内是否还有元素,如果有则依次出栈成为后缀表达式的一部分。
     **/
    private function midToBack($midExpress)
    {
        $back = [];
        $symbol = [];
        preg_match_all('/\d+|[\+\-\*\/\(\)]/', $midExpress, $matches);
        if(empty($matches)){
            throw new \Exception('invalid express');
        }
        $expresses = $matches[0];
        foreach ($expresses as $exp) {
            if(is_numeric($exp)){
                $back[] = $exp;
            }else{
                if($exp==')'){
                    $count = count($symbol);
                    for($i=0;$i<$count;$i++){
                        $s = array_pop($symbol);
                        if($s=='('){
                            break;
                        }
                        $back[] = $s;
                    }
                }else{
                    $count = count($symbol);
                    for($i=0;$i<$count;$i++){
                        $top = $symbol[count($symbol)-1];
                        if($this->compareSymbol($exp,$top)<=0){
                            $s = array_pop($symbol);
                            $back[] = $s;
                        }else{
                            break;
                        }
                    }
                    $symbol[] = $exp;
                }

            }
        }
        if(!empty($symbol)){
            $count = count($symbol);
            for($i=0;$i<$count;$i++){
                $s = array_pop($symbol);
                $back[] = $s;
            }
        }
        return $back;
    }

    /**
     * 比较符号优先级
     **/
    private function compareSymbol($s1, $s2)
    {
        $symbol = ['+'=>1,'-'=>1,'*'=>2,'/'=>2];
        //如果输入为括号
        if(!isset($symbol[$s1])|| !isset($symbol[$s2])){
            return 1;
        }
        $v1 = $symbol[$s1];
        $v2 = $symbol[$s2];
        $res = 0;
        if($v1 > $v2){
            $res = 1;
        }elseif($v1<$v2){
            $res = -1;
        }
        return $res;
    }