As per my promise, here is the stuff that lets us parse integers and operators
(+-*/) and brackets into RPN order.
Actually the patch is in two parts.
1. o.a.p.h.r.formula.FormulaParser :- this class now completely parses a
formula and returns a rpn order list of Ptgs. The rpn conversion is implicit in
the parsing grammer, thus there is no seperation "toRPN" method. try calling
this class with (2+3)*4 and 2+3*4 to test its capabilities. This class is built
using the philosophy of all parsing (tokenising) in one class -- the actual
conversion to hex is of course in each ptg impl.
2. o.a.p.h.r.formula.Ptg :- a new method List ptgToRpn(List) that converts a
list of infix order ptgs to rpn order ptgs. This is what one would do if we
follow Andy's idea of each Ptg being responsible for tokenising the relevent
part of the formula string. I havent tested this too much since i would have to
write code in each ptg to test it. however, you can try it for 2+3, which works
fine , since the Andy has already written up the IntPtg and AddPtg. I've added
a method to the OperationsPtg interface to to return precedence.
Since i havent yet made up my mind on either of the two approaches, i will
parallely experiment on both tracks, until circumstances or good sense overtake
me.
With the above level of functionality, we should be able to integrate formulas
consisting of literals and operators into poi. The next hill to climb of course
is functions, and the next mountain is cell references.
Regards
-
Avik
? .nbattrs
? formula.patch
Index: DividePtg.java
===================================================================
RCS file:
/home/cvspublic/jakarta-poi/src/java/org/apache/poi/hssf/record/formula/DividePtg.java,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 DividePtg.java
--- DividePtg.java 31 Jan 2002 02:23:44 -0000 1.1.1.1
+++ DividePtg.java 21 Apr 2002 20:41:07 -0000
@@ -118,4 +118,11 @@
buffer.append(operands[ 1 ].toFormulaString());
return buffer.toString();
}
+ public int getPrecedence() {
+ return 4;
+ }
+
+ public int getStringLength() {
+ return 1;
+ }
}
Index: FormulaParser.java
===================================================================
RCS file:
/home/cvspublic/jakarta-poi/src/java/org/apache/poi/hssf/record/formula/FormulaParser.java,v
retrieving revision 1.1
diff -u -r1.1 FormulaParser.java
--- FormulaParser.java 17 Apr 2002 23:06:49 -0000 1.1
+++ FormulaParser.java 21 Apr 2002 20:41:08 -0000
@@ -61,17 +61,25 @@
import java.util.Stack;
/**
- * EXPERIMENTAL code to parse formulas back and forth between RPN and not
+ * EXPERIMENTAL
*
* @author Avik Sengupta <[EMAIL PROTECTED]>
+ *
+ * This class parses a formula string into a List of tokens in RPN order
+ * Inspired by
+ * Lets Build a Compiler, by Jack Crenshaw
+ * BNF for the formula expression is :
+ * <expression> ::= <term> [<addop> <term>]*
+ * <term> ::= <factor> [ <mulop> <factor ]*
+ * <factor> ::= <number> | (<expression>) | <cellRef>
*/
public class FormulaParser {
private String formulaString;
private int pointer=0;
- private Stack operationsList = new java.util.Stack();
- private Stack operandsList = new java.util.Stack();
+ private List tokens = new java.util.Stack();
+ //private Stack tokens = new java.util.Stack();
private List result = new ArrayList();
private int numParen;
@@ -160,7 +168,6 @@
return (c =='+' || c =='-');
}
-
//{--------------------------------------------------------------}
//{ Recognize White Space }
@@ -261,7 +268,7 @@
boolean cellRef = true ; //we should probably do it with reg exp??
if (cellRef) {
- operationsList.add(new ValueReferencePtg()); //TODO we need to pass
in Name somewhere
+ tokens.add(new ValueReferencePtg()); //TODO we need to pass in Name
+somewhere
}else {
//handle after named range is integrated!!
}
@@ -277,10 +284,10 @@
private void Factor() {
if (Look == '(' ) {
Match('(');
- operationsList.add(new ParenthesisPtg());
+ //tokens.add(new ParenthesisPtg());
Expression();
Match(')');
- operationsList.add(new ParenthesisPtg());
+ //tokens.add(new ParenthesisPtg());
return;
} else if (IsAlpha(Look)){
Ident();
@@ -288,7 +295,7 @@
//EmitLn("MOVE #" + GetNum() + ",D0");
IntPtg p = new IntPtg();
p.setValue(Short.parseShort(GetNum()));
- operandsList.add(p);
+ tokens.add(p);
}
}
@@ -299,7 +306,7 @@
private void Multiply(){
Match('*');
Factor();
- operationsList.add(new MultiplyPtg());
+ tokens.add(new MultiplyPtg());
//EmitLn("MULS (SP)+,D0");
}
@@ -310,7 +317,7 @@
private void Divide() {
Match('/');
Factor();
- operationsList.add(new DividePtg());
+ tokens.add(new DividePtg());
//EmitLn("MOVE (SP)+,D1");
//EmitLn("EXS.L D0");
//EmitLn("DIVS D1,D0");
@@ -338,7 +345,7 @@
Match('+');
Term();
//EmitLn("ADD (SP)+,D0");
- operationsList.add(new AddPtg());
+ tokens.add(new AddPtg());
}
@@ -348,7 +355,7 @@
private void Subtract() {
Match('-');
Term();
- operationsList.add(new SubtractPtg());
+ tokens.add(new SubtractPtg());
//EmitLn("SUB (SP)+,D0");
//EmitLn("NEG D0");
}
@@ -364,9 +371,11 @@
Term();
}
while (IsAddop(Look)) {
- EmitLn("MOVE D0,-(SP)");
+ // EmitLn("MOVE D0,-(SP)");
if ( Look == '+' ) Add();
if (Look == '-') Subtract();
+ // if (Look == '*') Multiply();
+ // if (Look == '/') Divide();
}
}
@@ -397,39 +406,20 @@
Init();
Expression();
//now tokenisation is done .. convert to RPN!!
- tokenToRPN();
+ /**String s = "";
+ for (int i=0;i<tokens.size();i++) {
+ s=s+ ( (Ptg)tokens.get(i)).toFormulaString();
+ s=s+" ";
+ } **/
+ //System.out.println("Tokens are : " + s);
+ //result = ptgsToRpn(tokens);
}
- private void tokenToRPN() {
- OperationPtg op;
- Ptg operand;
- int numOper = 0;
- int numOnStack = 0;
- result.add(operandsList.pop()); numOnStack++;
-
- while (!operationsList.isEmpty()) {
- op = (OperationPtg) operationsList.pop();
- if (op instanceof ParenthesisPtg) {
- // do something smart
- }
-
-
- for (numOper = op.getNumberOfOperands();numOper>0;numOper--) {
- if (numOnStack==0) {
- result.add(operandsList.pop());//numOnStack++;
- } else {
- numOnStack--;
- }
- }
- result.add(op);
- numOnStack++;
- }
- }
public String toString() {
StringBuffer buf = new StringBuffer();
- for (int i=0;i<result.size();i++) {
- buf.append( ( (Ptg)result.get(i)).toFormulaString());
+ for (int i=0;i<tokens.size();i++) {
+ buf.append( ( (Ptg)tokens.get(i)).toFormulaString());
buf.append(' ');
}
return buf.toString();
Index: MultiplyPtg.java
===================================================================
RCS file:
/home/cvspublic/jakarta-poi/src/java/org/apache/poi/hssf/record/formula/MultiplyPtg.java,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 MultiplyPtg.java
--- MultiplyPtg.java 31 Jan 2002 02:23:44 -0000 1.1.1.1
+++ MultiplyPtg.java 21 Apr 2002 20:41:09 -0000
@@ -118,4 +118,11 @@
buffer.append(operands[ 1 ].toFormulaString());
return buffer.toString();
}
+ public int getPrecedence() {
+ return 4;
+ }
+
+ public int getStringLength() {
+ return 1;
+ }
}
Index: OperationPtg.java
===================================================================
RCS file:
/home/cvspublic/jakarta-poi/src/java/org/apache/poi/hssf/record/formula/OperationPtg.java,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 OperationPtg.java
--- OperationPtg.java 31 Jan 2002 02:23:44 -0000 1.1.1.1
+++ OperationPtg.java 21 Apr 2002 20:41:09 -0000
@@ -76,4 +76,6 @@
public int getNumberOfOperands();
public String toFormulaString(Ptg [] operands);
+
+ public int getPrecedence();
}
Index: PowerPtg.java
===================================================================
RCS file:
/home/cvspublic/jakarta-poi/src/java/org/apache/poi/hssf/record/formula/PowerPtg.java,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 PowerPtg.java
--- PowerPtg.java 31 Jan 2002 02:23:44 -0000 1.1.1.1
+++ PowerPtg.java 21 Apr 2002 20:41:10 -0000
@@ -108,6 +108,10 @@
{
return "^";
}
+
+ public int getPrecedence() {
+ return 3;
+ }
public String toFormulaString(Ptg [] operands)
{
Index: Ptg.java
===================================================================
RCS file:
/home/cvspublic/jakarta-poi/src/java/org/apache/poi/hssf/record/formula/Ptg.java,v
retrieving revision 1.2
diff -u -r1.2 Ptg.java
--- Ptg.java 18 Apr 2002 12:00:53 -0000 1.2
+++ Ptg.java 21 Apr 2002 20:41:11 -0000
@@ -77,6 +77,11 @@
{
}
+ /** return Ptgs in Reverse polish notation order
+ * @return Ptg[] array of ptgs in rpn order
+ * @param formula the formula string
+ * @param offset the offset ??
+ */
public static Ptg[] parse(String formula, int offset) {
List ptgs = new ArrayList();
@@ -86,8 +91,56 @@
ptgs.add(ptg);
}
- Ptg[] retval = new Ptg[ptgs.size()];
- retval = (Ptg[])ptgs.toArray(retval);
+ List rpnPtgs = ptgsToRpn(ptgs);
+ Ptg[] retval = new Ptg[rpnPtgs.size()];
+ retval = (Ptg[])rpnPtgs.toArray(retval);
+ return retval;
+ }
+
+ /** convert infix order ptg list to rpn order ptg list
+ * @return List ptgs in RPN order
+ * @param infixPtgs List of ptgs in infix order
+ */
+ public static List ptgsToRpn(List infixPtgs) {
+ java.util.Stack operands = new java.util.Stack();
+ java.util.List retval = new java.util.Stack();
+
+ java.util.ListIterator i = infixPtgs.listIterator();
+ Object p;
+ OperationPtg o ;
+ boolean weHaveABracket = false;
+ while (i.hasNext()) {
+ p=i.next();
+ if (p instanceof OperationPtg) {
+ if (p instanceof ParenthesisPtg) {
+ if (!weHaveABracket) {
+ operands.push(p);
+ weHaveABracket = true;
+ } else {
+ o = (OperationPtg) operands.pop();
+ while (!(o instanceof ParenthesisPtg)) {
+ retval.add(o);
+ }
+ weHaveABracket = false;
+ }
+ } else {
+
+ while (!operands.isEmpty() && ((OperationPtg)
+operands.peek()).getPrecedence() >= ((OperationPtg) p).getPrecedence() ) { //TODO
+handle ^ since it is right associative
+ retval.add(operands.pop());
+ }
+ operands.push(p);
+ }
+ } else {
+ retval.add(p);
+ }
+ }
+ while (!operands.isEmpty()) {
+ if (operands.peek() instanceof ParenthesisPtg ){
+ //throw some error
+ } else {
+ retval.add(operands.pop());
+ }
+ }
return retval;
}
@@ -96,6 +149,7 @@
for (int k =0; k < ptgs.length; k++) {
Ptg ptg = ptgs[k];
res.append(ptg.toFormulaString());
+ res.append(' ');
}
return res.toString();
}
Index: SubtractPtg.java
===================================================================
RCS file:
/home/cvspublic/jakarta-poi/src/java/org/apache/poi/hssf/record/formula/SubtractPtg.java,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 SubtractPtg.java
--- SubtractPtg.java 31 Jan 2002 02:23:44 -0000 1.1.1.1
+++ SubtractPtg.java 21 Apr 2002 20:41:12 -0000
@@ -118,4 +118,11 @@
buffer.append(operands[ 1 ].toFormulaString());
return buffer.toString();
}
+ public int getPrecedence() {
+ return 5;
+ }
+
+ public int getStringLength() {
+ return 1;
+ }
}
