1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 * < LESS THAN operator
47 * > GREATER THAN operator
48 * <= LESS THAN EQUALS operator
49 * >= 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
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
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
169 postfix.append(infixToPostFix(tokenizer));
170 postfix.append(space);
171 } else if (")".equals(token)) {
172
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
184
185
186
187
188
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 }