001: /*************************************************************************
002: * *
003: * 1) This source code file, in unmodified form, and compiled classes *
004: * derived from it can be used and distributed without restriction, *
005: * including for commercial use. (Attribution is not required *
006: * but is appreciated.) *
007: * *
008: * 2) Modified versions of this file can be made and distributed *
009: * provided: the modified versions are put into a Java package *
010: * different from the original package, edu.hws; modified *
011: * versions are distributed under the same terms as the original; *
012: * and the modifications are documented in comments. (Modification *
013: * here does not include simply making subclasses that belong to *
014: * a package other than edu.hws, which can be done without any *
015: * restriction.) *
016: * *
017: * David J. Eck *
018: * Department of Mathematics and Computer Science *
019: * Hobart and William Smith Colleges *
020: * Geneva, New York 14456, USA *
021: * Email: eck@hws.edu WWW: http://math.hws.edu/eck/ *
022: * *
023: *************************************************************************/package edu.hws.jcm.functions;
024:
025: import edu.hws.jcm.data.*;
026:
027: /**
028: * The SummationParser class makes it possible to use summations such as sum(i,1,5,x^i) in a Parser.
029: * The summation psedu-function has four parameters: (1) The summation variable, which must be an identifier;
030: * (2) The lower limit for the summation, given as an expression; (3) The upper limit for the
031: * summation, given as an expression; and (4) The expression that is summed. The values of
032: * the lower and upper limit expressions are rounded to the nearest integer. The expression in
033: * the fourth parameter can (and presumably will) use the summation variable (as well as other
034: * identifiers known to the parser).
035: *
036: * <p>To use summations with a Parser p, just say p.add(new SummationParser()). It's unlikely that
037: * you will ever need to do anything else with SummationParsers.
038: * If you want to use a name other than "sum", you can change the name after creating the
039: * SummationParser object but before adding it to a parser. (Note, by the way, that parsers by default do not do
040: * factorials. If you want a parser that recognizes factorials, you could do something
041: * like p = new Parser(Parser.DEFAULT_OPTIONS | Parser.FACTORIAL).)
042: *
043: */
044: public class SummationParser implements ParserExtension {
045:
046: /* A name is required by the MathObject interface, which ParserExtension extends. The name
047: is what is used to indicate a summation in an expression. The name should not be changed
048: after the SummationParser is added to a Parser. */
049:
050: private String name = "sum";
051:
052: /**
053: * Set the name, which will be used in place of "sum" in expressions. This should not
054: * be done after the SummationParser has been added to a Parser. The default name is "sum".
055: */
056: public void setName(String name) {
057: this .name = name;
058: }
059:
060: /**
061: * Get the name, which will be used in place of "sum" in expressions.
062: */
063: public String getName() {
064: return name;
065: }
066:
067: /**
068: * When the name of this ParserExtension is encountered by a parser with which
069: * the extension is registered, the parser calls this routine to parse the
070: * summation subexpression. The subexpression has the form
071: * (<variable>,<lower-limit>,<upper-limit>,<expression>). This method is
072: * not meant to be called directly
073: */
074: public void doParse(Parser parser, ParserContext context) {
075: int tok = context.next();
076: String open = context.tokenString;
077: if (tok == ParserContext.OPCHARS
078: && (open.equals("(")
079: || (open.equals("[") && (context.options & Parser.BRACKETS) != 0) || (open
080: .equals("{") && (context.options & Parser.BRACES) != 0))) {
081: String close = open.equals("(") ? ")"
082: : (open.equals("[") ? "]" : "}");
083: tok = context.next(); // Must be an identifier.
084: if (tok != ParserContext.IDENTIFIER)
085: throw new ParseError(
086: "Expected the summation variable as the first argument of "
087: + name + ".", context);
088: String varName = context.tokenString;
089: tok = context.next();
090: if (tok != ParserContext.OPCHARS
091: || !context.tokenString.equals(","))
092: throw new ParseError(
093: "Exprected a comma after the index variable, "
094: + varName + ".", context);
095: parser.parseExpression(context);
096: tok = context.next();
097: if (tok != ParserContext.OPCHARS
098: || !context.tokenString.equals(","))
099: throw new ParseError(
100: "Exprected a comma after the lower limit expression for "
101: + name + ".", context);
102: parser.parseExpression(context);
103: tok = context.next();
104: if (tok != ParserContext.OPCHARS
105: || !context.tokenString.equals(","))
106: throw new ParseError(
107: "Exprected a comma after the upper limit expression for "
108: + name + ".", context);
109: Variable v = new Variable(varName);
110: context.mark(); // Temporoarily add the summation variable to the symbol table.
111: context.add(v);
112: ExpressionProgram saveProg = context.prog;
113: context.prog = new ExpressionProgram(); // Compile the expression into a new program.
114: parser.parseExpression(context);
115: tok = context.next();
116: if (tok != ParserContext.OPCHARS
117: || !context.tokenString.equals(close))
118: throw new ParseError("Expected a \"" + close
119: + "\" at the end of the paramter list for "
120: + name + ".", context);
121: context.revert(); // Restore the state of the ParserContext.
122: saveProg.addCommandObject(new Cmd(v, context.prog));
123: context.prog = saveProg;
124: } else
125: throw new ParseError(
126: "Parentheses required around parameters of summation.",
127: context);
128: } // end doParse()
129:
130: private static class Cmd implements ExpressionCommand {
131: // When a summation occurs in an expression, it is represented in the compiled ExpressionProgram
132: // by an object belonging to this class.
133:
134: private Variable sumVar; // The summation variable.
135: private ExpressionProgram sumExpr; // The expression that is summed
136:
137: Cmd(Variable v, ExpressionProgram e) {
138: // Constructor.
139: sumVar = v;
140: sumExpr = e;
141: }
142:
143: public void apply(StackOfDouble stack, Cases cases) {
144: // This routine is called when an ExpressionCommand object is encountered during
145: // the evaluation of an ExpressionProgram. The stack may contain results of
146: // previous commands in the program. In this case, the command is a summation
147: // and the stack contains the upper and lower limits summation limits.
148: double upper = Math.round(stack.pop()) + 0.1; // Get summation limits.
149: double lower = Math.round(stack.pop());
150: if (Double.isNaN(upper) && Double.isNaN(lower)
151: || upper - lower > 1000000)
152: stack.push(Double.NaN);
153: double sum = 0;
154: for (double x = lower; x <= upper; x++) { // Compute the sum.
155: sumVar.setVal(x);
156: sum += sumExpr.getVal();
157: }
158: stack.push(sum); // Leave the sum on the stack.
159: }
160:
161: public void compileDerivative(ExpressionProgram prog,
162: int myIndex, ExpressionProgram deriv, Variable wrt) {
163: // The ExpressionCommand occurs in the program prog at the index indicated by myIndex.
164: // Add commands to deriv that will evaluate the derivative of this command with respect to
165: // the variable wrt. Note that the "Cmd" object is preceded in the program by commands that
166: // compute the lower and upper limits of the summation.
167: if (!sumExpr.dependsOn(wrt))
168: deriv.addConstant(0);
169: else {
170: int upper = prog.extent(myIndex - 1); // Size of expression giving the upper limit.
171: prog.copyExpression(myIndex - 1 - upper, deriv); // Copy lower limit exression to deriv.
172: prog.copyExpression(myIndex - 1, deriv); // Copy upper limit expression to deriv.
173: deriv.addCommandObject(new Cmd(sumVar,
174: (ExpressionProgram) sumExpr.derivative(wrt)));
175: }
176: }
177:
178: public int extent(ExpressionProgram prog, int myIndex) {
179: // The ExpressionCommand occurs in the program prog at the index indicated by myIndex.
180: // Return the total number of indices in prog occupied by this command and the commands
181: // that generate data used by this command. In this case, that means the commands that
182: // compute the upper and lower limits of the summatio, plus this Cmd object.
183: int upper = prog.extent(myIndex - 1); // Extent of upper limit expression in prog.
184: int lower = prog.extent(myIndex - 1 - upper); // Extent of lower limit expression in prog.
185: return upper + lower + 1; // Upper + lower limits + this object.
186: }
187:
188: public boolean dependsOn(Variable x) {
189: // Return true if this command depends on the value of x, false otherwise.
190: // That is, when apply() is called, can the result depend on the value of x?
191: return sumExpr.dependsOn(x);
192: }
193:
194: public void appendOutputString(ExpressionProgram prog,
195: int myIndex, StringBuffer buffer) {
196: // The ExpressionCommand occurs in the program prog at the index indicated by myIndex.
197: // Add a print string representation of the sub-expression represented by this command
198: // (including any previous commands in the program that generate data used by this
199: // command).
200: int upper = prog.extent(myIndex - 1);
201: buffer.append("sum(");
202: buffer.append(sumVar.getName());
203: buffer.append(", ");
204: prog.appendOutputString(myIndex - 1 - upper, buffer);
205: buffer.append(", ");
206: prog.appendOutputString(myIndex - 1, buffer);
207: buffer.append(", ");
208: buffer.append(sumExpr.toString());
209: buffer.append(")");
210: }
211:
212: } // end nested class Cmd
213:
214: } // end SumParserExtension
|