1 /* 2 * Copyright (C) 2015 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.android.calculator2; 18 19 import android.content.Context; 20 import android.text.SpannableString; 21 import android.text.SpannableStringBuilder; 22 import android.text.Spanned; 23 import android.text.style.TtsSpan; 24 25 import java.io.ByteArrayOutputStream; 26 import java.io.DataInput; 27 import java.io.DataOutput; 28 import java.io.DataOutputStream; 29 import java.io.IOException; 30 import java.math.BigInteger; 31 import java.util.ArrayList; 32 import java.util.Collections; 33 import java.util.HashSet; 34 35 /** 36 * A mathematical expression represented as a sequence of "tokens". 37 * Many tokens are represented by button ids for the corresponding operator. 38 * A token may also represent the result of a previously evaluated expression. 39 * The add() method adds a token to the end of the expression. The delete method() removes one. 40 * Clear() deletes the entire expression contents. Eval() evaluates the expression, 41 * producing a UnifiedReal result. 42 * Expressions are parsed only during evaluation; no explicit parse tree is maintained. 43 * 44 * The write() method is used to save the current expression. Note that neither UnifiedReal 45 * nor the underlying CR provide a serialization facility. Thus we save all previously 46 * computed values by writing out the expression that was used to compute them, and reevaluate 47 * when reading it back in. 48 */ 49 class CalculatorExpr { 50 /** 51 * An interface for resolving expression indices in embedded subexpressions to 52 * the associated CalculatorExpr, and associating a UnifiedReal result with it. 53 * All methods are thread-safe in the strong sense; they may be called asynchronously 54 * at any time from any thread. 55 */ 56 public interface ExprResolver { 57 /* 58 * Retrieve the expression corresponding to index. 59 */ 60 CalculatorExpr getExpr(long index); 61 /* 62 * Retrieve the degree mode associated with the expression at index i. 63 */ 64 boolean getDegreeMode(long index); 65 /* 66 * Retrieve the stored result for the expression at index, or return null. 67 */ 68 UnifiedReal getResult(long index); 69 /* 70 * Atomically test for an existing result, and set it if there was none. 71 * Return the prior result if there was one, or the new one if there was not. 72 * May only be called after getExpr. 73 */ 74 UnifiedReal putResultIfAbsent(long index, UnifiedReal result); 75 } 76 77 private ArrayList<Token> mExpr; // The actual representation 78 // as a list of tokens. Constant 79 // tokens are always nonempty. 80 81 private static enum TokenKind { CONSTANT, OPERATOR, PRE_EVAL }; 82 private static TokenKind[] tokenKindValues = TokenKind.values(); 83 private final static BigInteger BIG_MILLION = BigInteger.valueOf(1000000); 84 private final static BigInteger BIG_BILLION = BigInteger.valueOf(1000000000); 85 86 private static abstract class Token { 87 abstract TokenKind kind(); 88 89 /** 90 * Write token as either a very small Byte containing the TokenKind, 91 * followed by data needed by subclass constructor, 92 * or as a byte >= 0x20 directly describing the OPERATOR token. 93 */ 94 abstract void write(DataOutput out) throws IOException; 95 96 /** 97 * Return a textual representation of the token. 98 * The result is suitable for either display as part od the formula or TalkBack use. 99 * It may be a SpannableString that includes added TalkBack information. 100 * @param context context used for converting button ids to strings 101 */ 102 abstract CharSequence toCharSequence(Context context); 103 } 104 105 /** 106 * Representation of an operator token 107 */ 108 private static class Operator extends Token { 109 // TODO: rename id. 110 public final int id; // We use the button resource id 111 Operator(int resId) { 112 id = resId; 113 } 114 Operator(byte op) throws IOException { 115 id = KeyMaps.fromByte(op); 116 } 117 @Override 118 void write(DataOutput out) throws IOException { 119 out.writeByte(KeyMaps.toByte(id)); 120 } 121 @Override 122 public CharSequence toCharSequence(Context context) { 123 String desc = KeyMaps.toDescriptiveString(context, id); 124 if (desc != null) { 125 SpannableString result = new SpannableString(KeyMaps.toString(context, id)); 126 Object descSpan = new TtsSpan.TextBuilder(desc).build(); 127 result.setSpan(descSpan, 0, result.length(), Spanned.SPAN_EXCLUSIVE_EXCLUSIVE); 128 return result; 129 } else { 130 return KeyMaps.toString(context, id); 131 } 132 } 133 @Override 134 TokenKind kind() { return TokenKind.OPERATOR; } 135 } 136 137 /** 138 * Representation of a (possibly incomplete) numerical constant. 139 * Supports addition and removal of trailing characters; hence mutable. 140 */ 141 private static class Constant extends Token implements Cloneable { 142 private boolean mSawDecimal; 143 private String mWhole; // String preceding decimal point. 144 private String mFraction; // String after decimal point. 145 private int mExponent; // Explicit exponent, only generated through addExponent. 146 private static int SAW_DECIMAL = 0x1; 147 private static int HAS_EXPONENT = 0x2; 148 149 Constant() { 150 mWhole = ""; 151 mFraction = ""; 152 // mSawDecimal = false; 153 // mExponent = 0; 154 }; 155 156 Constant(DataInput in) throws IOException { 157 mWhole = in.readUTF(); 158 byte flags = in.readByte(); 159 if ((flags & SAW_DECIMAL) != 0) { 160 mSawDecimal = true; 161 mFraction = in.readUTF(); 162 } else { 163 // mSawDecimal = false; 164 mFraction = ""; 165 } 166 if ((flags & HAS_EXPONENT) != 0) { 167 mExponent = in.readInt(); 168 } 169 } 170 171 @Override 172 void write(DataOutput out) throws IOException { 173 byte flags = (byte)((mSawDecimal ? SAW_DECIMAL : 0) 174 | (mExponent != 0 ? HAS_EXPONENT : 0)); 175 out.writeByte(TokenKind.CONSTANT.ordinal()); 176 out.writeUTF(mWhole); 177 out.writeByte(flags); 178 if (mSawDecimal) { 179 out.writeUTF(mFraction); 180 } 181 if (mExponent != 0) { 182 out.writeInt(mExponent); 183 } 184 } 185 186 // Given a button press, append corresponding digit. 187 // We assume id is a digit or decimal point. 188 // Just return false if this was the second (or later) decimal point 189 // in this constant. 190 // Assumes that this constant does not have an exponent. 191 public boolean add(int id) { 192 if (id == R.id.dec_point) { 193 if (mSawDecimal || mExponent != 0) return false; 194 mSawDecimal = true; 195 return true; 196 } 197 int val = KeyMaps.digVal(id); 198 if (mExponent != 0) { 199 if (Math.abs(mExponent) <= 10000) { 200 if (mExponent > 0) { 201 mExponent = 10 * mExponent + val; 202 } else { 203 mExponent = 10 * mExponent - val; 204 } 205 return true; 206 } else { // Too large; refuse 207 return false; 208 } 209 } 210 if (mSawDecimal) { 211 mFraction += val; 212 } else { 213 mWhole += val; 214 } 215 return true; 216 } 217 218 public void addExponent(int exp) { 219 // Note that adding a 0 exponent is a no-op. That's OK. 220 mExponent = exp; 221 } 222 223 /** 224 * Undo the last add or remove last exponent digit. 225 * Assumes the constant is nonempty. 226 */ 227 public void delete() { 228 if (mExponent != 0) { 229 mExponent /= 10; 230 // Once zero, it can only be added back with addExponent. 231 } else if (!mFraction.isEmpty()) { 232 mFraction = mFraction.substring(0, mFraction.length() - 1); 233 } else if (mSawDecimal) { 234 mSawDecimal = false; 235 } else { 236 mWhole = mWhole.substring(0, mWhole.length() - 1); 237 } 238 } 239 240 public boolean isEmpty() { 241 return (mSawDecimal == false && mWhole.isEmpty()); 242 } 243 244 /** 245 * Produce human-readable string representation of constant, as typed. 246 * We do add digit grouping separators to the whole number, even if not typed. 247 * Result is internationalized. 248 */ 249 @Override 250 public String toString() { 251 String result; 252 if (mExponent != 0) { 253 result = mWhole; 254 } else { 255 result = StringUtils.addCommas(mWhole, 0, mWhole.length()); 256 } 257 if (mSawDecimal) { 258 result += '.'; 259 result += mFraction; 260 } 261 if (mExponent != 0) { 262 result += "E" + mExponent; 263 } 264 return KeyMaps.translateResult(result); 265 } 266 267 /** 268 * Return BoundedRational representation of constant, if well-formed. 269 * Result is never null. 270 */ 271 public BoundedRational toRational() throws SyntaxException { 272 String whole = mWhole; 273 if (whole.isEmpty()) { 274 if (mFraction.isEmpty()) { 275 // Decimal point without digits. 276 throw new SyntaxException(); 277 } else { 278 whole = "0"; 279 } 280 } 281 BigInteger num = new BigInteger(whole + mFraction); 282 BigInteger den = BigInteger.TEN.pow(mFraction.length()); 283 if (mExponent > 0) { 284 num = num.multiply(BigInteger.TEN.pow(mExponent)); 285 } 286 if (mExponent < 0) { 287 den = den.multiply(BigInteger.TEN.pow(-mExponent)); 288 } 289 return new BoundedRational(num, den); 290 } 291 292 @Override 293 public CharSequence toCharSequence(Context context) { 294 return toString(); 295 } 296 297 @Override 298 public TokenKind kind() { 299 return TokenKind.CONSTANT; 300 } 301 302 // Override clone to make it public 303 @Override 304 public Object clone() { 305 Constant result = new Constant(); 306 result.mWhole = mWhole; 307 result.mFraction = mFraction; 308 result.mSawDecimal = mSawDecimal; 309 result.mExponent = mExponent; 310 return result; 311 } 312 } 313 314 /** 315 * The "token" class for previously evaluated subexpressions. 316 * We treat previously evaluated subexpressions as tokens. These are inserted when we either 317 * continue an expression after evaluating some of it, or copy an expression and paste it back 318 * in. 319 * This only contains enough information to allow us to display the expression in a 320 * formula, or reevaluate the expression with the aid of an ExprResolver; we no longer 321 * cache the result. The expression corresponding to the index can be obtained through 322 * the ExprResolver, which looks it up in a subexpression database. 323 * The representation includes a UnifiedReal value. In order to 324 * support saving and restoring, we also include the underlying expression itself, and the 325 * context (currently just degree mode) used to evaluate it. The short string representation 326 * is also stored in order to avoid potentially expensive recomputation in the UI thread. 327 */ 328 private static class PreEval extends Token { 329 public final long mIndex; 330 private final String mShortRep; // Not internationalized. 331 PreEval(long index, String shortRep) { 332 mIndex = index; 333 mShortRep = shortRep; 334 } 335 @Override 336 // This writes out only a shallow representation of the result, without 337 // information about subexpressions. To write out a deep representation, we 338 // find referenced subexpressions, and iteratively write those as well. 339 public void write(DataOutput out) throws IOException { 340 out.writeByte(TokenKind.PRE_EVAL.ordinal()); 341 if (mIndex > Integer.MAX_VALUE || mIndex < Integer.MIN_VALUE) { 342 // This would be millions of expressions per day for the life of the device. 343 throw new AssertionError("Expression index too big"); 344 } 345 out.writeInt((int)mIndex); 346 out.writeUTF(mShortRep); 347 } 348 PreEval(DataInput in) throws IOException { 349 mIndex = in.readInt(); 350 mShortRep = in.readUTF(); 351 } 352 @Override 353 public CharSequence toCharSequence(Context context) { 354 return KeyMaps.translateResult(mShortRep); 355 } 356 @Override 357 public TokenKind kind() { 358 return TokenKind.PRE_EVAL; 359 } 360 public boolean hasEllipsis() { 361 return mShortRep.lastIndexOf(KeyMaps.ELLIPSIS) != -1; 362 } 363 } 364 365 /** 366 * Read token from in. 367 */ 368 public static Token newToken(DataInput in) throws IOException { 369 byte kindByte = in.readByte(); 370 if (kindByte < 0x20) { 371 TokenKind kind = tokenKindValues[kindByte]; 372 switch(kind) { 373 case CONSTANT: 374 return new Constant(in); 375 case PRE_EVAL: 376 PreEval pe = new PreEval(in); 377 if (pe.mIndex == -1) { 378 // Database corrupted by earlier bug. 379 // Return a conspicuously wrong placeholder that won't lead to a crash. 380 Constant result = new Constant(); 381 result.add(R.id.dec_point); 382 return result; 383 } else { 384 return pe; 385 } 386 default: throw new IOException("Bad save file format"); 387 } 388 } else { 389 return new Operator(kindByte); 390 } 391 } 392 393 CalculatorExpr() { 394 mExpr = new ArrayList<Token>(); 395 } 396 397 private CalculatorExpr(ArrayList<Token> expr) { 398 mExpr = expr; 399 } 400 401 /** 402 * Construct CalculatorExpr, by reading it from in. 403 */ 404 CalculatorExpr(DataInput in) throws IOException { 405 mExpr = new ArrayList<Token>(); 406 int size = in.readInt(); 407 for (int i = 0; i < size; ++i) { 408 mExpr.add(newToken(in)); 409 } 410 } 411 412 /** 413 * Write this expression to out. 414 */ 415 public void write(DataOutput out) throws IOException { 416 int size = mExpr.size(); 417 out.writeInt(size); 418 for (int i = 0; i < size; ++i) { 419 mExpr.get(i).write(out); 420 } 421 } 422 423 /** 424 * Use write() above to generate a byte array containing a serialized representation of 425 * this expression. 426 */ 427 public byte[] toBytes() { 428 ByteArrayOutputStream byteArrayStream = new ByteArrayOutputStream(); 429 try (DataOutputStream out = new DataOutputStream(byteArrayStream)) { 430 write(out); 431 } catch (IOException e) { 432 // Impossible; No IO involved. 433 throw new AssertionError("Impossible IO exception", e); 434 } 435 return byteArrayStream.toByteArray(); 436 } 437 438 /** 439 * Does this expression end with a numeric constant? 440 * As opposed to an operator or preevaluated expression. 441 */ 442 boolean hasTrailingConstant() { 443 int s = mExpr.size(); 444 if (s == 0) { 445 return false; 446 } 447 Token t = mExpr.get(s-1); 448 return t instanceof Constant; 449 } 450 451 /** 452 * Does this expression end with a binary operator? 453 */ 454 boolean hasTrailingBinary() { 455 int s = mExpr.size(); 456 if (s == 0) return false; 457 Token t = mExpr.get(s-1); 458 if (!(t instanceof Operator)) return false; 459 Operator o = (Operator)t; 460 return (KeyMaps.isBinary(o.id)); 461 } 462 463 /** 464 * Append press of button with given id to expression. 465 * If the insertion would clearly result in a syntax error, either just return false 466 * and do nothing, or make an adjustment to avoid the problem. We do the latter only 467 * for unambiguous consecutive binary operators, in which case we delete the first 468 * operator. 469 */ 470 boolean add(int id) { 471 int s = mExpr.size(); 472 final int d = KeyMaps.digVal(id); 473 final boolean binary = KeyMaps.isBinary(id); 474 Token lastTok = s == 0 ? null : mExpr.get(s-1); 475 int lastOp = lastTok instanceof Operator ? ((Operator) lastTok).id : 0; 476 // Quietly replace a trailing binary operator with another one, unless the second 477 // operator is minus, in which case we just allow it as a unary minus. 478 if (binary && !KeyMaps.isPrefix(id)) { 479 if (s == 0 || lastOp == R.id.lparen || KeyMaps.isFunc(lastOp) 480 || KeyMaps.isPrefix(lastOp) && lastOp != R.id.op_sub) { 481 return false; 482 } 483 while (hasTrailingBinary()) { 484 delete(); 485 } 486 // s invalid and not used below. 487 } 488 final boolean isConstPiece = (d != KeyMaps.NOT_DIGIT || id == R.id.dec_point); 489 if (isConstPiece) { 490 // Since we treat juxtaposition as multiplication, a constant can appear anywhere. 491 if (s == 0) { 492 mExpr.add(new Constant()); 493 s++; 494 } else { 495 Token last = mExpr.get(s-1); 496 if(!(last instanceof Constant)) { 497 if (last instanceof PreEval) { 498 // Add explicit multiplication to avoid confusing display. 499 mExpr.add(new Operator(R.id.op_mul)); 500 s++; 501 } 502 mExpr.add(new Constant()); 503 s++; 504 } 505 } 506 return ((Constant)(mExpr.get(s-1))).add(id); 507 } else { 508 mExpr.add(new Operator(id)); 509 return true; 510 } 511 } 512 513 /** 514 * Add exponent to the constant at the end of the expression. 515 * Assumes there is a constant at the end of the expression. 516 */ 517 void addExponent(int exp) { 518 Token lastTok = mExpr.get(mExpr.size() - 1); 519 ((Constant) lastTok).addExponent(exp); 520 } 521 522 /** 523 * Remove trailing op_add and op_sub operators. 524 */ 525 void removeTrailingAdditiveOperators() { 526 while (true) { 527 int s = mExpr.size(); 528 if (s == 0) { 529 break; 530 } 531 Token lastTok = mExpr.get(s-1); 532 if (!(lastTok instanceof Operator)) { 533 break; 534 } 535 int lastOp = ((Operator) lastTok).id; 536 if (lastOp != R.id.op_add && lastOp != R.id.op_sub) { 537 break; 538 } 539 delete(); 540 } 541 } 542 543 /** 544 * Append the contents of the argument expression. 545 * It is assumed that the argument expression will not change, and thus its pieces can be 546 * reused directly. 547 */ 548 public void append(CalculatorExpr expr2) { 549 int s = mExpr.size(); 550 int s2 = expr2.mExpr.size(); 551 // Check that we're not concatenating Constant or PreEval tokens, since the result would 552 // look like a single constant, with very mysterious results for the user. 553 if (s != 0 && s2 != 0) { 554 Token last = mExpr.get(s-1); 555 Token first = expr2.mExpr.get(0); 556 if (!(first instanceof Operator) && !(last instanceof Operator)) { 557 // Fudge it by adding an explicit multiplication. We would have interpreted it as 558 // such anyway, and this makes it recognizable to the user. 559 mExpr.add(new Operator(R.id.op_mul)); 560 } 561 } 562 for (int i = 0; i < s2; ++i) { 563 mExpr.add(expr2.mExpr.get(i)); 564 } 565 } 566 567 /** 568 * Undo the last key addition, if any. 569 * Or possibly remove a trailing exponent digit. 570 */ 571 public void delete() { 572 final int s = mExpr.size(); 573 if (s == 0) { 574 return; 575 } 576 Token last = mExpr.get(s-1); 577 if (last instanceof Constant) { 578 Constant c = (Constant)last; 579 c.delete(); 580 if (!c.isEmpty()) { 581 return; 582 } 583 } 584 mExpr.remove(s-1); 585 } 586 587 /** 588 * Remove all tokens from the expression. 589 */ 590 public void clear() { 591 mExpr.clear(); 592 } 593 594 public boolean isEmpty() { 595 return mExpr.isEmpty(); 596 } 597 598 /** 599 * Returns a logical deep copy of the CalculatorExpr. 600 * Operator and PreEval tokens are immutable, and thus aren't really copied. 601 */ 602 public Object clone() { 603 CalculatorExpr result = new CalculatorExpr(); 604 for (Token t : mExpr) { 605 if (t instanceof Constant) { 606 result.mExpr.add((Token)(((Constant)t).clone())); 607 } else { 608 result.mExpr.add(t); 609 } 610 } 611 return result; 612 } 613 614 // Am I just a constant? 615 public boolean isConstant() { 616 if (mExpr.size() != 1) { 617 return false; 618 } 619 return mExpr.get(0) instanceof Constant; 620 } 621 622 /** 623 * Return a new expression consisting of a single token representing the current pre-evaluated 624 * expression. 625 * The caller supplies the expression index and short string representation. 626 * The expression must have been previously evaluated. 627 */ 628 public CalculatorExpr abbreviate(long index, String sr) { 629 CalculatorExpr result = new CalculatorExpr(); 630 @SuppressWarnings("unchecked") 631 Token t = new PreEval(index, sr); 632 result.mExpr.add(t); 633 return result; 634 } 635 636 /** 637 * Internal evaluation functions return an EvalRet pair. 638 * We compute rational (BoundedRational) results when possible, both as a performance 639 * optimization, and to detect errors exactly when we can. 640 */ 641 private static class EvalRet { 642 public int pos; // Next position (expression index) to be parsed. 643 public final UnifiedReal val; // Constructive Real result of evaluating subexpression. 644 EvalRet(int p, UnifiedReal v) { 645 pos = p; 646 val = v; 647 } 648 } 649 650 /** 651 * Internal evaluation functions take an EvalContext argument. 652 */ 653 private static class EvalContext { 654 public final int mPrefixLength; // Length of prefix to evaluate. Not explicitly saved. 655 public final boolean mDegreeMode; 656 public final ExprResolver mExprResolver; // Reconstructed, not saved. 657 // If we add any other kinds of evaluation modes, they go here. 658 EvalContext(boolean degreeMode, int len, ExprResolver er) { 659 mDegreeMode = degreeMode; 660 mPrefixLength = len; 661 mExprResolver = er; 662 } 663 EvalContext(DataInput in, int len, ExprResolver er) throws IOException { 664 mDegreeMode = in.readBoolean(); 665 mPrefixLength = len; 666 mExprResolver = er; 667 } 668 void write(DataOutput out) throws IOException { 669 out.writeBoolean(mDegreeMode); 670 } 671 } 672 673 private UnifiedReal toRadians(UnifiedReal x, EvalContext ec) { 674 if (ec.mDegreeMode) { 675 return x.multiply(UnifiedReal.RADIANS_PER_DEGREE); 676 } else { 677 return x; 678 } 679 } 680 681 private UnifiedReal fromRadians(UnifiedReal x, EvalContext ec) { 682 if (ec.mDegreeMode) { 683 return x.divide(UnifiedReal.RADIANS_PER_DEGREE); 684 } else { 685 return x; 686 } 687 } 688 689 // The following methods can all throw IndexOutOfBoundsException in the event of a syntax 690 // error. We expect that to be caught in eval below. 691 692 private boolean isOperatorUnchecked(int i, int op) { 693 Token t = mExpr.get(i); 694 if (!(t instanceof Operator)) { 695 return false; 696 } 697 return ((Operator)(t)).id == op; 698 } 699 700 private boolean isOperator(int i, int op, EvalContext ec) { 701 if (i >= ec.mPrefixLength) { 702 return false; 703 } 704 return isOperatorUnchecked(i, op); 705 } 706 707 public static class SyntaxException extends Exception { 708 public SyntaxException() { 709 super(); 710 } 711 public SyntaxException(String s) { 712 super(s); 713 } 714 } 715 716 // The following functions all evaluate some kind of expression starting at position i in 717 // mExpr in a specified evaluation context. They return both the expression value (as 718 // constructive real and, if applicable, as BoundedRational) and the position of the next token 719 // that was not used as part of the evaluation. 720 // This is essentially a simple recursive descent parser combined with expression evaluation. 721 722 private EvalRet evalUnary(int i, EvalContext ec) throws SyntaxException { 723 final Token t = mExpr.get(i); 724 if (t instanceof Constant) { 725 Constant c = (Constant)t; 726 return new EvalRet(i+1,new UnifiedReal(c.toRational())); 727 } 728 if (t instanceof PreEval) { 729 final long index = ((PreEval)t).mIndex; 730 UnifiedReal res = ec.mExprResolver.getResult(index); 731 if (res == null) { 732 // We try to minimize this recursive evaluation case, but currently don't 733 // completely avoid it. 734 res = nestedEval(index, ec.mExprResolver); 735 } 736 return new EvalRet(i+1, res); 737 } 738 EvalRet argVal; 739 switch(((Operator)(t)).id) { 740 case R.id.const_pi: 741 return new EvalRet(i+1, UnifiedReal.PI); 742 case R.id.const_e: 743 return new EvalRet(i+1, UnifiedReal.E); 744 case R.id.op_sqrt: 745 // Seems to have highest precedence. 746 // Does not add implicit paren. 747 // Does seem to accept a leading minus. 748 if (isOperator(i+1, R.id.op_sub, ec)) { 749 argVal = evalUnary(i+2, ec); 750 return new EvalRet(argVal.pos, argVal.val.negate().sqrt()); 751 } else { 752 argVal = evalUnary(i+1, ec); 753 return new EvalRet(argVal.pos, argVal.val.sqrt()); 754 } 755 case R.id.lparen: 756 argVal = evalExpr(i+1, ec); 757 if (isOperator(argVal.pos, R.id.rparen, ec)) { 758 argVal.pos++; 759 } 760 return new EvalRet(argVal.pos, argVal.val); 761 case R.id.fun_sin: 762 argVal = evalExpr(i+1, ec); 763 if (isOperator(argVal.pos, R.id.rparen, ec)) { 764 argVal.pos++; 765 } 766 return new EvalRet(argVal.pos, toRadians(argVal.val, ec).sin()); 767 case R.id.fun_cos: 768 argVal = evalExpr(i+1, ec); 769 if (isOperator(argVal.pos, R.id.rparen, ec)) { 770 argVal.pos++; 771 } 772 return new EvalRet(argVal.pos, toRadians(argVal.val,ec).cos()); 773 case R.id.fun_tan: 774 argVal = evalExpr(i+1, ec); 775 if (isOperator(argVal.pos, R.id.rparen, ec)) { 776 argVal.pos++; 777 } 778 UnifiedReal arg = toRadians(argVal.val, ec); 779 return new EvalRet(argVal.pos, arg.sin().divide(arg.cos())); 780 case R.id.fun_ln: 781 argVal = evalExpr(i+1, ec); 782 if (isOperator(argVal.pos, R.id.rparen, ec)) { 783 argVal.pos++; 784 } 785 return new EvalRet(argVal.pos, argVal.val.ln()); 786 case R.id.fun_exp: 787 argVal = evalExpr(i+1, ec); 788 if (isOperator(argVal.pos, R.id.rparen, ec)) { 789 argVal.pos++; 790 } 791 return new EvalRet(argVal.pos, argVal.val.exp()); 792 case R.id.fun_log: 793 argVal = evalExpr(i+1, ec); 794 if (isOperator(argVal.pos, R.id.rparen, ec)) { 795 argVal.pos++; 796 } 797 return new EvalRet(argVal.pos, argVal.val.ln().divide(UnifiedReal.TEN.ln())); 798 case R.id.fun_arcsin: 799 argVal = evalExpr(i+1, ec); 800 if (isOperator(argVal.pos, R.id.rparen, ec)) { 801 argVal.pos++; 802 } 803 return new EvalRet(argVal.pos, fromRadians(argVal.val.asin(), ec)); 804 case R.id.fun_arccos: 805 argVal = evalExpr(i+1, ec); 806 if (isOperator(argVal.pos, R.id.rparen, ec)) { 807 argVal.pos++; 808 } 809 return new EvalRet(argVal.pos, fromRadians(argVal.val.acos(), ec)); 810 case R.id.fun_arctan: 811 argVal = evalExpr(i+1, ec); 812 if (isOperator(argVal.pos, R.id.rparen, ec)) { 813 argVal.pos++; 814 } 815 return new EvalRet(argVal.pos, fromRadians(argVal.val.atan(),ec)); 816 default: 817 throw new SyntaxException("Unrecognized token in expression"); 818 } 819 } 820 821 private static final UnifiedReal ONE_HUNDREDTH = new UnifiedReal(100).inverse(); 822 823 private EvalRet evalSuffix(int i, EvalContext ec) throws SyntaxException { 824 final EvalRet tmp = evalUnary(i, ec); 825 int cpos = tmp.pos; 826 UnifiedReal val = tmp.val; 827 828 boolean isFact; 829 boolean isSquared = false; 830 while ((isFact = isOperator(cpos, R.id.op_fact, ec)) || 831 (isSquared = isOperator(cpos, R.id.op_sqr, ec)) || 832 isOperator(cpos, R.id.op_pct, ec)) { 833 if (isFact) { 834 val = val.fact(); 835 } else if (isSquared) { 836 val = val.multiply(val); 837 } else /* percent */ { 838 val = val.multiply(ONE_HUNDREDTH); 839 } 840 ++cpos; 841 } 842 return new EvalRet(cpos, val); 843 } 844 845 private EvalRet evalFactor(int i, EvalContext ec) throws SyntaxException { 846 final EvalRet result1 = evalSuffix(i, ec); 847 int cpos = result1.pos; // current position 848 UnifiedReal val = result1.val; // value so far 849 if (isOperator(cpos, R.id.op_pow, ec)) { 850 final EvalRet exp = evalSignedFactor(cpos + 1, ec); 851 cpos = exp.pos; 852 val = val.pow(exp.val); 853 } 854 return new EvalRet(cpos, val); 855 } 856 857 private EvalRet evalSignedFactor(int i, EvalContext ec) throws SyntaxException { 858 final boolean negative = isOperator(i, R.id.op_sub, ec); 859 int cpos = negative ? i + 1 : i; 860 EvalRet tmp = evalFactor(cpos, ec); 861 cpos = tmp.pos; 862 final UnifiedReal result = negative ? tmp.val.negate() : tmp.val; 863 return new EvalRet(cpos, result); 864 } 865 866 private boolean canStartFactor(int i) { 867 if (i >= mExpr.size()) return false; 868 Token t = mExpr.get(i); 869 if (!(t instanceof Operator)) return true; 870 int id = ((Operator)(t)).id; 871 if (KeyMaps.isBinary(id)) return false; 872 switch (id) { 873 case R.id.op_fact: 874 case R.id.rparen: 875 return false; 876 default: 877 return true; 878 } 879 } 880 881 private EvalRet evalTerm(int i, EvalContext ec) throws SyntaxException { 882 EvalRet tmp = evalSignedFactor(i, ec); 883 boolean is_mul = false; 884 boolean is_div = false; 885 int cpos = tmp.pos; // Current position in expression. 886 UnifiedReal val = tmp.val; // Current value. 887 while ((is_mul = isOperator(cpos, R.id.op_mul, ec)) 888 || (is_div = isOperator(cpos, R.id.op_div, ec)) 889 || canStartFactor(cpos)) { 890 if (is_mul || is_div) ++cpos; 891 tmp = evalSignedFactor(cpos, ec); 892 if (is_div) { 893 val = val.divide(tmp.val); 894 } else { 895 val = val.multiply(tmp.val); 896 } 897 cpos = tmp.pos; 898 is_mul = is_div = false; 899 } 900 return new EvalRet(cpos, val); 901 } 902 903 /** 904 * Is the subexpression starting at pos a simple percent constant? 905 * This is used to recognize exppressions like 200+10%, which we handle specially. 906 * This is defined as a Constant or PreEval token, followed by a percent sign, and followed 907 * by either nothing or an additive operator. 908 * Note that we are intentionally far more restrictive in recognizing such expressions than 909 * e.g. http://blogs.msdn.com/b/oldnewthing/archive/2008/01/10/7047497.aspx . 910 * When in doubt, we fall back to the the naive interpretation of % as 1/100. 911 * Note that 100+(10)% yields 100.1 while 100+10% yields 110. This may be controversial, 912 * but is consistent with Google web search. 913 */ 914 private boolean isPercent(int pos) { 915 if (mExpr.size() < pos + 2 || !isOperatorUnchecked(pos + 1, R.id.op_pct)) { 916 return false; 917 } 918 Token number = mExpr.get(pos); 919 if (number instanceof Operator) { 920 return false; 921 } 922 if (mExpr.size() == pos + 2) { 923 return true; 924 } 925 if (!(mExpr.get(pos + 2) instanceof Operator)) { 926 return false; 927 } 928 Operator op = (Operator) mExpr.get(pos + 2); 929 return op.id == R.id.op_add || op.id == R.id.op_sub || op.id == R.id.rparen; 930 } 931 932 /** 933 * Compute the multiplicative factor corresponding to an N% addition or subtraction. 934 * @param pos position of Constant or PreEval expression token corresponding to N. 935 * @param isSubtraction this is a subtraction, as opposed to addition. 936 * @param ec usable evaluation contex; only length matters. 937 * @return UnifiedReal value and position, which is pos + 2, i.e. after percent sign 938 */ 939 private EvalRet getPercentFactor(int pos, boolean isSubtraction, EvalContext ec) 940 throws SyntaxException { 941 EvalRet tmp = evalUnary(pos, ec); 942 UnifiedReal val = isSubtraction ? tmp.val.negate() : tmp.val; 943 val = UnifiedReal.ONE.add(val.multiply(ONE_HUNDREDTH)); 944 return new EvalRet(pos + 2 /* after percent sign */, val); 945 } 946 947 private EvalRet evalExpr(int i, EvalContext ec) throws SyntaxException { 948 EvalRet tmp = evalTerm(i, ec); 949 boolean is_plus; 950 int cpos = tmp.pos; 951 UnifiedReal val = tmp.val; 952 while ((is_plus = isOperator(cpos, R.id.op_add, ec)) 953 || isOperator(cpos, R.id.op_sub, ec)) { 954 if (isPercent(cpos + 1)) { 955 tmp = getPercentFactor(cpos + 1, !is_plus, ec); 956 val = val.multiply(tmp.val); 957 } else { 958 tmp = evalTerm(cpos + 1, ec); 959 if (is_plus) { 960 val = val.add(tmp.val); 961 } else { 962 val = val.subtract(tmp.val); 963 } 964 } 965 cpos = tmp.pos; 966 } 967 return new EvalRet(cpos, val); 968 } 969 970 /** 971 * Return the starting position of the sequence of trailing binary operators. 972 */ 973 private int trailingBinaryOpsStart() { 974 int result = mExpr.size(); 975 while (result > 0) { 976 Token last = mExpr.get(result - 1); 977 if (!(last instanceof Operator)) break; 978 Operator o = (Operator)last; 979 if (!KeyMaps.isBinary(o.id)) break; 980 --result; 981 } 982 return result; 983 } 984 985 /** 986 * Is the current expression worth evaluating? 987 */ 988 public boolean hasInterestingOps() { 989 final int last = trailingBinaryOpsStart(); 990 int first = 0; 991 if (last > first && isOperatorUnchecked(first, R.id.op_sub)) { 992 // Leading minus is not by itself interesting. 993 first++; 994 } 995 for (int i = first; i < last; ++i) { 996 Token t1 = mExpr.get(i); 997 if (t1 instanceof Operator 998 || t1 instanceof PreEval && ((PreEval)t1).hasEllipsis()) { 999 return true; 1000 } 1001 } 1002 return false; 1003 } 1004 1005 /** 1006 * Does the expression contain trig operations? 1007 */ 1008 public boolean hasTrigFuncs() { 1009 for (Token t : mExpr) { 1010 if (t instanceof Operator) { 1011 Operator o = (Operator)t; 1012 if (KeyMaps.isTrigFunc(o.id)) { 1013 return true; 1014 } 1015 } 1016 } 1017 return false; 1018 } 1019 1020 /** 1021 * Add the indices of unevaluated PreEval expressions embedded in the current expression to 1022 * argument. This includes only directly referenced expressions e, not those indirectly 1023 * referenced by e. If the index was already present, it is not added. If the argument 1024 * contained no duplicates, the result will not either. New indices are added to the end of 1025 * the list. 1026 */ 1027 private void addReferencedExprs(ArrayList<Long> list, ExprResolver er) { 1028 for (Token t : mExpr) { 1029 if (t instanceof PreEval) { 1030 Long index = ((PreEval) t).mIndex; 1031 if (er.getResult(index) == null && !list.contains(index)) { 1032 list.add(index); 1033 } 1034 } 1035 } 1036 } 1037 1038 /** 1039 * Return a list of unevaluated expressions transitively referenced by the current one. 1040 * All expressions in the resulting list will have had er.getExpr() called on them. 1041 * The resulting list is ordered such that evaluating expressions in list order 1042 * should trigger few recursive evaluations. 1043 */ 1044 public ArrayList<Long> getTransitivelyReferencedExprs(ExprResolver er) { 1045 // We could avoid triggering any recursive evaluations by actually building the 1046 // dependency graph and topologically sorting it. Note that sorting by index works 1047 // for positive and negative indices separately, but not their union. Currently we 1048 // just settle for reverse breadth-first-search order, which handles the common case 1049 // of simple dependency chains well. 1050 ArrayList<Long> list = new ArrayList<Long>(); 1051 int scanned = 0; // We've added expressions referenced by [0, scanned) to the list 1052 addReferencedExprs(list, er); 1053 while (scanned != list.size()) { 1054 er.getExpr(list.get(scanned++)).addReferencedExprs(list, er); 1055 } 1056 Collections.reverse(list); 1057 return list; 1058 } 1059 1060 /** 1061 * Evaluate the expression at the given index to a UnifiedReal. 1062 * Both saves and returns the result. 1063 */ 1064 UnifiedReal nestedEval(long index, ExprResolver er) throws SyntaxException { 1065 CalculatorExpr nestedExpr = er.getExpr(index); 1066 EvalContext newEc = new EvalContext(er.getDegreeMode(index), 1067 nestedExpr.trailingBinaryOpsStart(), er); 1068 EvalRet new_res = nestedExpr.evalExpr(0, newEc); 1069 return er.putResultIfAbsent(index, new_res.val); 1070 } 1071 1072 /** 1073 * Evaluate the expression excluding trailing binary operators. 1074 * Errors result in exceptions, most of which are unchecked. Should not be called 1075 * concurrently with modification of the expression. May take a very long time; avoid calling 1076 * from UI thread. 1077 * 1078 * @param degreeMode use degrees rather than radians 1079 */ 1080 UnifiedReal eval(boolean degreeMode, ExprResolver er) throws SyntaxException 1081 // And unchecked exceptions thrown by UnifiedReal, CR, 1082 // and BoundedRational. 1083 { 1084 // First evaluate all indirectly referenced expressions in increasing index order. 1085 // This ensures that subsequent evaluation never encounters an embedded PreEval 1086 // expression that has not been previously evaluated. 1087 // We could do the embedded evaluations recursively, but that risks running out of 1088 // stack space. 1089 ArrayList<Long> referenced = getTransitivelyReferencedExprs(er); 1090 for (long index : referenced) { 1091 nestedEval(index, er); 1092 } 1093 try { 1094 // We currently never include trailing binary operators, but include other trailing 1095 // operators. Thus we usually, but not always, display results for prefixes of valid 1096 // expressions, and don't generate an error where we previously displayed an instant 1097 // result. This reflects the Android L design. 1098 int prefixLen = trailingBinaryOpsStart(); 1099 EvalContext ec = new EvalContext(degreeMode, prefixLen, er); 1100 EvalRet res = evalExpr(0, ec); 1101 if (res.pos != prefixLen) { 1102 throw new SyntaxException("Failed to parse full expression"); 1103 } 1104 return res.val; 1105 } catch (IndexOutOfBoundsException e) { 1106 throw new SyntaxException("Unexpected expression end"); 1107 } 1108 } 1109 1110 // Produce a string representation of the expression itself 1111 SpannableStringBuilder toSpannableStringBuilder(Context context) { 1112 SpannableStringBuilder ssb = new SpannableStringBuilder(); 1113 for (Token t : mExpr) { 1114 ssb.append(t.toCharSequence(context)); 1115 } 1116 return ssb; 1117 } 1118 } 1119
