简体中文（ZH-CN）English（EN）繁体中文（ZH-TW）日本語（JA）한국어（KO）Melayu（MS）Français（FR）Deutsch（DE）
首頁
文章
問答
課程
專題
下載
遊戲
詞典
最近更新

首頁  >  文章  >  Java  >  實例介紹基於Java實作一個複雜關係表達式過濾器

實例介紹基於Java實作一個複雜關係表達式過濾器

WBOY
WBOY轉載
2022-08-01 14:56:321548瀏覽

本篇文章為大家帶來了關於java的相關知識，主要為大家詳細介紹如何基於Java實作一個複雜關係表達式過濾器。文中的範例程式碼講解詳細，下面一起來看一下，希望對大家有幫助。

實例介紹基於Java實作一個複雜關係表達式過濾器

推薦學習：《java影片教學》

背景

最近，有一個新需求，需要後台設定一個複雜的關係表達式，根據使用者指定ID，解析該用使用者是否滿足該條件，後台設定類似於禪道的搜尋條件

但是不同的是禪道有且僅有兩個組，每個組最多三個條件

而我們這邊組與關係可能是更複雜的，組中有組，每個條件都是有且或關係的。由於保密原因，原型就不發出來了。

看到這個需求，作為一個後端，第一時間想到的是類似QLEpress這類的表達式框架，只要建立一個表達式，透過解析表達式即可快速對目標使用者進行篩選，但可惜的是前端同學不乾了，因為作為使用vue或react這類資料驅動的框架來說，將表達式轉換為為上述的一個表單太難了，所以想了一下，決定自己定義一個資料結構，實作表達式解析。方便前端同學的處理。

分析準備

雖然是用類別實現表達式，但是其本質上依舊還是個表達式，我們列舉一個簡單的表達式：設條件為a,b,c,d ，我們隨意建構一個表達式：

