Logo Search packages:      
Sourcecode: galculator version File versions  Download package

calc_basic.c

/*
 *  calc_basic.c - arithmetic precedence handling and computing in basic 
 *                calculator mode.
 *    part of galculator
 *    (c) 2002-2006 Simon Floery (chimaira@users.sf.net)
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Library General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */
 
/*
 * compile with:
 * gcc calc_basic.c `pkg-config --cflags --libs glib-2.0` -Wall -lm
 *
 * this is calc_basic version 2.
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <glib.h>
#include <math.h>

#include "calc_basic.h"

/* i18n */

#include <libintl.h>
#define _(String) gettext (String)
#define gettext_noop(String) String
#define N_(String) gettext_noop (String)

static char       *operator_precedence[] = {"=)", "+-&|x", "*/<>%", "^", "(", "%", NULL};
static char       *right_associative = "^";

static GArray           *rpn_stack;
static int        rpn_stack_size;
static int        alg_debug = 0, rpn_debug = 0;

/*
 * GENERAL STUFF
 */

/* id. The identity function. This is used as stack function, if none was given.
 */

double id (double x)
{
      return x;
}

/* debug_input. debug code: enter tokens on stdin.
 */
/*
void debug_input ()
{
      char        input[20];
      s_cb_token  current_token;
      
      scanf ("%s", input);
      current_token.number = atof (input);
      scanf ("%s", input);
      current_token.operation = input[0];
      current_token.func = NULL;
      printf ("\t\tdisplay value: %f\n", alg_add_token (current_token));
}
*/
/* reduce. TRUE if op1 comes before op2 in a computation.
 */

static int reduce (char op1, char op2)
{
      int   counter = 0, p1 = 0, p2 = 0;
      
      while (operator_precedence[counter] != NULL) {
            if (strchr (operator_precedence[counter], op1) != NULL)
                  p1 = counter;
            if (strchr (operator_precedence[counter], op2) != NULL)
                  p2 = counter;
            counter++;
      }
      if (p1 < p2) return FALSE;
      /* associativity only makes sense for same operations */
      else if ((op1 == op2) && (strchr (right_associative, op1) != NULL)) 
            return FALSE;
      else return TRUE;
}

/* compute_expression. here, the real copmputation is done.
 */

static double compute_expression (double left_hand, 
                        char operator, 
                        double right_hand)
{
      double      result;
      
      switch (operator) {
      case '+':
            result = left_hand + right_hand;
            break;
      case '-':
            result = left_hand - right_hand;
            break;
      case '*':
            result = left_hand * right_hand;
            break;
      case '/':
            result = left_hand / right_hand;
            break;
      case '^':
            result = pow (left_hand, right_hand);
            break;
      case '<':
            /* left shift x*2^n */
            result = ldexp (left_hand, (int) floor(right_hand));        
            break;
      case '>':
            result = ldexp (left_hand, ((int) floor(right_hand))*(-1));
            break;
      case 'm':
            result = fmod (left_hand, right_hand);
            break;
      case '&':
            result = (long long int)left_hand & (long long int) right_hand;
            break;
      case '|':
            result = (long long int)left_hand | (long long int) right_hand;
            break;
      case 'x':
            result = (long long int)left_hand ^ (long long int) right_hand;
            break;
      case '%':
            result = left_hand * right_hand/100;
            break;
      default: 
            if (alg_debug+rpn_debug > 0) fprintf (stderr, _("[%s] %c - unknown operation \
character. %s\n"), PROG_NAME, operator, BUG_REPORT);
            result = left_hand;
            break;
      }     
      if (alg_debug + rpn_debug > 0) fprintf (stderr, "[%s] computing: %f %c %f = %f\n", 
            PROG_NAME, left_hand, operator, right_hand, result);
      return result;
}

/*
 * (PSEUDO)ALGEBRAIC MODE
 */

/* alg_stack_new. we are working with stacks. every bracket layer is a single 
 * stack. this function creates a new stack.
 */

static s_alg_stack *alg_stack_new (s_cb_token this_token)
{
      s_alg_stack *new_stack;
      
      new_stack = (s_alg_stack *) malloc (sizeof(s_alg_stack));
      new_stack->func = this_token.func;
      new_stack->number = NULL;
      new_stack->operation = NULL;
      new_stack->size = 0;
      return new_stack; 
}

/* alg_stack_append. simply appends token (number and operation) to stack.
 * that's all (no computation etc!).
 */

static void alg_stack_append (s_alg_stack *stack, s_cb_token token)
{
      stack->size++;
      stack->number = (double *) realloc (stack->number, 
            stack->size * sizeof(double));
      stack->number[stack->size-1] = token.number;
      stack->operation = (char *) realloc (stack->operation,
            stack->size * sizeof(char));
      stack->operation[stack->size-1] = token.operation;
}

