1    
2    /* ====================================================================
3     * The Apache Software License, Version 1.1
4     *
5     * Copyright (c) 2002 The Apache Software Foundation.  All rights
6     * reserved.
7     *
8     * Redistribution and use in source and binary forms, with or without
9     * modification, are permitted provided that the following conditions
10    * are met:
11    *
12    * 1. Redistributions of source code must retain the above copyright
13    *    notice, this list of conditions and the following disclaimer.
14    *
15    * 2. Redistributions in binary form must reproduce the above copyright
16    *    notice, this list of conditions and the following disclaimer in
17    *    the documentation and/or other materials provided with the
18    *    distribution.
19    *
20    * 3. The end-user documentation included with the redistribution,
21    *    if any, must include the following acknowledgment:
22    *       "This product includes software developed by the
23    *        Apache Software Foundation (http://www.apache.org/)."
24    *    Alternately, this acknowledgment may appear in the software itself,
25    *    if and wherever such third-party acknowledgments normally appear.
26    *
27    * 4. The names "Apache" and "Apache Software Foundation" and
28    *    "Apache POI" must not be used to endorse or promote products
29    *    derived from this software without prior written permission. For
30    *    written permission, please contact apache@apache.org.
31    *
32    * 5. Products derived from this software may not be called "Apache",
33    *    "Apache POI", nor may "Apache" appear in their name, without
34    *    prior written permission of the Apache Software Foundation.
35    *
36    * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
37    * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
38    * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
39    * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
40    * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41    * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
42    * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
43    * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
44    * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
45    * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
46    * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
47    * SUCH DAMAGE.
48    * ====================================================================
49    *
50    * This software consists of voluntary contributions made by many
51    * individuals on behalf of the Apache Software Foundation.  For more
52    * information on the Apache Software Foundation, please see
53    * <http://www.apache.org/>.
54    */
55   
56   
57   package org.apache.poi.hssf.record.formula;
58   
59   import java.util.List;
60   import java.util.ArrayList;
61   import java.util.Stack;
62   
63   /**
64    * EXPERIMENTAL code to parse formulas back and forth between RPN and not
65    *
66    * @author Avik Sengupta <lists@aviksengupta.com>
67    */
68   public class FormulaParser {
69       
70       private String formulaString;
71       private int pointer=0;
72       
73       private Stack operationsList = new java.util.Stack();
74       private Stack operandsList = new java.util.Stack();
75       private List result = new ArrayList();
76       private int numParen;
77       
78       //{--------------------------------------------------------------}
79       //{ Constant Declarations }
80       
81       private static char TAB = '\t';
82       private static char CR = '\n';
83       
84       //{--------------------------------------------------------------}
85       //{ Variable Declarations }
86       
87       private char Look;              //{ Lookahead Character }
88       
89       public FormulaParser(String formula){
90           formulaString = formula;
91           pointer=0;
92       }
93       
94       //{--------------------------------------------------------------}
95       //{ Read New Character From Input Stream }
96       
97       private void GetChar() {
98           Look=formulaString.charAt(pointer++);
99           System.out.println("Got char: "+Look);
100      }
101      
102      //{--------------------------------------------------------------}
103      //{ Report an Error }
104      
105      private void Error(String s) {
106          System.out.println("Error: "+s);
107      }
108      
109      
110      //{--------------------------------------------------------------}
111      //{ Report Error and Halt }
112      
113      private void Abort(String s) {
114          Error(s);
115          //System.exit(1);  //throw exception??
116          throw new RuntimeException("Cannot Parse, sorry");
117      }
118      
119      
120      //{--------------------------------------------------------------}
121      //{ Report What Was Expected }
122      
123      private void Expected(String s) {
124          Abort(s + " Expected");
125      }
126      
127      
128      //{--------------------------------------------------------------}
129      //{ Recognize an Alpha Character }
130      
131      private boolean IsAlpha(char c) {
132          return Character.isLetter(c);
133          //return  UpCase(c) in ['A'..'Z'];
134      }
135      
136      
137      //{--------------------------------------------------------------}
138      //{ Recognize a Decimal Digit }
139      
140      private boolean IsDigit(char c) {
141          System.out.println("Checking digit for"+c);
142          return Character.isDigit(c);
143          
144          //return ("0123456789".indexOf( (int) c) != 0)//c in ['0'..'9'];
145      }
146      
147      
148      //{--------------------------------------------------------------}
149      //{ Recognize an Alphanumeric }
150      
151      private boolean  IsAlNum(char c) {
152          return  (IsAlpha(c) || IsDigit(c));
153      }
154      
155      
156      //{--------------------------------------------------------------}
157      //{ Recognize an Addop }
158      
159      private boolean IsAddop( char c) {
160          return (c =='+' || c =='-');
161      }
162      
163      
164      //{--------------------------------------------------------------}
165      //{ Recognize White Space }
166      
167      private boolean IsWhite( char c) {
168          return  (c ==' ' || c== TAB);
169      }
170      
171      
172      //{--------------------------------------------------------------}
173      //{ Skip Over Leading White Space }
174      
175      private void SkipWhite() {
176          while (IsWhite(Look)) {
177              GetChar();
178          }
179      }
180      
181      
182      //{--------------------------------------------------------------}
183      //{ Match a Specific Input Character }
184      
185      private void Match(char x) {
186          if (Look != x) {
187              Expected("" + x + "");
188          }else {
189              GetChar();
190              SkipWhite();
191          }
192      }
193      
194      
195      //{--------------------------------------------------------------}
196      //{ Get an Identifier }
197      
198      private String GetName() {
199          String Token;
200          Token = "";
201          if (!IsAlpha(Look)) {
202              Expected("Name");
203          }
204          while (IsAlNum(Look)) {
205              Token = Token + Character.toUpperCase(Look);
206              GetChar();
207          }
208          
209          SkipWhite();
210          return Token;
211      }
212      
213      
214      //{--------------------------------------------------------------}
215      //{ Get a Number }
216      
217      private String GetNum() {
218          String Value ="";
219          if  (!IsDigit(Look)) Expected("Integer");
220          while (IsDigit(Look)){
221              Value = Value + Look;
222              GetChar();
223          }
224          SkipWhite();
225          return Value;
226      }
227      
228      
229      //{--------------------------------------------------------------}
230      //{ Output a String with Tab }
231      
232      private void  Emit(String s){
233          System.out.print(TAB+s);
234      }
235      
236      
237      //{--------------------------------------------------------------}
238      //{ Output a String with Tab and CRLF }
239      
240      private void EmitLn(String s) {
241          Emit(s);
242          System.out.println();;
243      }
244      
245      
246      //{---------------------------------------------------------------}
247      //{ Parse and Translate a Identifier }
248      
249      private void Ident() {
250          String Name;
251          Name = GetName();
252          if (Look == '('){
253              Match('(');
254              //Expression() -- add this!
255              Match(')');
256              //this is the end of the function
257              //EmitLn("BSR " + Name);
258          } else {
259              //EmitLn("MOVE " + Name + "(PC),D0b");
260              //this can be either a cell ref or a named range !!
261              
262              boolean cellRef = true ; //we should probably do it with reg exp??
263              if (cellRef) {
264                  operationsList.add(new ValueReferencePtg()); //TODO we need to pass in Name somewhere
265              }else {
266                  //handle after named range is integrated!!
267              }
268          }
269      }
270  
271      
272      //{---------------------------------------------------------------}
273      //{ Parse and Translate a Math Factor }
274      
275      //procedure Expression; Forward;
276      
277      private void Factor() {
278          if (Look == '(' ) {
279              Match('(');
280              operationsList.add(new ParenthesisPtg());
281              Expression();
282              Match(')');
283              operationsList.add(new ParenthesisPtg());
284              return;
285          } else if (IsAlpha(Look)){
286              Ident();
287          }else{
288              //EmitLn("MOVE #" + GetNum() + ",D0");
289              IntPtg p = new IntPtg();
290              p.setValue(Short.parseShort(GetNum()));
291              operandsList.add(p);
292          }
293      }
294  
295      
296      //{--------------------------------------------------------------}
297      //{ Recognize and Translate a Multiply }
298      
299      private void Multiply(){
300          Match('*');
301          Factor();
302          operationsList.add(new MultiplyPtg());
303          //EmitLn("MULS (SP)+,D0");
304      }
305      
306      
307      //{-------------------------------------------------------------}
308      //{ Recognize and Translate a Divide }
309      
310      private void Divide() {
311          Match('/');
312          Factor();
313          operationsList.add(new DividePtg());
314          //EmitLn("MOVE (SP)+,D1");
315          //EmitLn("EXS.L D0");
316          //EmitLn("DIVS D1,D0");
317      }
318      
319      
320      //{---------------------------------------------------------------}
321      //{ Parse and Translate a Math Term }
322      
323      private void  Term(){
324          Factor();
325          while (Look == '*' || Look == '/' ) {
326              //EmitLn("MOVE D0,-(SP)");
327              ///TODO do we need to do anything here??
328              if (Look == '*') Multiply();
329              if (Look == '/') Divide();
330          }
331      }
332      
333      
334      //{--------------------------------------------------------------}
335      //{ Recognize and Translate an Add }
336      
337      private void Add() {
338          Match('+');
339          Term();
340          //EmitLn("ADD (SP)+,D0");
341          operationsList.add(new AddPtg());
342      }
343      
344      
345      //{-------------------------------------------------------------}
346      //{ Recognize and Translate a Subtract }
347      
348      private void Subtract() {
349          Match('-');
350          Term();
351          operationsList.add(new SubtractPtg());
352          //EmitLn("SUB (SP)+,D0");
353          //EmitLn("NEG D0");
354      }
355      
356      
357      //{---------------------------------------------------------------}
358      //{ Parse and Translate an Expression }
359      
360      private void Expression() {
361          if (IsAddop(Look)) {
362              EmitLn("CLR D0");  //unaryAdd ptg???
363          } else {
364              Term();
365          }
366          while (IsAddop(Look)) {
367              EmitLn("MOVE D0,-(SP)");
368              if ( Look == '+' )  Add();
369              if (Look == '-') Subtract();
370          }
371      }
372      
373      
374      //{--------------------------------------------------------------}
375      //{ Parse and Translate an Assignment Statement }
376      /**
377  procedure Assignment;
378  var Name: string[8];
379  begin
380     Name := GetName;
381     Match('=');
382     Expression;
383     EmitLn('LEA ' + Name + '(PC),A0');
384     EmitLn('MOVE D0,(A0)')
385  end;
386       **/
387      
388      //{--------------------------------------------------------------}
389      //{ Initialize }
390      
391      private void  Init() {
392          GetChar();
393          SkipWhite();
394      }
395      
396      public void parse() {
397          Init();
398          Expression();
399          //now tokenisation is done .. convert to RPN!!
400          tokenToRPN();
401      }
402      
403      private void tokenToRPN() {
404          OperationPtg op;
405          Ptg operand;
406          int numOper = 0;
407          int numOnStack = 0;
408          result.add(operandsList.pop()); numOnStack++;
409          
410          while (!operationsList.isEmpty()) {
411              op = (OperationPtg) operationsList.pop();
412              if (op instanceof ParenthesisPtg) {
413                  // do something smart
414              }
415              
416              
417              for (numOper = op.getNumberOfOperands();numOper>0;numOper--) {
418                  if (numOnStack==0) {
419                      result.add(operandsList.pop());//numOnStack++;
420                  } else {
421                      numOnStack--;
422                  }
423              }
424              result.add(op);
425              numOnStack++;
426          }
427      }
428      
429      public String toString() {
430          StringBuffer buf = new StringBuffer();
431             for (int i=0;i<result.size();i++) {
432              buf.append( ( (Ptg)result.get(i)).toFormulaString());
433              buf.append(' ');
434          } 
435          return buf.toString();
436      }
437      
438      
439      //{--------------------------------------------------------------}
440      //{ Main Program for testing}
441      public static void main(String[] argv) {
442          FormulaParser fp = new FormulaParser(argv[0]+";");
443          fp.parse();
444          System.out.println(fp.toString());
445          
446          //If Look <> CR then Expected('NewLine');
447      }
448      //{--------------------------------------------------------------}
449      
450  }