首頁 > 軟體

基於Java實現一個複雜關係表示式過濾器

2022-07-12 18:01:02

背景

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

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

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

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

分析準備

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

boolean result=a>100 && b=10 || (c != 3 && d < 50)

我們對錶示式進行分析,可以發現表示式 都是共同屬性有:

過濾欄位(a、b、c、d),判斷條件(大於、小於、不等於等等),對比值(a>100 中的100)。

另外,還有關聯關係(且、或)和計算優先順序這幾個屬性組成。

於是我們對錶示式進行簡化:

令a>100 =>A,b=10 =>B,c!=3=>C ,d<50=>D,於是我們得到:

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 -> &&BA&& -> 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(List<ExpressDto>list){
         //關係 棧
         Deque<String> relationStack=new LinkedList();
         //結果棧
         Deque<Boolean> 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<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("表示式解析異常:關係表示式錯誤");
         }
     }

簡單寫了幾個測試用例:

 /**
      * 表示式: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表示式過濾器的資料請關注it145.com其它相關文章!


IT145.com E-mail:sddin#qq.com