boolean result=a>100 && b=10 || (c != 3 && d b0473336a61b320b645e61902285f25e100 中的100）。

另外，還有關聯關係（且、或）和計算優先級這幾個屬性組成。

於是我們將表達式簡化：

令a>100 =>A,b=10 =>B,c!=3=>C ,d1f95226a8acdafab5dc28f716ab5c5e4D,於是我們得到：

result=A && B || (C && D)

現在問題來了，如何處理優先順序呢？

如上表達式，很明顯，這是一個大學裡學過的標準的中序表達式，於是，我們畫一下它的樹形圖：

根據這個圖，我們可以明顯的看到，A且B 和C且D是同一級別，於是，我們按照這個理論設計一個層級的概念Deep，我們標註一下，然後再對節點的類型做一下區分，可得：

我們可以看到作為葉子節點（上圖綠色部分），相對於其計算計算關係，遇到了一定是優先計算的，所以對於深度的優先級，我們只需要考慮非葉子節點即可，也就是上圖中的藍色節點部分，於是我們得到了，計算優先級這個概念我們可以轉換為表達式的深度。

我們再看上面這個圖，Deep1 的關係是Deep2中A且B 和C且D兩個表達式計算出的結果再進行與或關係的，我們設A 且B 為G1， C且D為G2，於是我們發現關係節點關聯的型別有兩種類型，一種是條件Condition ，一種是群組Group

至此，這個類別的雛形基本上就確定了。這個類別包含關聯關係（Relation）、判斷欄位（Field）、運算子（Operator）、運算值（Values）、類型（Type）、深度（Deep）

但是，有個問題，上面的分析中，我們在將表達式轉換成樹，現在我們試著將其還原，於是我們一眼可以得到其中一個表達式：

result=(A && B)||(C && D)

很顯然，和我們的原來的表達式並不一致，這是因為我們上述僅能記錄表達式的計算順序，而不能完全準確的表示這個表達式，這是因為在我們解析表達式的過程中，不僅是有深度、還有一個時序關係，即從左到右的順序表示，而此時G1中的內容實際上在原表達式中的深度應該是1而不是2，然後我們引入序號的概念，將原來樹變成有向的圖即：

根據這個圖，我們就還原出有且唯一的一個表達式了：result= A && B ||(C && D)。

好了，我們分析了半天，原理說完了，回到最初始的問題：前後端怎麼實現？對著上圖想像一下，似乎還是無法處理，因為這個結構還是太複雜了。對於前端，資料最好是方便遍歷的，對於後端，資料最好是方便處理的，所以這時候我們需要將上面這個圖轉換成一個陣列。

實作方式

上面說到了需要一個陣列的結構，我們具體分析一下這個部分

##我們發現作為葉子節點，可以始終優先計算，所以我們可以將其壓縮，並將關係放置在其中一個表達式中形成

^A -> &&B或A&& -> B$ 的形式，這裡我用正則的開始(^) 和結束($) 表示了一下開始和結束的概念,這裡為了與產品原型保持一致我們用第一種方式，即關係符號表示與前一個元素的關係，於是我們再分析一下：

再將序號進行改造：

於是我們得到最終的資料結構：

 @Data
 @AllArgsConstructor
 @NoArgsConstructor
 @Accessors(chain = true)
 public class ExpressDto {
     /**
      * 序号
      */
     private Integer seq;
     /**
      * 深度（运算优先级）
      */
     private Integer deep;
     /**
      * 关系运算符
      */
     private String relation;
     /**
      * 类型
      */
     private String type;
     /**
      * 运算条件
      */
     private String field;
     /**
      * 逻辑运算符
      */
     private String operator;
     /**
      * 运算值
      */
     private String values;
     /**
      * 运算结果
      */
     private Boolean result;
 }

現在資料結構終於完成，既方便存儲，又（相對）方便前台展示，現在構造一個稍微複雜的表達式

A &&(( B || C )|| (D && E)) && F

換成數組對象，開始以BEGIN標識，表達式類型以CONDITION表示，群組以GROUP表示。 

 [
 {"seq":1,"deep":1,relation:"BEGIN","type":"CONDITION","field"="A"...},
 {"seq":2,"deep":1,relation:"AND","type":"GROUP","field":""...},
 {"seq":3,"deep":2,relation:"BEGIN","type":"GROUP","field":""...},
 {"seq":4,"deep":3,relation:"BEGIN","type":"CONDITION","field":"B"...},
 {"seq":5,"deep":3,relation:"OR","type":"CONDITION","field":"C"...},
 {"seq":6,"deep":2,relation:"OR","type":"GROUP","field":""...},
 {"seq":7,"deep":3,relation:"BEGIN","type":"CONDITION","field":"D"...},
 {"seq":8,"deep":3,relation:"AND","type":"CONDITION","field":"E"...},
 {"seq":9,"deep":1,relation:"AND","type":"CONDITION","field":"F"...}
 ]

現在就剩最後一個問題：如何透過這個json對資料進行過濾了

#由於數組物件的本質依舊是一個中綴表達式，所以其本質依舊是一個中綴表達式的解析，關於解析原理，這裡不多介紹，簡單的說就是透過資料棧和符號棧根據括號（在我們這裡稱為群組）進行遍歷，想了解更多，可以透過下面這篇文章複習一下

於是我們定義三個變數：

 //关系 栈
 Deque<String> relationStack=new LinkedList();
 //结果栈
 Deque<Boolean> resultStack=new LinkedList();
 // 当前深度
 Integer nowDeep=1;

透過遍歷數組，將關係與結果入棧，當發現需要優先計算的時候，從結果棧中取出兩個值，從關係棧中取出關係運算符，計算後再次入棧，等待下一次計算

 for (ExpressDto expressDto:list) {
             if(!StringUtils.equals(expressDto.getType(),"GROUP")){
                 //TODO 进行具体单个表达式计算并获取结果
                 resultStack.push(expressDto.getResult());
                 // 将关系放入栈中
                 relationStack.push(expressDto.getRelation());
                 if(deep==0 && resultStack.size()>1){ //由于已处理小于0的deep，当前deep理论上是>=0的，0表示同等级，需要立即运算
                     relationOperator(relationStack, resultStack);
                 }
             }else{
                 // 将关系放入栈中
                 relationStack.push(expressDto.getRelation());
             }
         } 
 
 private void relationOperator(Deque<String> relationStack, Deque<Boolean> resultStack) {
         Boolean lastResult= resultStack.pop();
         Boolean firstResult= resultStack.pop();
         String relation=relationStack.pop();
         if(StringUtils.equals(relation,"AND")){
             resultStack.push(firstResult&& lastResult) ;
             return;
         }
         if(StringUtils.equals(relation,"OR")){
             resultStack.push( firstResult|| lastResult);
             return;
         }else{
             throw new RuntimeException("表达式解析异常：关系表达式错误");
         }
     }

再說一下注意的邊界事項：

1.首先我們同級中關聯關係僅存在且、或兩種，而這兩種的計算優先權是一樣的。故同一個Deep下，由左至右依序遍歷計算即可。

2.當遇到GROUP的類型時，相當於遇到了"(",我們可以發現它後面的元素Deep 1 直​​到Deep -1為止")"結束，而括號中的元素需要優先計算，也就是說"()"所產生優先權透過Deep 和Type=GROUP 共同控制

#3.當Deep減少時，意味著遇到了")"，此時結束的Group的數量等於Deep減少的數量，針對")"結束，每遇到一個")" 都需要對該級括號進行檢查，是否同級別的元素是否已經計算完畢。 

   /**
      * 处理层级遗留元素
      *
      * @param relationStack
      * @param resultStack
      */
     private void computeBeforeEndGroup(Deque<String> relationStack, Deque<Boolean> resultStack) {
         boolean isBeginSymbol=StringUtils.equals(relationStack.peek(),"BEGIN");//防止group中仅有一个判断条件
         while(!isBeginSymbol){//上一个运算符非BEGIN，说明该group中还有运算需要优先处理，正常这里应该仅循环一次
             relationOperator(relationStack, resultStack);
             isBeginSymbol=StringUtils.equals(relationStack.peek(),"BEGIN");
         }
         if(isBeginSymbol){
             relationStack.pop();//该优先级处理完毕，将BEGIN运算符弹出
         }
     }

4.當遍歷結束發現最後一個元素Deep不等於1時，意味著有括號結束，這時，同樣需要進行括號結束處理

最後上完整程式碼：

     /**
      * 表达式解析器
      * 表达式规则：
      * 关系relation属性有：BEGIN、AND、OR 三种
      * 表达式类型 Type 属性有：GROUP、CONDITION 两种
      * 深度 deep 属性 根节点为 1，每增加一个括号（GROUP）deep+1，括号结束deep-1
      * 序号req：初始值为1，往后依次递增，用于防止表达式解析顺序错误
      * exp1：表达式：A &&(( B || C )|| (D && E)) && F
      * 分解对象：
      * [
      * {"seq":1,"deep":1,relation:"BEGIN","type":"CONDITION","field"="A"...},
      * {"seq":2,"deep":1,relation:"AND","type":"GROUP","field":""...},
      * {"seq":3,"deep":2,relation:"BEGIN","type":"GROUP","field":""...},
      * {"seq":4,"deep":3,relation:"BEGIN","type":"CONDITION","field":"B"...},
      * {"seq":5,"deep":3,relation:"OR","type":"CONDITION","field":"C"...},
      * {"seq":6,"deep":2,relation:"OR","type":"GROUP","field":""...},
      * {"seq":7,"deep":3,relation:"BEGIN","type":"CONDITION","field":"D"...},
      * {"seq":8,"deep":3,relation:"AND","type":"CONDITION","field":"E"...},
      * {"seq":9,"deep":1,relation:"AND","type":"CONDITION","field":"F"...}
      * ]
      *
      * exp2:(A || B && C)||(D && E && F)
      * [
      * {"seq":1,"deep":1,relation:"BEGIN","type":"GROUP","field":""...},
      * {"seq":2,"deep":2,relation:"BEGIN","type":"CONDITION","field":"A"...},
      * {"seq":3,"deep":2,relation:"OR","type":"CONDITION","field":"B"...},
      * {"seq":4,"deep":2,relation:"AND","type":"CONDITION","field":"C"...},
      * {"seq":5,"deep":1,relation:"OR","type":"GROUP","field":""...},
      * {"seq":6,"deep":2,relation:"BEGIN","type":"CONDITION","field":"D"...},
      * {"seq":7,"deep":2,relation:"AND","type":"CONDITION","field":"E"...},
      * {"seq":8,"deep":2,relation:"AND","type":"CONDITION","field":"F"...}
      * ]
      *
      *
      * @param list
      * @return
      */
     public boolean expressProcessor(Listlist){
         //关系 栈
         Deque relationStack=new LinkedList();
         //结果栈
         Deque resultStack=new LinkedList();
         // 当前深度
         Integer nowDeep=1;
         Integer seq=0;
         for (ExpressDto expressDto:list) {
             // 顺序检测，防止顺序错误
             int checkReq=expressDto.getSeq()-seq;
             if(checkReq!=1){
                 throw new RuntimeException("表达式异常：解析顺序异常");
             }
             seq=expressDto.getSeq();
             //计算深度（计算优先级），判断当前逻辑是否需要处理括号
             int deep=expressDto.getDeep()-nowDeep;
             // 赋予当前深度
             nowDeep=expressDto.getDeep();
             //deep 减小，说明有括号结束，需要处理括号到对应的层级，deep减少数量等于组（"）"）结束的数量
             while(deep++ < 0){
                 computeBeforeEndGroup(relationStack, resultStack);
             }
 
             if(!StringUtils.equals(expressDto.getType(),"GROUP")){
                 //TODO 进行具体单个表达式计算并获取结果
                 resultStack.push(expressDto.getResult());
                 // 将关系放入栈中
                 relationStack.push(expressDto.getRelation());
                 if(deep==0 && resultStack.size()>1){ //由于已处理小于0的deep，当前deep理论上是>=0的，0表示同等级，需要立即运算
                     relationOperator(relationStack, resultStack);
                 }
             }else{
                 // 将关系放入栈中
                 relationStack.push(expressDto.getRelation());
             }
         }
         //遍历完毕，处理栈中未进行运算的节点
         while(nowDeep-- > 0){ // 这里使用 nowdeep>0 的原因是最后deep=1的关系表达式也需要进行处理
             computeBeforeEndGroup(relationStack, resultStack);
         }
         if(resultStack.size()!=1){
             throw new RuntimeException("表达式解析异常:解析结果数量异常解析数量:"+resultStack.size());
         }
         return resultStack.pop();
     }
 
     /**
      * 处理层级遗留元素
      *
      * @param relationStack
      * @param resultStack
      */
     private void computeBeforeEndGroup(Deque<String> relationStack, Deque<Boolean> resultStack) {
         boolean isBeginSymbol=StringUtils.equals(relationStack.peek(),"BEGIN");//防止group中仅有一个判断条件
         while(!isBeginSymbol){//上一个运算符非BEGIN，说明该group中还有运算需要优先处理，正常这里应该仅循环一次
             relationOperator(relationStack, resultStack);
             isBeginSymbol=StringUtils.equals(relationStack.peek(),"BEGIN");
         }
         if(isBeginSymbol){
             relationStack.pop();//该优先级处理完毕，将BEGIN运算符弹出
         }
     }
 
 
     /**
      * 关系运算处理
      * @param relationStack
      * @param resultStack
      */
     private void relationOperator(Deque relationStack, Deque resultStack) {
         Boolean lastResult= resultStack.pop();
         Boolean firstResult= resultStack.pop();
         String relation=relationStack.pop();
         if(StringUtils.equals(relation,"AND")){
             resultStack.push(firstResult&& lastResult) ;
             return;
         }
         if(StringUtils.equals(relation,"OR")){
             resultStack.push( firstResult|| lastResult);
             return;
         }else{
             throw new RuntimeException("表达式解析异常：关系表达式错误");
         }
     }

簡單寫了幾個測試案例：

 /**
      * 表达式：A
      */
     @Test
     public void expTest0(){
         ExpressDto E1=new ExpressDto().setDeep(1).setResult(false).setSeq(1).setType("CONDITION").setField("A").setRelation("BEGIN");
         List<ExpressDto> list = new ArrayList();
         list.add(E1);
         boolean re=expressProcessor(list);
         Assertions.assertFalse(re);
     }
     /**
      * 表达式：(A && B)||(C || D)
      */
     @Test
     public void expTest1(){
         ExpressDto E1=new ExpressDto().setDeep(1).setSeq(1).setType("GROUP").setRelation("BEGIN");
         ExpressDto E2=new ExpressDto().setDeep(2).setResult(true).setSeq(2).setType("Condition").setField("A").setRelation("BEGIN");
         ExpressDto E3=new ExpressDto().setDeep(2).setResult(false).setSeq(3).setType("Condition").setField("B").setRelation("AND");
         ExpressDto E4=new ExpressDto().setDeep(1).setSeq(4).setType("GROUP").setRelation("OR");
         ExpressDto E5=new ExpressDto().setDeep(2).setResult(true).setSeq(5).setType("Condition").setField("C").setRelation("BEGIN");
         ExpressDto E6=new ExpressDto().setDeep(2).setResult(false).setSeq(6).setType("Condition").setField("D").setRelation("OR");
 
         List<ExpressDto> list = new ArrayList();
         list.add(E1);
         list.add(E2);
         list.add(E3);
         list.add(E4);
         list.add(E5);
         list.add(E6);
         boolean re=expressProcessor(list);
         Assertions.assertTrue(re);
     }
 
     /**
      * 表达式：A && (B || C && D)
      */
     @Test
     public void expTest2(){
         ExpressDto E1=new ExpressDto().setDeep(1).setResult(true).setSeq(1).setType("Condition").setField("A").setRelation("BEGIN");
         ExpressDto E2=new ExpressDto().setDeep(1).setSeq(2).setType("GROUP").setRelation("AND");
         ExpressDto E3=new ExpressDto().setDeep(2).setResult(false).setSeq(3).setType("Condition").setField("B").setRelation("BEGIN");
         ExpressDto E4=new ExpressDto().setDeep(2).setResult(false).setSeq(4).setType("Condition").setField("C").setRelation("OR");
         ExpressDto E5=new ExpressDto().setDeep(2).setResult(true).setSeq(5).setType("Condition").setField("D").setRelation("AND");
         List<ExpressDto> list = new ArrayList();
         list.add(E1);
         list.add(E2);
         list.add(E3);
         list.add(E4);
         list.add(E5);
         boolean re=expressProcessor(list);
         Assertions.assertFalse(re);
         E4.setResult(true);
         list.set(3,E4);
         re=expressProcessor(list);
         Assertions.assertTrue(re);
         E1.setResult(false);
         list.set(0,E1);
         re=expressProcessor(list);
         Assertions.assertFalse(re);
     }
 
     @Test
     public void expTest3(){
         ExpressDto E1=new ExpressDto().setDeep(1).setResult(true).setSeq(1).setType("Condition").setField("A").setRelation("BEGIN");
         ExpressDto E2=new ExpressDto().setDeep(1).setSeq(2).setType("GROUP").setRelation("OR");
         ExpressDto E3=new ExpressDto().setDeep(2).setResult(true).setSeq(3).setType("Condition").setField("B").setRelation("BEGIN");
         ExpressDto E4=new ExpressDto().setDeep(2).setSeq(4).setType("GROUP").setRelation("AND");
         ExpressDto E5=new ExpressDto().setDeep(3).setResult(true).setSeq(5).setType("Condition").setField("C").setRelation("BEGIN");
         ExpressDto E6=new ExpressDto().setDeep(3).setResult(false).setSeq(6).setType("Condition").setField("D").setRelation("OR");
 
         List<ExpressDto> list = new ArrayList();
         list.add(E1);
         list.add(E2);
         list.add(E3);
         list.add(E4);
         list.add(E5);
         list.add(E6);
         boolean re=expressProcessor(list);
         Assertions.assertTrue(re);
     }
 
     /**
      * 表达式：A &&(( B || C )|| (D && E))
      */
     @Test
     public void expTest4(){
         ExpressDto E1=new ExpressDto().setDeep(1).setSeq(1).setType("CONDITION").setResult(true).setField("A").setRelation("BEGIN");
         ExpressDto E2=new ExpressDto().setDeep(1).setSeq(2).setType("GROUP").setRelation("AND");
         ExpressDto E3=new ExpressDto().setDeep(2).setSeq(3).setType("GROUP").setRelation("BEGIN");
         ExpressDto E4=new ExpressDto().setDeep(3).setSeq(4).setType("CONDITION").setResult(true).setField("B").setRelation("BEGIN");
         ExpressDto E5=new ExpressDto().setDeep(3).setSeq(5).setType("CONDITION").setResult(true).setField("C").setRelation("OR");
         ExpressDto E6=new ExpressDto().setDeep(2).setSeq(6).setType("GROUP").setRelation("OR");
         ExpressDto E7=new ExpressDto().setDeep(3).setSeq(7).setType("CONDITION").setResult(false).setField("D").setRelation("BEGIN");
         ExpressDto E8=new ExpressDto().setDeep(3).setSeq(8).setType("CONDITION").setResult(false).setField("E").setRelation("AND");
         List<ExpressDto> list = new ArrayList();
         list.add(E1);
         list.add(E2);
         list.add(E3);
         list.add(E4);
         list.add(E5);
         list.add(E6);
         list.add(E7);
         list.add(E8);
         boolean re=expressProcessor(list);
         Assertions.assertTrue(re);
     }
 
 
     /**
      * 表达式：(A)
      */
     @Test
     public void expTest5(){
         ExpressDto E1=new ExpressDto().setDeep(1).setSeq(1).setType("GROUP").setRelation("BEGIN");
         ExpressDto E2=new ExpressDto().setDeep(2).setResult(true).setSeq(2).setType("Condition").setField("A").setRelation("BEGIN");
         List<ExpressDto> list = new ArrayList();
         list.add(E1);
         list.add(E2);
         boolean re=expressProcessor(list);
         Assertions.assertTrue(re);
         E2.setResult(false);
         list.set(1,E2);
         Assertions.assertFalse(expressProcessor(list));
     }

測試結果：

#寫在最後

至此，一個表達式解析就完成了，讓我們回過來再看這張圖：

我們可以發現，其實Seq3 的作用其實只是標識了一個組的開始並記錄該組與同級別的其他元素的關聯關係，其實，這裡還可以進行一次優化：我們發現每當一個組的開始的第一個節點其前置關聯關係一定是Begin，Deep 1，實際上我們可以考慮將Group的關聯關係放在這個節點上，然後僅僅通過Deep的增減控制組的關係，這樣，我們就不需要類型為表達式或群組的這個欄位了，而且陣列長度也會因此減少，但是個人認為理解起來會麻煩一點。這裡說一下大概改造思路，程式碼就不放出來了：

  • 將程式碼中有關Type="GROUP"的判斷改為透過deep的差值=1來判斷
  • 深度判斷入棧邏輯修改
  • 在儲存關係符號的時候還要儲存這個關係符號對應的深度
  • 在處理同深度遺留元素時,即：computeBeforeEndGroup( ) 方法中， 原方法是透過Begin元素進行區分Group是否處理完成，現需要改成通過下一個符號的深度是否和當前深度是否相同進行判斷，並刪除掉有關BEGIN元素的彈出的邏輯

推薦學習：《java影片教學》

以上是實例介紹基於Java實作一個複雜關係表達式過濾器的詳細內容。更多資訊請關注PHP中文網其他相關文章！

陳述：
本文轉載於：jb51.net。如有侵權，請聯絡admin@php.cn刪除
上一篇：Java之物件銷毀和finalize方法的使用下一篇：Java之物件銷毀和finalize方法的使用

相關文章

看更多