PHP中缀表达式转后缀表达式

相关知识：一元运算符``二元运算符``中缀表达式``后缀表达式

先上测试代码:

$filter = "{is_game_vip}==1";

$data = [
    'is_game_vip' => 1,
    'age' => 18
];
$value   = Filter::exec($filter, $data);

var_dump($value); // 1

var_dump(Filter::exec("18>2")); // 1

var_dump(Filter::exec("1+2")); //3

var_dump(Filter::exec("(1+2)*2")); //6

var_dump(Filter::exec("{age} > 10")); //1

var_dump(Filter::exec("({a}+{b}+{c})*{d}-{f}*{m}", [
    'a' => 1,
    'b' => 2,
    'c' => 3,
    'd' => 6,
    'f' => 4,
    'm' => 5
]));//16

class Filter
{
    protected static $operate = [
        '(',
        ')',
        '+',
        '-',
        '*',
        '/',
        '==',
        '>=',
        '<=',
        '>',
        '<',
        '!',
        '&&',
        '||',
        'and',
        'or',
        '<<',
        '>>',
        '!=',
        '&',
        '^',
        '|',
    ];

    protected static $twoElementOperation = [
        '+',
        '-',
        '*',
        '/',
        '==',
        '>=',
        '<=',
        '>',
        '<',
        '&&',
        '||',
        'and',
        'or',
        '<<',
        '>>',
        '!=',
        '&',
        '^',
        '|',
    ];

    protected static $oneElementOperation = ['!'];

    public static function exec($filter, $data)
    {
        $infix   = self::stringToOperateArray($filter);
        $postfix = self::infixToPostfix($infix);
        $data  = is_array($data) ? $data : [];
        $value = self::calculation($postfix, $data);

        return $value;
    }

    /**
     * 将中缀表达式转换为后缀表达式
     * @param array $infixExpression
     */
    public static function infixToPostfix($infixExpression)
    {
        $stacks = [];
        $output = [];
        array_walk($infixExpression, function ($value) use (&$stacks, &$output) {
            if (!self::isOperate($value)) {
                $output[] = $value;
            } else {
                if (empty($stacks) || $value == '(' || self::compareOperate($value, end($stacks)) == 1) {
                    $stacks[] = $value;
                } else if ($value == ')') {
                    while (!empty($stacks) && ($last = array_pop($stacks)) != '(') {
                        $output[] = $last;
                    }
                } else if (self::compareOperate($value, end($stacks)) <= 0) {
                    while (!empty($stacks) && end($stacks) != '(') {
                        if (self::compareOperate(end($stacks), $value) > -1) {
                            $output[] = array_pop($stacks);
                        } else {
                            break;
                        }
                    }
                    $stacks[] = $value;
                }
            }
        });
        while (!empty($stacks)) {
            $end = array_pop($stacks);
            if ($end != '(' && $end != ')') {
                $output[] = $end;
            }
        }
        return $output;
    }


    public static function calculation($postfix, $data)
    {
        $stacks = [];
        array_walk($postfix, function ($value) use ($data, &$stacks) {
            if (self::isOperate($value)) {
                if (self::getOperateType($value) == 1) {
                    if (!empty($stacks)) {
                        $stacks[] = self::oneElementOperation(array_pop($stacks), $value);
                    }
                } else if (self::getOperateType($value) == 2 && count($stacks) >= 2) {
                    $two      = array_pop($stacks);
                    $one      = array_pop($stacks);
                    $stacks[] = self::twoElementOperateion($one, $two, $value);
                }
            } else {
                if (substr($value, 0, 1) == '{' && substr($value, -1, 1) == '}') {
                    $value    = substr($value, 1, -1);
                    $stacks[] = array_key_exists($value, $data) ? $data[$value] : 0;
                } else {
                    $stacks[] = $value;
                }
            }
        });
        return count($stacks) > 0 ? array_pop($stacks) : 0;
    }