/* alg_stack_pool. do as many computation as possible with respect to
 * precedence. here, reduce from above is used.
 */

static double alg_stack_pool (s_alg_stack *stack)
{
      int   index;
      
      index = stack->size - 1;
      while ((index >= 1) && (reduce(stack->operation[index-1], 
            stack->operation[index]))) {
                  stack->number[index - 1] = compute_expression (
                        stack->number[index - 1],
                        stack->operation[index - 1],
                        stack->number[index]);
                  stack->operation[index - 1] = stack->operation[index];
                  index--;
      }
      if (stack->size != (index + 1)) {
            stack->size = index + 1;
            stack->number = (double *) realloc (stack->number,
                  sizeof(double) * stack->size);
            stack->operation = (char *) realloc (stack->operation, 
                  sizeof(char) * stack->size);
      }
      return stack->number[stack->size-1];
}

/* alg_stack_free. the stack destructor. 
 */

static void alg_stack_free (s_alg_stack *stack)
{
      if (!stack) {
            if (!stack->number) free (stack->number);
            if (!stack->operation) free (stack->operation);
            free (stack);
      }
}

/* alg_stack_free_gfunc. wrapper for alg_stack_free for g_slist_foreach.
 */

static void alg_stack_free_gfunc (gpointer data, gpointer user_data)
{
      s_alg_stack *stack;
      
      stack = data;
      alg_stack_free (stack);
}

/* alg_add_token. call this from outside. 
 */

double alg_add_token (ALG_OBJECT **alg, s_cb_token this_token)
{
      static double     return_value;
      s_alg_stack *current_stack;
      
      switch (this_token.operation) {
      case '(':
            if (this_token.func == NULL) this_token.func = id;
            *alg = g_slist_prepend (*alg, alg_stack_new (this_token));
            break;
      case ')':
            if (g_slist_length (*alg) < 2) break;
            current_stack = (s_alg_stack *) (*alg)->data;
            alg_stack_append (current_stack, this_token);
            return_value = current_stack->func (
                  alg_stack_pool (current_stack));
            /* we may specify a function after a bracket enclosed expression
             * this is necessary e.g. for factorial. This function is 
             * applied after the stack function, so sin(3)! will be (sin(3))!
             */
            if (this_token.func != NULL)
                  return_value = this_token.func(return_value);
            alg_stack_free (current_stack);
            *alg = g_slist_delete_link (*alg, *alg);
            break;
      case '=':
            /* first close all open brackets */
            while (g_slist_length (*alg) > 1) {
                  this_token.operation = ')';
                  this_token.number = alg_add_token (alg, this_token);
            }
            this_token.operation = '=';
            current_stack = (s_alg_stack *) (*alg)->data;
            alg_stack_append (current_stack, this_token);
            return_value = alg_stack_pool (current_stack);
            alg_free (*alg);
            *alg = alg_init(alg_debug);
            break;
      default:
            current_stack = (s_alg_stack *) (*alg)->data;
            alg_stack_append (current_stack, this_token);
            return_value = alg_stack_pool (current_stack);
            break;
      }
      return return_value;
}

/* alg_init. use this from outside to initialize everything
 */

ALG_OBJECT *alg_init (int debug_level)
{
      s_cb_token  token;
      
      alg_debug = debug_level;
      token.func = id;
      return g_slist_prepend (NULL, alg_stack_new(token));
}

/* alg_free. call this from outside to clean up properly
 */

void alg_free (ALG_OBJECT *alg)
{
      if (!alg) {
            g_slist_foreach (alg, alg_stack_free_gfunc, NULL);
            g_slist_free (alg);
            alg = NULL;
      }
}

/*
 * RPN
 */

/* rpn_init. initializes everything from stack to sizes and debug.
 */

void rpn_init (int size, int debug_level)
{
      rpn_stack = g_array_new (FALSE, FALSE, sizeof(double));
      rpn_stack_size = size;
      rpn_debug = debug_level;
}

/* debug_rpn_stack_print. printf stack to stderr
 */

void debug_rpn_stack_print ()
{
      int   counter;
      double      *stack;
      
      stack = rpn_stack_get (rpn_stack_size);
      for (counter = 0; counter < MAX(rpn_stack_size, (int)rpn_stack->len); counter++)
            fprintf (stderr, "[%s]\t %02i: %f\n", PROG_NAME, counter, stack[counter]);
      free (stack);
}

/* rpn_stack_push. new values is prepended! then, if finite stack size, 
 * remove last one. in the end some debugs.
 */

