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 >= 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