Parsegen can now run concurrently with itself, w00t

[grinvader]

Oops, NAND you're right :P

Well in that case, x^^y == !x != !y.

You're trying too hard...

Code: Select all

NAND|0 1
----+---
   0|1 1
   1|1 0

x !& y = !(x&&y)

And using your model, but simpler, XOR: x^^y = (bool)x != (bool)y

[byuu]

I don't consider typecasting any simpler, but whatever. Adding NAND in there was a joke. "(n)and you're right". Nevermind. I need to just kill my sense of humor already, since nobody ever follows.

[grinvader]

I apologize for missing the joke. ;_;
Logic gates has that effect on my joke detector, sorry again.

[byuu]

That's ok. I like your !& syntax. But I'm thinking, we need bitwise as !& and logical as !&&. Ok then, should we just add all possible logical operators for fun?

[ bitwise, logical ] x [ AND, OR, XOR, NAND, NOR, NOT, XNOR ] *

Can't imagine they'd be at all useful, but hey. I extended sprintf when I rewrote that, so why not math expressions, as well?

* Some may not work as logical.

[DataPath]

you forgot NNOT

[gladius]

byuu: Oops, you are right, the way it's currently done a comparison is assumed to be a ternary expression. To fix that you can add specific handling for the ? operator, and just make it do the zero = false, non-zero = true in the same way C does it. Comparisons would evaluate to zero and one then. That should actually simplify things a bit.

[adventure_of_link]

Nevermind. I need to just kill my sense of humor already, since nobody ever follows.

Eh, could be worse.

Example:

Code: Select all

<adventureoflink> How about DR F
<adventureoflink> All I want/need is DR F
<grinvader> DR == snes ratio
<adventureoflink> yeah, I know 
<grinvader> you can't do that with 1280x800
<grinvader> 1.6 ratio
<adventureoflink> ah
<adventureoflink> why not
<grinvader> because that's not how it works
<adventureoflink> oh ok.
<adventureoflink> So I'm stuck with DS
<adventureoflink> What, so I can't pick PSP ? :P
<grinvader> bad jokes won't help

[grinvader]

Why not, heh.

Bitwise:
AND: x & y
OR: x | y
XOR: x ^ y
NOT: ~x
NAND: ~(x & y)
NOR: ~(x | y)
XNOR: ~(x ^ y)

Logical:
AND: x && y
OR: x || y
XOR: (bool)x != (bool)y
NOT: !x
NAND: !(x && y)
NOR: !(x || y)
XNOR: (bool)x == (bool)y

There you go.
Btw, casts are in the worst case as fast as !-ing each param, since ! evaluates the param as a bool anyway in order to reverse it, heh.

[byuu]

byuu: Oops, you are right, the way it's currently done a comparison is assumed to be a ternary expression. To fix that you can add specific handling for the ? operator, and just make it do the zero = false, non-zero = true in the same way C does it. Comparisons would evaluate to zero and one then. That should actually simplify things a bit.

Yep, that's what I was trying but my code is returning incorrect results.
EDIT: found the problem. rhs already had the right-hand side of ?, so I just needed to call strmath_rdp one more time. Mostly finalized code :

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>

