Chinaunix首页 | 论坛 | 博客
  • 博客访问: 885312
  • 博文数量: 91
  • 博客积分: 803
  • 博客等级: 准尉
  • 技术积分: 1051
  • 用 户 组: 普通用户
  • 注册时间: 2012-05-24 13:42
文章分类

全部博文(91)

文章存档

2021年(1)

2020年(4)

2019年(4)

2018年(9)

2017年(11)

2016年(11)

2015年(6)

2014年(3)

2013年(28)

2012年(14)

分类: PHP

2021-10-14 11:45:26

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

词法分析

点击(此处)折叠或打开

  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.                 }

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

  115.         }
  116.     }
  117.     return $token;
  118. }
生成后缀表达式

点击(此处)折叠或打开

  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.     ];


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

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

点击(此处)折叠或打开

  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));



阅读(366) | 评论(0) | 转发(0) |
0

上一篇:avl树的php实现

下一篇:没有了

给主人留下些什么吧!~~