View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  
18  package org.apache.log4j.rule;
19  
20  import java.util.HashMap;
21  import java.util.List;
22  import java.util.Map;
23  import java.util.Stack;
24  import java.util.StringTokenizer;
25  import java.util.Vector;
26  
27  /***
28   * A helper class which converts infix expressions to postfix expressions
29   * Currently grouping is supported, as well as all of the
30   * Rules supported by <code>RuleFactory</code>
31   *
32   * NOTE: parsing is supported through the use of <code>StringTokenizer</code>,
33   * which means all tokens in the expression must be separated by spaces.
34   *
35   * Supports grouping via parens, mult-word operands using single quotes,
36   * and these operators:
37   *
38   * !        NOT operator
39   * !=       NOT EQUALS operator
40   * ==       EQUALS operator
41   * ~=       CASE-INSENSITIVE equals operator
42   * ||       OR operator
43   * &&       AND operator
44   * like     REGEXP operator
45   * exists   NOT NULL operator
46   * &lt      LESS THAN operator
47   * &gt      GREATER THAN operator
48   * &lt=     LESS THAN EQUALS operator
49   * &gt=     GREATER THAN EQUALS operator
50   *
51   * @author Scott Deboy (sdeboy@apache.org)
52   */
53  
54  public class InFixToPostFix {
55      /***
56       * Precedence map.
57       */
58    private final Map precedenceMap = new HashMap();
59      /***
60       * Operators.
61       */
62    private final List operators = new Vector();
63  
64      /***
65       * Create new instance.
66       */
67    public InFixToPostFix() {
68       super();
69      //boolean operators
70      operators.add("!");
71      operators.add("!=");
72      operators.add("==");
73      operators.add("~=");
74      operators.add("||");
75      operators.add("&&");
76      operators.add("like");
77      operators.add("exists");
78      operators.add("<");
79      operators.add(">");
80      operators.add("<=");
81      operators.add(">=");
82  
83      //boolean precedence
84      precedenceMap.put("<", new Integer(3));
85      precedenceMap.put(">", new Integer(3));
86      precedenceMap.put("<=", new Integer(3));
87      precedenceMap.put(">=", new Integer(3));
88  
89      precedenceMap.put("!", new Integer(3));
90      precedenceMap.put("!=", new Integer(3));
91      precedenceMap.put("==", new Integer(3));
92      precedenceMap.put("~=", new Integer(3));
93      precedenceMap.put("like", new Integer(3));
94      precedenceMap.put("exists", new Integer(3));
95  
96      precedenceMap.put("||", new Integer(2));
97      precedenceMap.put("&&", new Integer(2));
98    }
99  
100     /***
101      * Convert in-fix expression to post-fix.
102      * @param expression in-fix expression.
103      * @return post-fix expression.
104      */
105   public String convert(final String expression) {
106     return infixToPostFix(new StringTokenizer(expression));
107   }
108 
109     /***
110      * Evaluates whether symbol is operand.
111      * @param s symbol.
112      * @return true if operand.
113      */
114   boolean isOperand(final String s) {
115     String symbol = s.toLowerCase();
116     return (!operators.contains(symbol));
117   }
118 
119     /***
120      * Determines whether one symbol precedes another.
121      * @param s1 symbol 1
122      * @param s2 symbol 2
123      * @return true if symbol 1 precedes symbol 2
124      */
125   boolean precedes(final String s1, final String s2) {
126     String symbol1 = s1.toLowerCase();
127     String symbol2 = s2.toLowerCase();
128 
129     if (!precedenceMap.keySet().contains(symbol1)) {
130       return false;
131     }
132 
133     if (!precedenceMap.keySet().contains(symbol2)) {
134       return false;
135     }
136 
137     int index1 = ((Integer) precedenceMap.get(symbol1)).intValue();
138     int index2 = ((Integer) precedenceMap.get(symbol2)).intValue();
139 
140     boolean precedesResult = (index1 < index2);
141 
142     return precedesResult;
143   }
144 
145     /***
146      * convert in-fix expression to post-fix.
147      * @param tokenizer tokenizer.
148      * @return post-fix expression.
149      */
150   String infixToPostFix(final StringTokenizer tokenizer) {
151     final String space = " ";
152     StringBuffer postfix = new StringBuffer();
153 
154     Stack stack = new Stack();
155 
156     while (tokenizer.hasMoreTokens()) {
157       String token = tokenizer.nextToken();
158 
159       boolean inText = (token.startsWith("'") && (!token.endsWith("'")));
160       if (inText) {
161           while (inText && tokenizer.hasMoreTokens()) {
162             token = token + " " + tokenizer.nextToken();
163             inText = !(token.endsWith("'"));
164         }
165       }
166 
167       if ("(".equals(token)) {
168         //recurse
169         postfix.append(infixToPostFix(tokenizer));
170         postfix.append(space);
171       } else if (")".equals(token)) {
172         //exit recursion level
173         while (stack.size() > 0) {
174           postfix.append(stack.pop().toString());
175           postfix.append(space);
176         }
177 
178         return postfix.toString();
179       } else if (isOperand(token)) {
180         postfix.append(token);
181         postfix.append(space);
182       } else {
183         //operator..
184         //peek the stack..if the top element has a lower precedence than token
185         //(peeked + has lower precedence than token *),
186         // push token onto the stack
187         //otherwise, pop top element off stack and add to postfix string
188         //in a loop until lower precedence or empty..then push token
189         if (stack.size() > 0) {
190 
191           String peek = stack.peek().toString();
192 
193           if (precedes(peek, token)) {
194             stack.push(token);
195           } else {
196             boolean bypass = false;
197 
198             do {
199               if (
200                 (stack.size() > 0)
201                   && !precedes(stack.peek().toString(), token)) {
202                 postfix.append(stack.pop().toString());
203                 postfix.append(space);
204               } else {
205                 bypass = true;
206               }
207             } while (!bypass);
208 
209             stack.push(token);
210           }
211         } else {
212           stack.push(token);
213         }
214       }
215     }
216 
217     while (stack.size() > 0) {
218       postfix.append(stack.pop().toString());
219       postfix.append(space);
220     }
221 
222     return postfix.toString();
223   }
224 }