近期在做一個(gè)項(xiàng)目，涉及到一些簡(jiǎn)單的規(guī)則匹配。規(guī)則的判定條件可以用關(guān)系表達(dá)式描述，形如(P1|P2)&(P3|P4)。其中&是與，|是或，P1-P4是Pattern，具體的匹配條件，返回值是True或者False。為計(jì)算此表達(dá)式的值，采用中序轉(zhuǎn)后序再計(jì)算表達(dá)式的值。

1. 后序表達(dá)式的生成

中序表達(dá)式轉(zhuǎn)后序表達(dá)式算法：

1. 用&|()對(duì)原表達(dá)式進(jìn)行拆分，得到List<String>。 2. 從前往后遍歷該List： ? ? （1）如果是一個(gè)pattern，則入棧。 ? ??（2）如果是左括號(hào)(，也入棧。 ? ??（3）如果是右括號(hào)： ? ??? ??（a）如果此時(shí)棧為空，則表示表達(dá)式解析異常，報(bào)警并退出。 ? ??? ??（b）如果棧不為空，則依次pop棧頂元素，直到匹配到左括號(hào)(。如果沒有左括號(hào)(的匹配，則表達(dá)式依次，報(bào)警并退出。 ? ??（4）如果是&和|： ? ??? ??（a）如果棧為空，直接入棧。 ? ??? ??（b）如果棧不為空，依次出棧直到匹配左括號(hào)（左括號(hào)不出棧）。再把操作符入棧。 3、所有的pattern和操作符都入棧以后，把棧中所有元素依次出棧，就得到后序表達(dá)式。

參考代碼：

List<String> postfix = new ArrayList<String>(); Stack<String> stack = new Stack<String>(); String delims = "&|()"; // 支持的操作符 StringTokenizer st = new StringTokenizer(rule, delims, true); while (st.hasMoreTokens()) {String tk = st.nextToken();if (!delims.contains(tk)) {// pattern，直接入棧 postfix.add(tk);} else if (tk.equals("(")) {// 左括號(hào)，入棧 stack.push(tk);} else if (tk.equals(")")) {if (stack.empty()) {// 碰到右括號(hào)，如果棧為空，解析異常throw new RuleException("parseRule Error!");}String val = stack.pop();// 如果棧不為空，依次出棧直到匹配左括號(hào)while (!val.equals("(")) {postfix.add(val);if (!stack.empty()) {val = stack.pop();} elsebreak;}if (stack.empty() && !val.equals("(")) {// 如果匹配不到左括號(hào)，解析異常throw new RuleException("parseRule Error!");}} else if (tk.equals("&") || tk.equals("|")) {if (stack.empty()) {// 碰到操作符，如果棧空，則直接入棧 stack.push(tk);} else {// 如果棧不為空，依次出棧直到匹配左括號(hào)while (!stack.empty() && !stack.lastElement().equals("(")) {postfix.add(stack.pop());}// 操作符入棧 stack.push(tk);}} }// 所有的pattern和操作符匹配完畢，把堆棧中還有的數(shù)據(jù)依次出棧 while (!stack.empty()) {postfix.add(stack.pop()); }System.out.println("Original Rule：" + rule); System.out.println("Postfix Rule: " + postfix.toString());

?

2. 后序表達(dá)式的計(jì)算

后序表達(dá)式的計(jì)算算法：

1. 從前往后遍歷中序表達(dá)式： ? ??（1）如果是&|操作符，則pop兩個(gè)字段r1和r2，計(jì)算r1&r2或r1|r2的值r3，并將r3入棧。 ? ??（2）如果是pattern，則計(jì)算pattern的匹配結(jié)果True Or False，并將結(jié)果入棧。 2、中序表達(dá)式便利完畢，棧中只有1個(gè)元素，即為表達(dá)式結(jié)果。

?參考代碼：

Stack<Boolean> stack = new Stack<Boolean>(); for (String str : this.postfix) {if (str.equals("&")) {// pop兩個(gè)pattern，計(jì)算boolean r1 = stack.pop();boolean r2 = stack.pop();stack.push(r1 && r2);} else if (str.equals("|")) {// pop兩個(gè)pattern，計(jì)算boolean r1 = stack.pop();boolean r2 = stack.pop();stack.push(r1 || r2);} else {// 計(jì)算pattern的值，并push到stackPattern ptn = this.patterns.get(str);stack.push(ptn.judge(fact));} }if (stack.size() == 1) {return stack.pop(); } else {throw new RuleException("judge failed: postfix error!"); }

?

轉(zhuǎn)載于:https://www.cnblogs.com/simplestupid/p/4771892.html

總結(jié)

以上是生活随笔為你收集整理的关系表达式的计算的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。