字符串表达式求值

480阅读　0评论2021-10-14　nuoyazhou110
分类：PHP

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

词法分析

点击(此处)折叠或打开

  1. function lexer($str,$params) {
  2.     $token = [];
  3.     $len = strlen($str);
  4.     $i = 0;
  5.     while($i < $len) {
  6.         switch ($str[$i]) {
  7.             case '(' :
  8.                 $token[] = [
  9.                     'type' => 'CLAUSE'
  10.                 ];
  11.                 $i += 1;
  12.                 break;
  13.             case ')' :
  14.                 $token[] = [
  15.                     'type' => 'CLAUSE_CLOSE'
  16.                 ];
  17.                 $i += 1;
  18.                 break;
  19.             case '+' :
  20.                 $token[] = [
  21.                     'type' => 'ADD',
  22.                 ];
  23.                 $i += 1;
  24.                 break;
  25.             case '-' :
  26.                 $token[] = [
  27.                     'type' => 'SUB',
  28.                 ];
  29.                 $i += 1;
  30.                 break;
  31.             case '*' :
  32.                 $token[] = [
  33.                     'type' => 'MUL',
  34.                 ];
  35.                 $i += 1;
  36.                 break;
  37.             case '/' :
  38.                 $token[] = [
  39.                     'type' => 'DIV',
  40.                 ];
  41.                 $i += 1;
  42.                 break;
  43.             case '>':
  44.                 if( $str[$i+1] == '=') {
  45.                     $token[] = [
  46.                         'type' => 'GTE',
  47.                     ];
  48.                     $i += 2;
  49.                 } else {
  50.                     $token[] = [
  51.                         'type' => 'GT',
  52.                     ];
  53.                     $i += 1;
  54.                 }
  55.                 break;
  56.             case '<':
  57.                 if( $str[$i+1] == '=') {
  58.                     $token[] = [
  59.                         'type' => 'LTE',
  60.                     ];
  61.                     $i += 2;
  62.                 } else {
  63.                     $token[] = [
  64.                         'type' => 'LT',
  65.                     ];
  66.                     $i += 1;
  67.                 }
  68.                 break;
  69.             case '|':
  70.                 if( $str[$i+1] == '|') {
  71.                     $token[] = [
  72.                         'type' => 'OR',
  73.                     ];
  74.                     $i += 2;
  75.                 } else {
  76.                     throw new Exception('未知类型');
  77.                 }
  78.                 break;
  79.             case '&':
  80.                 if( $str[$i+1] == '&') {
  81.                     $token[] = [
  82.                         'type' => 'AND',
  83.                     ];
  84.                     $i += 2;
  85.                 } else {
  86.                     throw new Exception('未知类型');
  87.                 }

  89.                 break;
  90.             default :
  91.                 $asc = ord($str[$i]);
  92.                 if ($asc == 32) {
  93.                     $i ++;
  94.                     break;
  95.                 } elseif ($asc >= 97 && $asc <= 122) {
  96.                     preg_match('#\w+#',substr($str,$i),$match);
  97.                     $strLength = strlen($match[0]);
  98.                     $token[] = [
  99.                         'type' => 'NUMERIC_REPLACE',
  100.                         'value' => $params[$match[0]]
  101.                     ];
  102.                     $i += $strLength;
  103.                     break;
  104.                 } elseif ($asc >= 48 && $asc <= 57) {
  105.                     preg_match('#\d+#',substr($str,$i),$match);
  106.                     $numLength = strlen($match[0]);
  107.                     $token[] = [
  108.                         'type' => 'NUMERIC',
  109.                         'value' => $match[0]
  110.                     ];
  111.                     $i += $numLength;
  112.                     break;
  113.                 } else {
  114.                     throw new Exception('未知类型');
  115.                 }

  117.         }
  118.     }
  119.     return $token;
  120. }
生成后缀表达式

