1 /**************************************************************
2  *
3  * Licensed to the Apache Software Foundation (ASF) under one
4  * or more contributor license agreements.  See the NOTICE file
5  * distributed with this work for additional information
6  * regarding copyright ownership.  The ASF licenses this file
7  * to you under the Apache License, Version 2.0 (the
8  * "License"); you may not use this file except in compliance
9  * with the License.  You may obtain a copy of the License at
10  *
11  *   http://www.apache.org/licenses/LICENSE-2.0
12  *
13  * Unless required by applicable law or agreed to in writing,
14  * software distributed under the License is distributed on an
15  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16  * KIND, either express or implied.  See the License for the
17  * specific language governing permissions and limitations
18  * under the License.
19  *
20  *************************************************************/
21 
22 
23 
24 package org.openoffice.xmerge.converter.xml.sxc.pexcel.records.formula;
25 
26 import java.util.*;
27 import org.openoffice.xmerge.util.Debug;
28 
29 /**
30  * FormulaCompiler converts Calc formula string into PocketXL bytes
31  * and PocketXL formula bytes into Calc Formula strings
32  *
33  * For converting from infix to Reverse Polish (or Postfix) notation the string is
34  * converted into a vector of Tokens and then re-ordered based on a modified version
35  * of the standard Infix to RPN conversion algorithms.
36  * <pre>
37  *	Infix2Rpn(tokens)
38  *		while have more tokens
39  *			if token is operand
40  *				push to stack
41  *			else if token is function, argument separater, or open bracket
42  *				push token
43  *				extract tokens to matching close bracket into param
44  *				Infix2Rpn(param)
45  *			else if token is close bracket
46  *				pop from stack into result until close bracket or function
47  *			else
48  *				while stack.top.priority &gt;= token.priority
49  *					add stack.pop to result
50  *				push token onto stack
51  * </pre>
52  * For converting from RPN to Infix the following algorithm is applied:
53  * <pre>
54  * 		while have more tokens
55  * 			if token is operand
56  *				push token to stack
57  *			else if token is function or operator
58  *				pop from stack number of args required by token
59  *				apply token to params to make expr
60  *				push expr to stack
61  *		return stack.pop
62  * </pre>
63  */
64 public class FormulaCompiler {
65 	/**
66 	 *	Constructs a FormulaCompiler object
67 	 */
FormulaCompiler()68     public FormulaCompiler() {
69     }
70 
isPercent(Token pt)71     private boolean isPercent(Token pt) {
72         return pt.getTokenID() == TokenConstants.TPERCENT;
73     }
74 
isOpenBrace(Token pt)75     private boolean isOpenBrace(Token pt) {
76         return pt.getTokenID() == TokenConstants.TPAREN;
77     }
78 
isCloseBrace(Token pt)79     private boolean isCloseBrace(Token pt) {
80         return pt.getValue().compareTo(")") == 0;
81     }
82 
isParamDelimiter(Token pt)83     private boolean isParamDelimiter(Token pt) {
84         return pt.getTokenID() == TokenConstants.TARGSEP;
85     }
86 
isBinaryOperator(Token pt)87 	private boolean isBinaryOperator(Token pt) {
88 		return false;
89 	}
90 
91     /**
92 	 * Re-order into Infix format
93 	 * @param	tokens	The tokens in RPN form
94 	 * @return	The vector of tokens re-ordered in Infix notation
95      */
RPN2Infix(Vector tokens)96     public Vector RPN2Infix(Vector tokens) {
97         Vector infixExpr = new Vector(15);
98         ListIterator iter = tokens.listIterator();
99         Stack evalStack = new Stack();
100         Stack args = new Stack();
101 
102         while (iter.hasNext()) {
103             Token pt = (Token)iter.next();
104             if (pt.isOperand()) {
105                 Vector expr = new Vector(5);
106                 expr.add(pt);
107                 evalStack.push(expr);
108             } else if (pt.isOperator() || pt.isFunction()) {
109                 args.clear();
110                 for (int i=0; i< pt.getNumArgs(); i++) {
111                     args.push(evalStack.pop());
112                 }
113                 evalStack.push(makeExpression(pt, args));
114             }
115         }
116         return (Vector)evalStack.elementAt(0);
117     }
118 
119     /**
120 	 * Convert the infix expression to RPN. Note that open brackets are saved onto the stack to preserve the users bracketing.
121 	 * <p>Also note that the open bracket following functions is not pushed onto the stack - it is always implied when
122 	 * writing out results
123 	 *
124      * @param	tokens	The vector of tokens in Infix form
125 	 *
126 	 * @return	A vector of tokens for the expression in Reverse Polish Notation order
127      */
infix2RPN(Vector tokens)128     public Vector infix2RPN(Vector tokens) {
129         Vector rpnExpr = new Vector(15);
130         Stack evalStack = new Stack();
131         ListIterator iter = tokens.listIterator();
132         while (iter.hasNext()) {
133             Token pt = (Token)iter.next();
134 
135             if (pt.isOperand()) { //Operands are output immediately
136                 rpnExpr.add(pt);
137             } else if (pt.isFunction() || isParamDelimiter(pt) || isOpenBrace(pt)) { //Extract parameters after afunction or comma
138                 evalStack.push(pt);
139 				if (pt.isFunction()) {
140 					iter.next();
141 				}
142                 Vector param = extractParameter(iter);
143 				Debug.log(Debug.TRACE, "Extracted parameter " + param);
144                 rpnExpr.addAll(infix2RPN(param));
145             } else if (isCloseBrace(pt)) { //Pop off stack till you meet a function or an open bracket
146                 Token tmpTok = null;
147                 boolean bPop = true;
148                 while (bPop) {
149                     if (evalStack.isEmpty()) {
150                         bPop = false;
151                     } else {
152                         tmpTok = (Token)evalStack.pop();
153                         //if (!(isOpenBrace(tmpTok) || isParamDelimiter(tmpTok))) { //Don't output brackets and commas
154                         if (!isParamDelimiter(tmpTok)) { //Don't output commas
155                             rpnExpr.add(tmpTok);
156 						}
157                         if (tmpTok.isFunction() || isOpenBrace(tmpTok)) {
158 							bPop = false;
159                         }
160                     }
161                 }
162             } else {
163                 if (!evalStack.isEmpty()) {
164                     while (!evalStack.isEmpty() &&
165                             (((Token)evalStack.peek()).getTokenPriority() >=pt.getTokenPriority())) {
166                     	Token topTok = (Token)evalStack.peek();
167                         if (topTok.isFunction() || isOpenBrace(topTok)) {
168                             break;
169                         }
170                        	rpnExpr.add(evalStack.pop());
171                     }
172                 }
173                 evalStack.push(pt);
174             }
175         }
176 
177         while (!evalStack.isEmpty()) {
178             Token topTok = (Token)evalStack.peek();
179             if (!(isOpenBrace(topTok) || isParamDelimiter(topTok))) { //Don't output brackets and commas
180             	rpnExpr.add(evalStack.pop());
181 			}
182 			else
183 			{
184 				evalStack.pop();
185 			}
186         }
187         return rpnExpr;
188     }
189 
190     /**
191      * Extract a parameter or bracketed sub-expression
192 	 * @param iter an iterator into the list
193 	 * @return A complete sub-expression
194      */
extractParameter(ListIterator iter)195     protected Vector extractParameter(ListIterator iter) {
196         Vector param = new Vector(5);
197 		int subExprCount = 0;
198 
199         while (iter.hasNext()) {
200             Token pt = (Token)iter.next();
201 			Debug.log(Debug.TRACE, "Token is " + pt + " and subExprCount is " + subExprCount);
202 			if (isOpenBrace(pt)) {
203 				subExprCount++;
204                 param.add(pt);
205 			} else if (isCloseBrace(pt)) {
206 				if (subExprCount == 0) {
207 					iter.previous();
208 					return param;
209 				} else {
210 					subExprCount--;
211 					param.add(pt);
212 				}
213 			} else if (isParamDelimiter(pt) && (subExprCount == 0)) {
214 				iter.previous();
215 				return param;
216 			} else {
217 				param.add(pt);
218 			}
219         }
220         return param;
221     }
222 
223 	/**
224 	 * Given the operator and it's operators
225 	 * @param 	pt	The operator token
226 	 * @param	args	The arguments for this operator
227 	 * @return	A correctly ordered expression
228 	 */
makeExpression(Token pt, Stack args)229     protected Vector makeExpression(Token pt, Stack args) {
230         Vector tmp = new Vector(5);
231 		TokenFactory tf = new TokenFactory();
232         if (pt.isOperator()) {
233             if (pt.getNumArgs()==2) { //Binary operator
234                 tmp.addAll((Vector)args.pop());
235                 tmp.add(pt);
236                 tmp.addAll((Vector)args.pop());
237             } else if (pt.getNumArgs() == 1) {
238 				if(isPercent(pt)) {
239 					tmp.addAll((Vector)args.elementAt(0));
240 					tmp.add(pt);
241 				} else {
242 					tmp.add(pt);
243 					tmp.addAll((Vector)args.elementAt(0));
244 				}
245 				if (isOpenBrace(pt)) {
246 					tmp.add(tf.getOperatorToken(")",1));
247 				}
248 			}
249         } else if (pt.isFunction()) {
250 	    	tmp.add(pt);
251 			tmp.add(tf.getOperatorToken("(",1));
252 			if (!args.isEmpty()) {
253 				Vector v = (Vector)args.pop();
254 				tmp.addAll(v);
255 			}
256 			while (!args.isEmpty()) {
257 				tmp.add(tf.getOperatorToken(",",1));
258 				Vector v = (Vector)args.pop();
259 				tmp.addAll(v);
260 
261 			}
262 			tmp.add(tf.getOperatorToken(")",1));
263         }
264 
265 		return tmp;
266     }
267 }
268