#define maxlevel 12
int strmath_rdp(const char *&s, int level = 0) {
  if(level == maxlevel) {
    if(*s == '(') {
    int result = strmath_rdp(++s, 0);
      s++;
      return result;
    } else if(*s == '+') {
      return +strmath_rdp(++s, maxlevel);
    } else if(*s == '-') {
      return -strmath_rdp(++s, maxlevel);
    } else if(*s == '!') {
      return !strmath_rdp(++s, maxlevel);
    } else if(*s == '~') {
      return ~strmath_rdp(++s, maxlevel);
    } else if(*s >= '0' && *s <= '9') {
    int num, len;
      sscanf(s, "%d%n", &num, &len);
      s += len;
      return num;
    }
  }

int lhs = strmath_rdp(s, level + 1);
  while(*s) {
  const char *org = s;
  int a = *org;
  int b = *org ? *(org + 1) : 0;
    switch(level) {
    case 0:
      if(a == '?')break;
      return lhs;
    case 1:
      if(a == '|' && b == '|') { s++; break; }
      return lhs;
    case 2:
      if(a == '^' && b == '^') { s++; break; }
      return lhs;
    case 3:
      if(a == '&' && b == '&') { s++; break; }
      return lhs;
    case 4:
      if(a == '|' && b != '|')break;
      return lhs;
    case 5:
      if(a == '^' && b != '^')break;
      return lhs;
    case 6:
      if(a == '&' && b != '&')break;
      return lhs;
    case 7:
      if(a == '=' && b == '=') { s++; break; }
      if(a == '!' && b == '=') { s++; break; }
      return lhs;
    case 8:
      if(a == '<' && b == '=') { s++; break; }
      if(a == '>' && b == '=') { s++; break; }
      if(a == '<')break;
      if(a == '>')break;
      return lhs;
    case 9:
      if(a == '<' && b == '<') { s++; break; }
      if(a == '>' && b == '>') { s++; break; }
      return lhs;
    case 10:
      if(a == '+')break;
      if(a == '-')break;
      return lhs;
    case 11:
      if(a == '*')break;
      if(a == '/')break;
      if(a == '%')break;
      return lhs;
    }
  int rhs = strmath_rdp(++s, level + 1);
    a = *org;
    b = *org ? *(org + 1) : 0;
    if(a == '?') {
    int tr = rhs;
    int fr = strmath_rdp(++s, level);
      lhs = (lhs) ? tr : fr;
    }
    else if(a == '|' && b == '|') lhs = (lhs || rhs);
    else if(a == '^' && b == '^') lhs = (!lhs != !rhs);
    else if(a == '&' && b == '&') lhs = (lhs && rhs);
    else if(a == '|' && b != '|') lhs |= rhs;
    else if(a == '^' && b != '^') lhs ^= rhs;
    else if(a == '&' && b != '&') lhs &= rhs;
    else if(a == '=' && b == '=') lhs = (lhs == rhs);
    else if(a == '!' && b == '=') lhs = (lhs != rhs);
    else if(a == '<' && b == '=') lhs = (lhs <= rhs);
    else if(a == '>' && b == '=') lhs = (lhs >= rhs);
    else if(a == '<' && b != '<') lhs = (lhs < rhs);
    else if(a == '>' && b != '>') lhs = (lhs > rhs);
    else if(a == '<' && b == '<') lhs <<= rhs;
    else if(a == '>' && b == '>') lhs >>= rhs;
    else if(a == '+')             lhs += rhs;
    else if(a == '-')             lhs -= rhs;
    else if(a == '*')             lhs *= rhs;
    else if(a == '/')             lhs /= rhs;
    else if(a == '%')             lhs %= rhs;
  }
  return lhs;
}
#undef maxlevel

int strmath(const char *eval) {
  return strmath_rdp(eval);
}

int main() {
  printf("%10s = %5d, %5d\n", "5+3*7",   strmath("5+3*7"),   5+3*7);
  printf("%10s = %5d, %5d\n", "+3-2",    strmath("+3-2"),    +3-2);
  printf("%10s = %5d, %5d\n", "0||1",    strmath("0||1"),    0||1);
  printf("%10s = %5d, %5d\n", "2==3",    strmath("2==3"),    2==3);
  printf("%10s = %5d, %5d\n", "!(3>=2)", strmath("!(3>=2)"), !(3>=2));
  printf("%10s = %5d, %5d\n", "2<<4",    strmath("2<<4"),    2<<4);
  printf("%10s = %5d, %5d\n", "1<2?3:4", strmath("1<2?3:4"), 1<2?3:4);
  printf("%10s = %5d, %5d\n", "1>2?3:4", strmath("1>2?3:4"), 1>2?3:4);
  printf("%10s = %5d, %5d\n", "1^^0",    strmath("1^^0"),    !1!=!0);

  getch();
  return 0;
}

Anything else we should add / optimize?

I added logical XOR because it just seemed like it should be there, since there's already a bitwise XOR. I didn't add NAND, NOR or XNOR since they can be done using existing operators ~() or !() and don't really add anything -- not to mention, I don't have good symbols to use for them anyway. XOR can be done using AND/OR/NOT, but eh. Everyone expects XOR to be there.

I'm thinking I will extend all int's to int64's for my strmath library. The only other thing to maybe add would be to convert int64's to floating point (double or long double, maybe?) and use a more adept function than sscanf to handle the different types of input.

Also, bad input can crash the program. A little error handling (even just bailing out with zero on failure) would probably be a good idea.

Btw, casts are in the worst case as fast as !-ing each param, since ! evaluates the param as a bool anyway in order to reverse it, heh.

Not on my Athlon 3500+. Example:
!!(x & 0x80) creates one more opcode than bool(x & 0x80), but the opcodes it chooses (sorry, not at home to run my disassembler and post them) end up running slower, at least on my CPU.
I know you're right for the most part. But it isn't always the case that compilers cast better. They should, and that's generally how I write my code.

But for this purpose, I think it's better to express the comparators as natural expressions that a CPU can do by using operators only and no casting. Eh, doesn't really matter either way.

[gladius]

byuu: Looks mostly good, but the problem is ternary does not evaluate right-to-left now which is the C spec. Here is the fixed code (the unit tests actually caught this error! "9>5?95>?1:0:4*2" was evaluating incorrectly). Also a tiny bit of cleanup, you don't need to re-cache a and b