void rpn_stack_push (double number)
{
      rpn_stack = g_array_prepend_val (rpn_stack, number);
      if (((int)rpn_stack->len > rpn_stack_size) && (rpn_stack_size > 0))
            rpn_stack = g_array_remove_index (rpn_stack, rpn_stack_size);
      if (rpn_debug > 0) fprintf (stderr, "[%s] RPN stack size is %i.\n", 
            PROG_NAME, (int)rpn_stack->len);
      if (rpn_debug > 1) debug_rpn_stack_print();
}

/* rpn_stack_operation. does some operation. This is also the place where the
 * stack is popped!
 */

double rpn_stack_operation (s_cb_token current_token)
{
      double      return_value;
      double      left_hand;
      double      last_on_stack;
      
      /* this function only serves binary operations. therefore, we need at 
       * least one element on the stack. if this is not the case, work with 0.
       */
      if (rpn_stack->len < 1) left_hand = 0;
      else {
            /* retrieve left_hand from stack */
            left_hand = g_array_index (rpn_stack, double, 0);
            last_on_stack = g_array_index (rpn_stack, double, (int)rpn_stack->len-1);
            rpn_stack = g_array_remove_index (rpn_stack, 0);
            /* last register is kept, if stack size is finite */
            if (((int) rpn_stack->len == rpn_stack_size-1) && (rpn_stack_size > 0))
                  rpn_stack = g_array_append_val (rpn_stack, last_on_stack);
      }
      /* compute it */
      return_value = compute_expression (left_hand, current_token.operation, 
            current_token.number);
      if (rpn_debug > 0) fprintf (stderr, "[%s] RPN stack size is %i.\n", 
            PROG_NAME, (int)rpn_stack->len);
      if (rpn_debug > 1) debug_rpn_stack_print();
      return return_value;
}

/* rpn_stack_swapxy. swap first and second register. there are some special cases.
 */

double rpn_stack_swapxy (double x)
{
      double      *y, ret_val;
      
      if ((int)rpn_stack->len < 1) { 
            ret_val = 0.;
            rpn_stack = g_array_append_val (rpn_stack, x);
      } else {
            y = &g_array_index (rpn_stack, double, 0);
            ret_val = *y;
            *y = x;
      }
      if (rpn_debug > 0) fprintf (stderr, "[%s] RPN stack size is %i.\n", 
            PROG_NAME, (int)rpn_stack->len);
      if (rpn_debug > 1) debug_rpn_stack_print();
      return ret_val;
}

/* rpn_stack_rolldown. y->x, z->y, ..., x->t
 * return value ret_val is new result.
 */

double rpn_stack_rolldown (double x)
{
      double      *a, ret_val;
      int   counter;
      
      if (rpn_stack_size <= 0) return x;
      ret_val = 0.;
      /* in the following case we have to fill up with zeros. thus this is
       * done virtually in rpn_stack_get.
       */
      if ((rpn_stack_size > 0) && ((int)rpn_stack->len < rpn_stack_size))
            for (counter = rpn_stack->len; counter < rpn_stack_size; counter++)
                  rpn_stack = g_array_append_val (rpn_stack, ret_val);
      ret_val = g_array_index (rpn_stack, double, 0);
      for (counter = 0; counter < (int) rpn_stack->len - 1; counter++) {
            a = &g_array_index (rpn_stack, double, counter);
            *a = g_array_index (rpn_stack, double, counter + 1);
      }
      a = &g_array_index (rpn_stack, double, rpn_stack->len - 1);
      *a = x;
      return ret_val;
}

/* rpn_stack_get. returns a double array with the first length elements of
 * stack. returned array should be freed.
 */

double *rpn_stack_get (int length)
{
      double            *return_array;
      int         counter;
      
      if (length <= 0) length = (int)rpn_stack->len;
      return_array = (double *) malloc (length*sizeof(double));
      for (counter = 0; counter < MIN (length, (int)rpn_stack->len); counter++)
            return_array[counter] = g_array_index (rpn_stack, double, counter);
      for (; counter < length; counter++) 
            return_array[counter] = 0.;
      return return_array;
}

/* rpn_stack_set_size. write rpn_stack_size.
 */

void rpn_stack_set_size (int size)
{
      int   counter;

      if ((size > 0) && ((size < rpn_stack_size) || (rpn_stack_size == -1)))
            for (counter = ((int)rpn_stack->len-1); counter >= size; counter--)
                  rpn_stack = g_array_remove_index (rpn_stack, counter);
      rpn_stack_size = size;
}
/* rpn_free. the finalizer.
 */

void rpn_free ()
{
      if (!rpn_stack) g_array_free (rpn_stack, TRUE);
}

/*
int main (int argc, char *argv[])
{
      alg_init(1);
      while (1) debug_input();
      return 1;
}
*/

Generated by  Doxygen 1.6.0   Back to index