parse_term.cc

Go to the documentation of this file.

#include "numbpart.cc" /* for calculation of partition numbers */


namespace parse_term
{

signed short int gZ_priority (const char ch)
{
  switch (ch)
   {
     case '+': case '-': return 1;
     case '*': case '/': case ':': case '%': return 2;
     case '^': return 3;
     default: return 0;
   } 
}

bool gZ_mehrstellig(const char ch)
{
  switch (ch)
   {
     case '+': case '-':
     case '*': case '/': case ':': case '%':
     case '^':
      return true;
     default: return false;
   } 
}

bool gZ_einstellig(const char ch)
{
  switch (ch)
   {
     case 'F': case 'L': case 'P':
     case 'f': case 'p': case 's':
     case 'q': case 'i': case 'd':
     case 'r':
      /*
         F - index of Fibonacci number
         L - index of Luscas number
         P - index of Partition number
         f - evaluates factorial of the given argument
         p - evaluates the next greater prime number (if argument isn't prime)
         s - evaluates the next greater safeprime (if argument isn't safeprime)
         q - tests, whether argument is a prime number. If not: abort program.
             (this is useful for some loops in scripts calling this program)
         i - increment argument by one
         d - decrement argument by one
         r - square root (truncated)
      */
      return true;
    default: return false;
   }
}

bool gZ_priority_le (const char a, const char b)
{
  return gZ_priority(a)<=gZ_priority(b);
}

bool gZ_priority_gr (const char a, const char b)
{
  return gZ_priority(a)>gZ_priority(b);
}

bool get_number (mpz_t n, char* &s, const char op='R', const char upto_op='\0')
{ 
  /*
     Evaluate the string (array of chars) to a multiple precision number.
     The string will be interpreted as a term consisting of numbers,
     numeric expressions, parentheses and operation symbols.
  */
  
  while (s[0]==' ') s++; // read over spaces
  
  bool term_structure_ok = true;
  char* s_anf = s; // starting position of the current subterm
  char h;
  mpz_t tmp;
  mpz_init(tmp);

  if (s[0]=='(')
    {
      s++; // skip leading parenthesis
      term_structure_ok=get_number(tmp,s); // evaluate subterm
      if (s[0]==')') s++; // skip trailing parenthesis
      else 
        {
          term_structure_ok=false;
          cerr << "error: ')' expected at '" << s << "'" << endl; 
        }
    }
  else if (gZ_einstellig(s[0])) // einstellige Funktionssymbole
    {
      s++; // skip the function symbol
      term_structure_ok=get_number(tmp,s,s_anf[0]); // evaluate term (as an argument)
    }
  else if (s[0]>='0' && s[0]<='9')
    { // get subterm (parentheses need be removed beforehand)
      char* anf=s;
      while (s[0]>='0' && s[0]<='9') s++;
      h=s[0]; s[0]='\0';
      if (mpz_set_str(tmp, anf, 10))
        {
          term_structure_ok=false;
          s[0]=h;
          cerr << "error: number expected at '" << anf << "'" << endl;
        }
      s[0]=h;
    }
  else term_structure_ok=false;

  while (s[0]==' ') s++; // over read spaces
  if (s[0]=='*' && s[1]=='*') { s[0]=' '; ++s; s[0]='^'; } // "**" -> '^'
  h=s[0]; // next operation symbol

  if (term_structure_ok && !gZ_einstellig(op))
   {
     if (gZ_priority_gr(h,op) || (h=='^' && op=='^'))
      {
        // operator with higher priority (or rightwise associative)
        // evaluate the right term before the left one... 
#ifdef VERBOSE_WARN
        if (op=='^' && h=='^') cout << "Warning: a^b^c ambiguent; using a^(b^c)." << endl;
#endif
        term_structure_ok=get_number(tmp,++s,h,op);
        if (s[0]=='*' && s[1]=='*') { s[0]=' '; ++s; s[0]='^'; } // "**" -> '^'
        h=s[0]; // next operation symbol
      }
   }
  
  if (term_structure_ok) switch (op)
    {
    case '\0':
      break;
    case 'R' :
      //cout << "Reset" << endl;
      mpz_set(n,tmp);
      break;
    case 'F' : // Fibonacci number
      {
       if (mpz_cmp_ui(tmp,100000)>0)
        {
         cerr << "fibonacci: argument to big: " << tmp << endl;
         exit(1);
        }
       if (mpz_sgn(tmp)<0)
        {
         cerr << "fibonacci: argument negative: " << tmp << endl;
         exit(1);
        }
#ifdef VERBOSE_INFO
       cout << "computing fibonacci number" << endl;
#endif
       mpz_fib_ui(n,mpz_get_ui(tmp));
      }
      break;
    case 'L' : // Lucas number
      {
       if (mpz_cmp_ui(tmp,100000)>0)
        {
         cerr << "lucas: argument too big: " << tmp << endl;
         exit(1);
        }
       if (mpz_sgn(tmp)<0)
        {
         cerr << "lucas: argument negative: " << tmp << endl;
         exit(1);
        }
#ifdef VERBOSE_INFO
       cout << "computing lucas number" << endl;
#endif
       mpz_lucnum_ui(n,mpz_get_ui(tmp));
      }
      break;
    case 'P' : // Partition number
      {
       if (mpz_cmp_ui(tmp,1000000)>0)
        {
         cerr << "partition number: argument to big: " << tmp << endl;
         exit(1);
        }
       if (mpz_sgn(tmp)<0)
        {
         cerr << "partition number: argument negative: " << tmp << endl;
         exit(1);
        }
#ifdef VERBOSE_INFO
       cout << "computing partition number" << endl;
#endif
       numbpart::numbpart(n,mpz_get_ui(tmp));
      }
      break;
    case 'f' : // evaluate factorial of tmp
      {
       if (mpz_cmp_ui(tmp,100000)>0)
        {
         cerr << "factorial: argument to big: " << tmp << endl;
         exit(1);
        }
       if (mpz_sgn(tmp)<0)
        {
         cerr << "factorial: argument negative: " << tmp << endl;
         exit(1);
        }
#ifdef VERBOSE_INFO
       cout << "computing factorial" << endl;
#endif
       mpz_fac_ui(n,mpz_get_ui(tmp));
      }
      break;
    case 'p' : // compute next prime number after tmp (as long as tmp isn't prime)
      {
        mpz_set(n,tmp); mpz_sub_ui(n,n,1);
        do { mpz_nextprime(n,n); } while (!mpz_probab_prime_p(n,50)); 
      }
      break;
    case 's' : // compute next safeprime number after tmp (as long as tmp isn't safeprime)
      {
        // safeprime: p is prime and (p-1)/2 is prime
        mpz_set(n,tmp);
        if (mpz_cmp_ui(n,7)<0) mpz_set_ui(n,7);
        mpz_sub_ui(n,n,1);
        do
         {
           mpz_nextprime(n,n);
           mpz_div_ui(tmp,n,2); // floor(n/2) = (n-1)/2
         } while (!mpz_probab_prime_p(tmp,20) || !mpz_probab_prime_p(n,50) ); 
      }
      break;
    case 'q' : // abort program, is tmp is composite
      {
#ifdef VERBOSE_NOTICE
        cout << "special command q, testing argument..." << endl;
#endif
        mpz_set(n,tmp);
        if (!mpz_probab_prime_p(n,50))
         {
           cout << "argument is not prime, aborting program." << endl;
           exit(0);
         }
      }
      break;
    case 'i' :
      mpz_add_ui(n,tmp,1);
      break;
    case 'd' :
      mpz_sub_ui(n,tmp,1);
      break;
    case 'r' :
      mpz_sqrt(n,tmp);
      break;
    case '+' :
      mpz_add(n,n,tmp);
      break;
    case '-' :
      mpz_sub(n,n,tmp);
      break;
    case '*' : 
      mpz_mul(n,n,tmp);
      break;
    case '/' :
    case ':' :
      {
        mpz_t q;
        mpz_init(q);
        mpz_div(q,n,tmp);
#ifdef VERBOSE_WARN
        mpz_mul(tmp,q,tmp);
        if (mpz_cmp(tmp,n)) // is there a residue?
         {
           cout << "Warning: result of division is truncated!" << endl;
         }
#endif
        mpz_set(n,q);
        mpz_clear(q);
      }
      break;
    case '%' :
      mpz_mod(n,n,tmp);
      break;
    case '^' :
#ifdef VERBOSE_WARN
      if (h=='^') cout << "Warning: a^b^c ambiguent; using (a^b)^c." << endl;
#endif
      if (!mpz_fits_ulong_p(tmp))
       {
         cerr << "argument for exponentiation too big!" << endl;
         exit(1);
       }
      mpz_pow_ui(n,n,mpz_get_ui(tmp));
      break;
    default :
      s=--s_anf;
      cerr << "error: operation +-*/:^ expected at '" << s << "'" << endl;
      term_structure_ok=false;
      break;
    }
  mpz_clear(tmp);

  if ((gZ_einstellig(op) || op=='R') && !(h=='\0'||h==')'||gZ_mehrstellig(h)) ) return false;
  if (gZ_einstellig(op)) return term_structure_ok;

  if (term_structure_ok && h!='\0' && h!=')' )
   {
     // up to now, the term is okay;
     // there is no trailing parenthesis and an operator follows.
     if (upto_op=='\0') return get_number(n,++s,h);
     if (gZ_priority_le(h,upto_op)) return term_structure_ok;
     else return get_number(n,++s,h,upto_op);
   }
  else return term_structure_ok;
}

} // namespace parse_term

---