Bug#93665: xbase-clients: [xcalc] uses wrong order of operations in infix mode
Tags: patch
Yes, the infix operand logic was broken. It seems that it attempts to
follow Dijkstra's Shunting Yard infix-to-postfix conversion algorithm
like this: http://www.chris-j.co.uk/parsing.php judging by the code
structure. However, to actually follow it, twoop() should have carried
out all stacked operations up to and including those with the same
priority in a loop, but it didn't.
I've re-factored the code to do that kind of stack operations in a
single function, to make the algorithm easier to follow and maintain.
I've made power evaluation work right-to-left as is conventional, so for
example 2, y^x, 3, y^x, 2 gives 512, i.e. 2^(3^2), not 64 which is
(2^3)^2. The rest work left-to-right as expected and are evaluated on
the fly where possible.
I've tried to respect the code style as much as I could, in the hope
that the code doesn't look like a mixture of styles. Not sure how good
an idea that was.
Pedro Gimeno Fortea
--- xcalc/math.c~ 2012-06-07 11:38:25.000000000 +0200
+++ xcalc/math.c 2014-06-11 19:03:57.000000000 +0200
@@ -14,6 +14,8 @@
* Beware the HP functions: there are still errors here.
*
* Geoffrey Coram fixed most of the HP mode bugs.
+ *
+ * Pedro Gimeno Fortea fixed a long-standing infix mode precedence bug.
*/
#include "xcalc.h"
@@ -304,6 +306,44 @@ numeric(int keynum)
lift_enabled = 0;
}
+static void
+calc_to_op_priority(int op)
+{
+ /* perform stacked operations of all operands of same or more priority
+ (end of stack has least priority of all) */
+
+ int pri = priority(op);
+#ifdef DEBUG
+ showstack("op_priority begin");
+#endif
+
+ dnum = PopNum();
+ while (!isopempty()) {
+ lastop = PopOp();
+ if (priority(lastop) < pri) { PushOp(lastop); break; }
+
+ if (lastop != kLPAR) acc = PopNum(); /* LPAR is not two-op */
+
+ switch (lastop) {
+ case kADD: acc += dnum; break;
+ case kSUB: acc -= dnum; break;
+ case kMUL: acc *= dnum; break;
+ case kDIV: acc /= dnum; break;
+ case kPOW: acc = pow(acc, dnum); break;
+ case kLPAR: --flagPAREN; acc = dnum; break;
+ }
+ dnum=acc;
+
+ /* as a special case, RPAR also stops processing at latest LPAR */
+ if (lastop == kLPAR && op == kRPAR) break;
+ }
+ PushNum(dnum);
+
+#ifdef DEBUG
+ showstack("op_priority end");
+#endif
+}
+
void
bkspf(void)
{
@@ -444,54 +484,23 @@ twoop(int keynum)
PushOp(keynum); /* with the new one */
return;
}
-
+
if (entered==1)
parse_double(dispstr,"%lf",&dnum);
clrdisp=CLR=1;
entered=Dpoint=exponent=0;
- if (!isopempty()) { /* there was a previous op */
- lastop=PopOp(); /* get it */
+ PushNum(dnum);
- if (lastop==kLPAR) { /* put it back */
- PushOp(kLPAR);
- PushOp(keynum);
- PushNum(dnum);
- return;
- }
+ if (keynum != kPOW) /* Power precedence is right to left */
+ if (!isopempty())
+ calc_to_op_priority(keynum);
- /* now, if the current op (keynum) is of
- higher priority than the lastop, the current
- op and number are just pushed on top
- Priorities: (Y^X) > *,/ > +,- */
-
- if (priority(keynum) > priority(lastop)) {
- PushNum(dnum);
- PushOp(lastop);
- PushOp(keynum);
- } else { /* execute lastop on lastnum and dnum, push
- result and current op on stack */
- acc=PopNum();
- switch (lastop) { /* perform the operation */
- case kADD: acc += dnum; break;
- case kSUB: acc -= dnum; break;
- case kMUL: acc *= dnum; break;
- case kDIV: acc /= dnum; break;
- case kPOW: acc = pow(acc,dnum); break;
- }
- PushNum(acc);
- PushOp(keynum);
- sprintf(dispstr,"%.8g",acc);
- DrawDisplay();
- dnum=acc;
- }
- }
- else { /* op stack is empty, push op and num */
- PushOp(keynum);
- PushNum(dnum);
- }
-}
+ PushOp(keynum);
+ sprintf(dispstr,"%.8g",dnum);
+ DrawDisplay();
+}
/* Two operand functions for rpn calc */
void
@@ -557,28 +566,9 @@ equf(void)
PushNum(dnum);
- while (!isopempty()) { /* do all pending ops */
- dnum=PopNum();
- acc=PopNum();
- lastop=PopOp();
- switch (lastop) {
- case kADD: acc += dnum;
- break;
- case kSUB: acc -= dnum;
- break;
- case kMUL: acc *= dnum;
- break;
- case kDIV: acc /= dnum;
- break;
- case kPOW: acc = pow(acc,dnum);
- break;
- case kLPAR: flagPAREN--;
- PushNum(acc);
- break;
- }
- dnum=acc;
- PushNum(dnum);
- }
+/* while (flagPAREN) calc_to_op_priority(kRPAR);*/
+ calc_to_op_priority(-1);
+ dnum=PopNum();
sprintf(dispstr,"%.8g",dnum);
DrawDisplay();
@@ -618,36 +608,17 @@ rparf(void)
if (!flagPAREN)
return;
-
+
clrdisp++;
Dpoint=exponent=0;
if (entered==1)
parse_double(dispstr,"%lf",&dnum);
- entered=2;
PushNum(dnum);
- while (!isopempty() && (lastop=PopOp())!=kLPAR) {
- /* do all pending ops, back to left paren */
- dnum=PopNum();
- acc=PopNum();
- switch (lastop) {
- case kADD: acc += dnum;
- break;
- case kSUB: acc -= dnum;
- break;
- case kMUL: acc *= dnum;
- break;
- case kDIV: acc /= dnum;
- break;
- case kPOW: acc = pow(acc,dnum);
- break;
- }
- dnum=acc;
- PushNum(dnum);
- }
- (void) PopNum();
- flagPAREN--;
+ calc_to_op_priority(kRPAR);
+ dnum = PopNum();
+
entered=2;
sprintf(dispstr,"%.8g",dnum);
DrawDisplay();
@@ -828,8 +799,19 @@ isopempty(void)
static void
showstack(char *string)
{
+ if (rpn)
fprintf(stderr, "%s: %lf %lf %lf\n", string, numstack[0], numstack[1],
numstack[2]);
+ else {
+ int i;
+ fprintf(stderr, "%s\nnumstack:", string);
+ for (i = 0; i < numsp; ++i)
+ fprintf(stderr, " %g", numstack[i]);
+ fprintf(stderr, "\nopstack:");
+ for (i = 0; i < opsp; ++i)
+ fprintf(stderr, " %d", opstack[i]);
+ fprintf(stderr, "\ndnum=%g\n", dnum);
+ }
}
#endif
@@ -910,13 +892,15 @@ priority(int op)
/*******/
{
switch (op) {
- case kPOW: return(2);
+ case kPOW: return(3);
case kMUL:
- case kDIV: return(1);
+ case kDIV: return(2);
case kADD:
- case kSUB: return(0);
+ case kSUB: return(1);
+ case kLPAR:
+ case kRPAR: return(0);
}
- return 0;
+ return -1;
}
Reply to: