字符串表达式求值

主要使用了中缀表达式转后缀表达式

词法分析

function lexer($str,$params) {
    $token = [];
    $len = strlen($str);
    $i = 0;
    while($i < $len) {
        switch ($str[$i]) {
            case '(' :
                $token[] = [
                    'type' => 'CLAUSE'
                ];
                $i += 1;
                break;
            case ')' :
                $token[] = [
                    'type' => 'CLAUSE_CLOSE'
                ];
                $i += 1;
                break;
            case '+' :
                $token[] = [
                    'type' => 'ADD',
                ];
                $i += 1;
                break;
            case '-' :
                $token[] = [
                    'type' => 'SUB',
                ];
                $i += 1;
                break;
            case '*' :
                $token[] = [
                    'type' => 'MUL',
                ];
                $i += 1;
                break;
            case '/' :
                $token[] = [
                    'type' => 'DIV',
                ];
                $i += 1;
                break;
            case '>':
                if( $str[$i+1] == '=') {
                    $token[] = [
                        'type' => 'GTE',
                    ];
                    $i += 2;
                } else {
                    $token[] = [
                        'type' => 'GT',
                    ];
                    $i += 1;
                }
                break;
            case '<':
                if( $str[$i+1] == '=') {
                    $token[] = [
                        'type' => 'LTE',
                    ];
                    $i += 2;
                } else {
                    $token[] = [
                        'type' => 'LT',
                    ];
                    $i += 1;
                }
                break;
            case '|':
                if( $str[$i+1] == '|') {
                    $token[] = [
                        'type' => 'OR',
                    ];
                    $i += 2;
                } else {
                    throw new Exception('未知类型');
                }
                break;
            case '&':
                if( $str[$i+1] == '&') {
                    $token[] = [
                        'type' => 'AND',
                    ];
                    $i += 2;
                } else {
                    throw new Exception('未知类型');
                }

                break;
            default :
                $asc = ord($str[$i]);
                if ($asc == 32) {
                    $i ++;
                    break;
                } elseif ($asc >= 97 && $asc <= 122) {
                    preg_match('#\w+#',substr($str,$i),$match);
                    $strLength = strlen($match[0]);
                    $token[] = [
                        'type' => 'NUMERIC_REPLACE',
                        'value' => $params[$match[0]]
                    ];
                    $i += $strLength;
                    break;
                } elseif ($asc >= 48 && $asc <= 57) {
                    preg_match('#\d+#',substr($str,$i),$match);
                    $numLength = strlen($match[0]);
                    $token[] = [
                        'type' => 'NUMERIC',
                        'value' => $match[0]
                    ];
                    $i += $numLength;
                    break;
                } else {
                    throw new Exception('未知类型');
                }

        }
    }
    return $token;
}

生成后缀表达式

function parse($token) {
    $levelMap = [
        'CLAUSE'=> 0,
        'CLAUSE_CLOSE' => 0,
        'MUL' => 1,
        'DIV' => 1,
        'ADD' => 2,
        'SUB' => 2,
        'GTE' => 3,
        'GT' => 3,
        'LTE' => 3,
        'LT' => 3,
        'AND' => 4,
        'OR' => 4
    ];


    $len = count($token);
    $i = 0;
    $parses = [];
    $stack = new SplStack();
    while($i < $len) {
        switch ($token[$i]['type']) {
            case 'NUMERIC':
            case 'NUMERIC_REPLACE':
                $parses[] = is_integer($token[$i]['value']) ? (int)$token[$i]['value'] : (float)$token[$i]['value'];
                break;
            case 'CLAUSE':
                $stack->push('CLAUSE');
                break;
            case 'CLAUSE_CLOSE':
                //取出 操作符
                while(!$stack->isEmpty()) {
                    if($stack->top() == 'CLAUSE') {
                        $stack->pop();
                        break;
                    } else {
                        $parses[] = $stack->pop();
                    }
                }
                break;
            case 'MUL':
            case 'DIV':
            case 'ADD':
            case 'SUB':
            case 'GTE':
            case 'GT':
            case 'LTE':
            case 'LT':
            case 'AND':
            case 'OR':
                if($stack->isEmpty() || $levelMap[$token[$i]['type']] < $levelMap[$stack->top()]) {
                    $stack->push($token[$i]['type']);
                } else {
                    while(!$stack->isEmpty() && $levelMap[$token[$i]['type']] >= $levelMap[$stack->top()]) {
                        if($stack->top() == 'CLAUSE') {
                            break;
                        }
                        $op = $stack->pop();
                        $parses[] = $op;
                    }
                    $stack->push($token[$i]['type']);
                }

                break;
        }
        $i ++;
    }
    //处理最后一个操作符
    if(!$stack->isEmpty()) {
        $op = $stack->pop();
        $parses[] = $op;
    }
    return $parses;
}

后缀表达式求值

function evalExpression($parses) {
    $stack = new SplStack();
    $len = count($parses);
    $i = 0;
    while($i < $len) {
        if(is_numeric($parses[$i])) {
            $stack->push($parses[$i]);
        } else {
            $op2 = $stack->pop(); //后操作数, 比较运算符(> >= < <=)关注顺序 (+ x)不关注操作符顺序
            $op1 = $stack->pop();
            switch ($parses[$i]) {
                case 'MUL':
                    $stack->push($op1 * $op2);
                    break;
                case 'DIV':
                    $stack->push($op1 / $op2);
                    break;
                case 'ADD':
                    $stack->push($op1 + $op2);
                    break;
                case 'SUB':
                    $stack->push($op1 - $op2);
                    break;
                case 'GTE':
                    $stack->push($op1 >= $op2 ? 1 : 0);
                    break;
                case 'GT':
                    $stack->push($op1 > $op2 ? 1 : 0);
                    break;
                case 'LTE':
                    $stack->push($op1 <= $op2 ? 1 : 0);
                    break;
                case 'LT':
                    $stack->push($op1 < $op2 ? 1 : 0);
                    break;
                case 'AND':
                    $stack->push($op1 && $op2 ? 1 : 0);
                    break;
                case 'OR':
                    $stack->push($op1 || $op2 ? 1 : 0);
                    break;
            }
        }
        $i ++;
    }
    return $stack->pop();
}

测试代码

$str = " bid * (100 + 2) > 40 || (0+0)";
$params['bid'] = 0.2;
$tokens = lexer($str,$params);
$parses = parse($tokens);
print_r(evalExpression($parses));