您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“基于Java如何實現(xiàn)一個復(fù)雜關(guān)系表達式過濾器”,感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷,實用性強。下面就讓小編來帶大家學(xué)習(xí)“基于Java如何實現(xiàn)一個復(fù)雜關(guān)系表達式過濾器”吧!
最近,有一個新需求,需要后臺設(shè)置一個復(fù)雜的關(guān)系表達式,根據(jù)用戶指定ID,解析該用用戶是否滿足該條件,后臺設(shè)置類似于禪道的搜索條件
但是不同的是禪道有且僅有兩個組,每個組最多三個條件
而我們這邊組與關(guān)系可能是更復(fù)雜的,組中有組,每個條件都是有且或關(guān)系的。由于保密原因,原型就不發(fā)出來了。
看到這個需求,作為一個后端,第一時間想到的是類似QLEpress這類的表達式框架,只要構(gòu)建一個表達式,通過解析表達式即可快速對目標用戶進行篩選,但是可惜的是前端同學(xué)不干了,因為作為使用vue或react這類數(shù)據(jù)驅(qū)動的框架來說,將表達式轉(zhuǎn)換為為上述的一個表單太難了 ,所以想了一下,決定自己定義一個數(shù)據(jù)結(jié)構(gòu),實現(xiàn)表達式解析。方便前端同學(xué)的處理。
雖然是用類實現(xiàn)表達式,但是其本質(zhì)上依舊還是個表達式,我們列舉一個簡單的表達式:設(shè)條件為a,b,c,d,我們隨意構(gòu)造一個表達式:
boolean result=a>100 && b=10 || (c != 3 && d < 50)
我們對表達式進行分析,可以發(fā)現(xiàn)表達式 都是共同屬性有:
過濾字段(a、b、c、d),判斷條件(大于、小于、不等于等等),對比值(a>100 中的100)。
另外,還有關(guān)聯(lián)關(guān)系(且、或)和計算優(yōu)先級這幾個屬性組成。
于是我們對表達式進行簡化:
令a>100 =>A,b=10 =>B,c!=3=>C ,d<50=>D,于是我們得到:
result=A && B || (C && D)
現(xiàn)在問題來了,如何處理優(yōu)先級呢?
如上表達式,很明顯,這是一個大學(xué)里學(xué)過的標準的中序表達式,于是,我們畫一下它的樹形圖:
根據(jù)這個圖,我們可以明顯的看到,A且B 和C且D是同一級別,于是,我們按照這個理論設(shè)計一個層級的概念Deep,我們標注一下,然后再對節(jié)點的類型做一下區(qū)分,可得:
我們可以看到作為葉子節(jié)點(上圖綠色部分),相對于其計算計算關(guān)系,遇到了一定是優(yōu)先計算的,所以對于深度的優(yōu)先級,我們僅需要考慮非葉子節(jié)點即可,即上圖中的藍色節(jié)點部分,于是我們得到了,計算優(yōu)先級這個概念我們可以轉(zhuǎn)換為表達式的深度。
我們再看上面這個圖,Deep1 的關(guān)系是Deep2中 A且B 和 C且D兩個表達式計算出的結(jié)果再進行與或關(guān)系的,我們設(shè)A 且B 為 G1, C且D為 G2,于是我們發(fā)現(xiàn)關(guān)系節(jié)點關(guān)聯(lián)的類型有兩種類型,一種是條件Condition ,一種是組Group
至此,這個類的雛形基本就確定了。這個類包含 關(guān)聯(lián)關(guān)系(Relation)、判斷字段(Field)、運算符(Operator)、運算值(Values)、類型(Type)、深度(Deep)
但是,有個問題,上面的分析中,我們在將表達式轉(zhuǎn)換成樹,現(xiàn)在我們試著將其還原,于是我們一眼可以得到其中一種表達式:
result=(A && B)||(C && D)
很顯然,和我們的原來的表達式并不一致,這是因為我們上述僅能記錄表達式的計算順序,而不能完全準確的表示這個表達式,這是因為在我們解析表達式的過程中,不僅是有深度、還有一個時序關(guān)系,即從左到右的順序表示,而此時G1中的內(nèi)容實際上在原表達式中的深度應(yīng)該是1而不是2,然后我們引入序號的概念,將原來樹變成有向的圖即:
根據(jù)這個圖,我們就還原出有且唯一的一個表達式了:result= A && B ||(C && D)
。
好了,我們分析了半天,原理說完了,回到最初始的問題:前后端怎么實現(xiàn)?對著上圖想象一下,貌似還是無法處理,因為這個結(jié)構(gòu)還是太復(fù)雜了。對于前端,數(shù)據(jù)最好是方便遍歷的,對于后端,數(shù)據(jù)最好是方便處理的,于是這時候我們需要將上面這個圖轉(zhuǎn)換成一個數(shù)組。
上面說到了需要一個數(shù)組的結(jié)構(gòu),我們具體分析一下這個部分
我們發(fā)現(xiàn)作為葉子節(jié)點,可以始終優(yōu)先計算,所以我們可以將其壓縮,并將關(guān)系放置在其中一個表達式中形成 ^A -> &&B
或 A&& -> B$
的形式,這里我用正則的開始(^) 和結(jié)束($) 表示了一下開始 和 結(jié)束 的概念,這里為了與產(chǎn)品原型保持一致我們用第一種方式,即關(guān)系符號表示與前一個元素的關(guān)系,于是我們再分析一下:
再對序號進行改造:
于是我們得到最終的數(shù)據(jù)結(jié)構(gòu):
@Data @AllArgsConstructor @NoArgsConstructor @Accessors(chain = true) public class ExpressDto { /** * 序號 */ private Integer seq; /** * 深度(運算優(yōu)先級) */ private Integer deep; /** * 關(guān)系運算符 */ private String relation; /** * 類型 */ private String type; /** * 運算條件 */ private String field; /** * 邏輯運算符 */ private String operator; /** * 運算值 */ private String values; /** * 運算結(jié)果 */ private Boolean result; }
現(xiàn)在數(shù)據(jù)結(jié)構(gòu)終于完成,既方便存儲,又(相對)方便前臺展示,現(xiàn)在構(gòu)造一個稍微復(fù)雜的表達式
A &&(( B || C )|| (D && E)) && F
換成數(shù)組對象,開始用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"...} ]
現(xiàn)在就剩最后一個問題:如何通過這個json對數(shù)據(jù)進行過濾了
由于數(shù)組對象的本質(zhì)依舊是一個中綴表達式,所以其本質(zhì)依舊是一個中綴表達式的解析,關(guān)于解析原理,這里不多介紹,簡單的說就是通過數(shù)據(jù)棧和符號棧根據(jù)括號(在我們這里稱為組)進行遍歷,想了解更多,可以通過下面這篇文章復(fù)習(xí)一下
于是我們定義三個變量:
//關(guān)系 棧 Deque<String> relationStack=new LinkedList(); //結(jié)果棧 Deque<Boolean> resultStack=new LinkedList(); // 當前深度 Integer nowDeep=1;
通過遍歷數(shù)組,將關(guān)系與結(jié)果入棧,當發(fā)現(xiàn)需要優(yōu)先計算的時候,從結(jié)果棧中取出兩個值,從關(guān)系棧中取出關(guān)系運算符,計算后再次入棧,等待下一次計算
for (ExpressDto expressDto:list) { if(!StringUtils.equals(expressDto.getType(),"GROUP")){ //TODO 進行具體單個表達式計算并獲取結(jié)果 resultStack.push(expressDto.getResult()); // 將關(guān)系放入棧中 relationStack.push(expressDto.getRelation()); if(deep==0 && resultStack.size()>1){ //由于已處理小于0的deep,當前deep理論上是>=0的,0表示同等級,需要立即運算 relationOperator(relationStack, resultStack); } }else{ // 將關(guān)系放入棧中 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("表達式解析異常:關(guān)系表達式錯誤"); } }
再說一下注意的邊界事項:
1.首先我們同級中關(guān)聯(lián)關(guān)系僅存在且、或兩種,而這兩種的計算優(yōu)先級是一樣的。故同一個Deep下,從左到右依次遍歷計算即可。
2.當遇到GROUP的類型時,相當于遇到了"(",我們可以發(fā)現(xiàn)它后面的元素Deep +1 直到Deep -1為止")"結(jié)束,而括號中的元素需要優(yōu)先計算,也就是說"()"所產(chǎn)生優(yōu)先級通過Deep 和Type=GROUP 共同控制
3.當Deep減少時,意味著遇到了")",此時結(jié)束的Group的數(shù)量等于Deep減少的數(shù)量,針對")"結(jié)束,每遇到一個")" 都需要對該級括號進行檢查,是否同級別的元素是否已經(jīng)計算完畢。
/** * 處理層級遺留元素 * * @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中還有運算需要優(yōu)先處理,正常這里應(yīng)該僅循環(huán)一次 relationOperator(relationStack, resultStack); isBeginSymbol=StringUtils.equals(relationStack.peek(),"BEGIN"); } if(isBeginSymbol){ relationStack.pop();//該優(yōu)先級處理完畢,將BEGIN運算符彈出 } }
4.當遍歷結(jié)束發(fā)現(xiàn)最后一個元素Deep不等于1時,意味著有括號結(jié)束,這時,同樣需要進行括號結(jié)束處理
最后上完整代碼:
/** * 表達式解析器 * 表達式規(guī)則: * 關(guān)系relation屬性有:BEGIN、AND、OR 三種 * 表達式類型 Type 屬性有:GROUP、CONDITION 兩種 * 深度 deep 屬性 根節(jié)點為 1,每增加一個括號(GROUP)deep+1,括號結(jié)束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){ //關(guān)系 棧 Deque<String> relationStack=new LinkedList(); //結(jié)果棧 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(); //計算深度(計算優(yōu)先級),判斷當前邏輯是否需要處理括號 int deep=expressDto.getDeep()-nowDeep; // 賦予當前深度 nowDeep=expressDto.getDeep(); //deep 減小,說明有括號結(jié)束,需要處理括號到對應(yīng)的層級,deep減少數(shù)量等于組(")")結(jié)束的數(shù)量 while(deep++ < 0){ computeBeforeEndGroup(relationStack, resultStack); } if(!StringUtils.equals(expressDto.getType(),"GROUP")){ //TODO 進行具體單個表達式計算并獲取結(jié)果 resultStack.push(expressDto.getResult()); // 將關(guān)系放入棧中 relationStack.push(expressDto.getRelation()); if(deep==0 && resultStack.size()>1){ //由于已處理小于0的deep,當前deep理論上是>=0的,0表示同等級,需要立即運算 relationOperator(relationStack, resultStack); } }else{ // 將關(guān)系放入棧中 relationStack.push(expressDto.getRelation()); } } //遍歷完畢,處理棧中未進行運算的節(jié)點 while(nowDeep-- > 0){ // 這里使用 nowdeep>0 的原因是最后deep=1的關(guān)系表達式也需要進行處理 computeBeforeEndGroup(relationStack, resultStack); } if(resultStack.size()!=1){ throw new RuntimeException("表達式解析異常:解析結(jié)果數(shù)量異常解析數(shù)量:"+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中還有運算需要優(yōu)先處理,正常這里應(yīng)該僅循環(huán)一次 relationOperator(relationStack, resultStack); isBeginSymbol=StringUtils.equals(relationStack.peek(),"BEGIN"); } if(isBeginSymbol){ relationStack.pop();//該優(yōu)先級處理完畢,將BEGIN運算符彈出 } } /** * 關(guān)系運算處理 * @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("表達式解析異常:關(guān)系表達式錯誤"); } }
簡單寫了幾個測試用例:
/** * 表達式: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)); }
測試結(jié)果:
至此,一個表達式解析就完成了,讓我們回過來再看這張圖:
我們可以發(fā)現(xiàn),其實Seq3 的作用其實僅僅是標識了一個組的開始并記錄該組與同級別的其他元素的關(guān)聯(lián)關(guān)系,其實,這里還可以進行一次優(yōu)化:我們發(fā)現(xiàn)每當一個組的開始的第一個節(jié)點其前置關(guān)聯(lián)關(guān)系一定是Begin,Deep+1,實際上我們可以考慮將Group的關(guān)聯(lián)關(guān)系放在這個節(jié)點上,然后僅僅通過Deep的增減控制組的關(guān)系,這樣,我們就不需要類型為表達式或組的這個字段了,而且數(shù)組長度也會因此減少,但是個人認為理解起來會麻煩一點。這里說一下大概改造思路,代碼就不放出來了:
將代碼中有關(guān)Type="GROUP"的判斷改為通過deep的差值=1進行判斷
深度判斷入棧邏輯修改
在存儲關(guān)系符號的時候還要存儲一下這個關(guān)系符號對應(yīng)的深度
在處理同深度遺留元素時,即:computeBeforeEndGroup()
方法中, 原方法是通過Begin元素進行區(qū)分Group是否處理完成,現(xiàn)需要改成通過下一個符號的深度是否和當前深度是否相同進行判斷,并刪除掉有關(guān)BEGIN元素的彈出的邏輯
到此,相信大家對“基于Java如何實現(xiàn)一個復(fù)雜關(guān)系表達式過濾器”有了更深的了解,不妨來實際操作一番吧!這里是億速云網(wǎng)站,更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。