点击(此处)折叠或打开

  1. function parse($token) {
  2.     $levelMap = [
  3.         'CLAUSE'=> 0,
  4.         'CLAUSE_CLOSE' => 0,
  5.         'MUL' => 1,
  6.         'DIV' => 1,
  7.         'ADD' => 2,
  8.         'SUB' => 2,
  9.         'GTE' => 3,
  10.         'GT' => 3,
  11.         'LTE' => 3,
  12.         'LT' => 3,
  13.         'AND' => 4,
  14.         'OR' => 4
  15.     ];


  18.     $len = count($token);
  19.     $i = 0;
  20.     $parses = [];
  21.     $stack = new SplStack();
  22.     while($i < $len) {
  23.         switch ($token[$i]['type']) {
  24.             case 'NUMERIC':
  25.             case 'NUMERIC_REPLACE':
  26.                 $parses[] = is_integer($token[$i]['value']) ? (int)$token[$i]['value'] : (float)$token[$i]['value'];
  27.                 break;
  28.             case 'CLAUSE':
  29.                 $stack->push('CLAUSE');
  30.                 break;
  31.             case 'CLAUSE_CLOSE':
  32.                 //取出 操作符
  33.                 while(!$stack->isEmpty()) {
  34.                     if($stack->top() == 'CLAUSE') {
  35.                         $stack->pop();
  36.                         break;
  37.                     } else {
  38.                         $parses[] = $stack->pop();
  39.                     }
  40.                 }
  41.                 break;
  42.             case 'MUL':
  43.             case 'DIV':
  44.             case 'ADD':
  45.             case 'SUB':
  46.             case 'GTE':
  47.             case 'GT':
  48.             case 'LTE':
  49.             case 'LT':
  50.             case 'AND':
  51.             case 'OR':
  52.                 if($stack->isEmpty() || $levelMap[$token[$i]['type']] < $levelMap[$stack->top()]) {
  53.                     $stack->push($token[$i]['type']);
  54.                 } else {
  55.                     while(!$stack->isEmpty() && $levelMap[$token[$i]['type']] >= $levelMap[$stack->top()]) {
  56.                         if($stack->top() == 'CLAUSE') {
  57.                             break;
  58.                         }
  59.                         $op = $stack->pop();
  60.                         $parses[] = $op;
  61.                     }
  62.                     $stack->push($token[$i]['type']);
  63.                 }

  65.                 break;
  66.         }
  67.         $i ++;
  68.     }
  69.     //处理最后一个操作符
  70.     if(!$stack->isEmpty()) {
  71.         $op = $stack->pop();
  72.         $parses[] = $op;
  73.     }
  74.     return $parses;
  75. }
后缀表达式求值

点击(此处)折叠或打开

  1. function evalExpression($parses) {
  2.     $stack = new SplStack();
  3.     $len = count($parses);
  4.     $i = 0;
  5.     while($i < $len) {
  6.         if(is_numeric($parses[$i])) {
  7.             $stack->push($parses[$i]);
  8.         } else {
  9.             $op2 = $stack->pop(); //后操作数, 比较运算符(> >= < <=)关注顺序 (+ x)不关注操作符顺序
  10.             $op1 = $stack->pop();
  11.             switch ($parses[$i]) {
  12.                 case 'MUL':
  13.                     $stack->push($op1 * $op2);
  14.                     break;
  15.                 case 'DIV':
  16.                     $stack->push($op1 / $op2);
  17.                     break;
  18.                 case 'ADD':
  19.                     $stack->push($op1 + $op2);
  20.                     break;
  21.                 case 'SUB':
  22.                     $stack->push($op1 - $op2);
  23.                     break;
  24.                 case 'GTE':
  25.                     $stack->push($op1 >= $op2 ? 1 : 0);
  26.                     break;
  27.                 case 'GT':
  28.                     $stack->push($op1 > $op2 ? 1 : 0);
  29.                     break;
  30.                 case 'LTE':
  31.                     $stack->push($op1 <= $op2 ? 1 : 0);
  32.                     break;
  33.                 case 'LT':
  34.                     $stack->push($op1 < $op2 ? 1 : 0);
  35.                     break;
  36.                 case 'AND':
  37.                     $stack->push($op1 && $op2 ? 1 : 0);
  38.                     break;
  39.                 case 'OR':
  40.                     $stack->push($op1 || $op2 ? 1 : 0);
  41.                     break;
  42.             }
  43.         }
  44.         $i ++;
  45.     }
  46.     return $stack->pop();
  47. }

测试代码

点击(此处)折叠或打开

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



上一篇：avl树的php实现
下一篇：没有了