Code: Select all

#define maxlevel 12 
int strmath_rdp(const char *&s, int level = 0) { 
  if(level == maxlevel) { 
    if(*s == '(') { 
    int result = strmath_rdp(++s, 0); 
      s++; 
      return result; 
    } else if(*s == '+') { 
      return +strmath_rdp(++s, maxlevel); 
    } else if(*s == '-') { 
      return -strmath_rdp(++s, maxlevel); 
    } else if(*s == '!') { 
      return !strmath_rdp(++s, maxlevel); 
    } else if(*s == '~') { 
      return ~strmath_rdp(++s, maxlevel); 
    } else if(*s >= '0' && *s <= '9') { 
    int num, len; 
      sscanf(s, "%d%n", &num, &len); 
      s += len; 
      return num; 
    } 
  } 

int lhs = strmath_rdp(s, level + 1); 
  while(*s) { 
  const char *org = s; 
  int a = *org; 
  int b = *org ? *(org + 1) : 0; 
    switch(level) { 
    case 0: 
      if(a == '?')break; 
      return lhs; 
    case 1: 
      if(a == '|' && b == '|') { s++; break; } 
      return lhs; 
    case 2: 
      if(a == '^' && b == '^') { s++; break; } 
      return lhs; 
    case 3: 
      if(a == '&' && b == '&') { s++; break; } 
      return lhs; 
    case 4: 
      if(a == '|' && b != '|')break; 
      return lhs; 
    case 5: 
      if(a == '^' && b != '^')break; 
      return lhs; 
    case 6: 
      if(a == '&' && b != '&')break; 
      return lhs; 
    case 7: 
      if(a == '=' && b == '=') { s++; break; } 
      if(a == '!' && b == '=') { s++; break; } 
      return lhs; 
    case 8: 
      if(a == '<' && b == '=') { s++; break; } 
      if(a == '>' && b == '=') { s++; break; } 
      if(a == '<')break; 
      if(a == '>')break; 
      return lhs; 
    case 9: 
      if(a == '<' && b == '<') { s++; break; } 
      if(a == '>' && b == '>') { s++; break; } 
      return lhs; 
    case 10: 
      if(a == '+')break; 
      if(a == '-')break; 
      return lhs; 
    case 11: 
      if(a == '*')break; 
      if(a == '/')break; 
      if(a == '%')break; 
      return lhs; 
    } 
    if(a == '?') { 
    int tr = strmath_rdp(++s, 0); 
    int fr = strmath_rdp(++s, 0); 
      lhs = (lhs) ? tr : fr; 
	} else { 
	  int rhs = strmath_rdp(++s, level + 1); 
    if(a == '|' && b == '|') lhs = (lhs || rhs); 
    else if(a == '^' && b == '^') lhs = (!lhs != !rhs); 
    else if(a == '&' && b == '&') lhs = (lhs && rhs); 
    else if(a == '|' && b != '|') lhs |= rhs; 
    else if(a == '^' && b != '^') lhs ^= rhs; 
    else if(a == '&' && b != '&') lhs &= rhs; 
    else if(a == '=' && b == '=') lhs = (lhs == rhs); 
    else if(a == '!' && b == '=') lhs = (lhs != rhs); 
    else if(a == '<' && b == '=') lhs = (lhs <= rhs); 
    else if(a == '>' && b == '=') lhs = (lhs >= rhs); 
    else if(a == '<' && b != '<') lhs = (lhs < rhs); 
    else if(a == '>' && b != '>') lhs = (lhs > rhs); 
    else if(a == '<' && b == '<') lhs <<= rhs; 
    else if(a == '>' && b == '>') lhs >>= rhs; 
    else if(a == '+')             lhs += rhs; 
    else if(a == '-')             lhs -= rhs; 
    else if(a == '*')             lhs *= rhs; 
    else if(a == '/')             lhs /= rhs; 
    else if(a == '%')             lhs %= rhs; 
  } 
  }
  return lhs; 
} 
#undef maxlevel 

int strmath(const char *eval) { 
  return strmath_rdp(eval); 
} 

[byuu]

int tr = strmath_rdp(++s, 0);
int fr = strmath_rdp(++s, 0);

Is it level 0 or the current level?

[gladius]

0 is (edit: not) correct. (edit: bogus example was used here)

Edit: You are correct, it should be level, not 0 (but not level+1, that would lose the right-to-left evaluation property).

[funkyass]

now, add support for reverse polish notation.

[gladius]

They are not exactly compatible grammar wise . Besides reverse polish notation is trivially implemented with a simple recursive function. No need for this recursive descent trickiness.