    /**
     * 将字符串转换为中缀表达式
     * 采用过滤敏感词的算法
     * @param string $string
     */
    public static function stringToOperateArray($string)
    {
        $string = trim($string);
        $string = html_entity_decode($string);
        $len    = strlen($string);
        $return = [];

        $operateIndex = [];
        foreach (self::$operate as $value) {
            !isset($operateIndex[$value[0]]) && $operateIndex[$value[0]] = [];
            $operateIndex[$value[0]][] = $value;
        }


        $left = 0;
        $i    = 0;
        while ($i < $len) {
            if ($string[$i] == ' ') {
                if ($i > $left) {
                    $return[] = substr($string, $left, $i - $left);
                }
                $left = $i + 1;
            } else if (!empty($operateIndex[$string[$i]])) {
                $offset   = 0;
                $lenValue = 0;
                foreach ($operateIndex[$string[$i]] as $value) {
                    $lenValue = strlen($value);
                    if (substr($string, $i, $lenValue) == $value) {
                        $offset = $lenValue > $offset ? $lenValue : $offset;
                    }
                }
                if ($offset > 0 && ($string[$i] != '-' || ($left != $i))) {
                    $i > $left && $return[] = substr($string, $left, $i - $left);
                    $return[] = substr($string, $i, $offset);
                    $i        = $i + $offset - 1;
                    $left     = $i + 1;
                }
            }

            $i++;
        }
        if ($len > $left) {
            $return[] = substr($string, $left, $len - $left);
        }

        return $return;
    }

    protected static function isOperate($string)
    {
        if (in_array($string, self::$operate)) {
            return true;
        }
        return false;
    }

    protected static function isString($string)
    {
        if ($string != ' ' && !self::isOperate($string)) {
            return true;
        }
        return false;
    }

    /**
     * 获取操作符，1元还是2元
     */
    protected static function getOperateType($operate)
    {
        if (in_array($operate, self::$twoElementOperation)) {
            return 2;
        } else if (in_array($operate, self::$oneElementOperation)) {
            return 1;
        }
    }

    protected static function compareOperate($s1, $s2)
    {
        $weight = [
            ['*', '/', '%'],
            ['+', '-', '.'],
            ['<<', '>>'],
            ['<', '<=', '>', '>='],
            ['==', '!=', '===', '!==', '<>', '<=>'],
            ['&'],
            ['^'],
            ['|'],
            ['&&'],
            ['||'],
            ['and'],
            ['xor'],
            ['or']
        ];

        foreach ($weight as $value) {
            if (in_array($s1, $value)) {
                if (in_array($s2, $value)) {
                    return 0;
                } else {
                    return 1;
                }
            } else if (in_array($s2, $value)) {
                return -1;
            }
        }
        return 0;
    }

    protected static function twoElementOperateion($a, $b, $operate)
    {
        switch ($operate) {
            case '+' :
                return $a + $b;
                break;
            case '-' :
                return $a - $b;
                break;
            case '*' :
                return $a * $b;
                break;
            case '/' :
                return $a / $b;
                break;
            case '==' :
                return $a == $b ? 1 : 0;
                break;
            case '>=' :
                return $a >= $b ? 1 : 0;
                break;
            case '<=' :
                return $a <= $b ? 1 : 0;
                break;
            case '>' :
                return $a > $b ? 1 : 0;
                break;
            case '<' :
                return $a < $b ? 1 : 0;
                break;
            case '&&' :
                return $a && $b ? 1 : 0;
                break;
            case '||' :
                return $a || $b;
                break;
            case 'and' :
                return $a and $b;
                break;
            case 'or' :
                return $a or $b;
                break;
            case '<<' :
                return $a << $b;
                break;
            case '>>' :
                return $a >> $b;
                break;
            case '!=' :
                return $a != $b ? 1 : 0;
                break;
            case '&' :
                return $a & $b;
                break;
            case '^' :
                return $a ^ $b;
                break;
            case '|' :
                return $a | $b;
                break;
//            case 'xor':
//                return $a xor $b;
//                break;
            default :
                return 0;
        }

    }

    protected static function oneElementOperation($a, $operate)
    {
        switch ($operate) {
            case '!' :
                return !$a ? 1 : 0;
                break;
            default :
                return 0;
                break;
        }
    }
}