scalc.c

// avp 2016 (for ru.stackoverflow.com)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

#include "scalc.h" // http://pastebin.com/y9H6B0SQ


struct calc {
  const char *str; // expression source
  int  rc,         // return code (OK == 0 or some error)
    pos,           // position to scan next lexem
    histop;        // lexems type (operation/number) "history"
  double result;   // current (and final) eval result or just read number
#define STACK(T) struct { T *mem; int size, sp; }
  STACK(double) nums; // stack for numbers (operands)
  STACK(char) ops;    // operations stack
#undef DSTACK
};

static const char *msgs[] = {
  "success",
  "out of memory",
  "two operands without operation beetwen them",
  "operand expected, but found ')' or operation",
  "unbalanced '(' ('(' found in stack by EOF)",
  "unbalanced ')' ('(' not found in stack)",
  "Invalid operation in expr() (INTERNAL ERROR)",
  "no operands for current operation",
  "at end operands stack depth too big",
  "at end operations left in stack",
  "invalid input char (letter, graph ...)",
  "empty input",
  "invalid error code",
  "no data"
};

// Returns error message text
const char *
scalc_strerr (int code)
{
  if (code == EOF)
    code = CALC_EOD;
  if (code < 0 || code >= (int)(sizeof(msgs) / sizeof(msgs[0])))
    code = CALC_ERR_CODE;

  return msgs[code];
}

// Previous token is an operation?
#define PREVOP(x) ((x) & 2)

#define INCR_STACK 100

#define CORRECT_STACK(st) ({ int rc = 1;                \
      if (!(st)->mem) {(st)->size = (st)->sp = 0;}          \
      if ((st)->size == (st)->sp) {                 \
    int s = sizeof(*((st)->mem)) * ((st)->size + INCR_STACK);   \
    void *t = realloc((st)->mem, s);                \
    if (!t)                             \
      rc = 0;                           \
    else {                              \
      (st)->mem = (typeof((st)->mem))t; (st)->size += INCR_STACK;   \
    }                               \
      }                                 \
      rc;                               \
    })

#define PUSH(stack, v) ({int rc = CORRECT_STACK(stack); \
      if (rc)                       \
    (stack)->mem[(stack)->sp++] = v;        \
      rc;                       \
    })

#define TOP(stack) ({typeof(*((stack)->mem)) v =  \
    (stack)->mem && (stack)->sp ?         \
    (stack)->mem[(stack)->sp - 1] : 0; v;})

#define POP(stack) ({typeof(*((stack)->mem)) v =  \
    (stack)->mem && (stack)->sp ?         \
    (stack)->mem[--((stack)->sp)] : 0; v;})

#define EMPTY(stack) (!((stack)->mem && (stack)->sp))

/*
   Take another token starting with ctx->str[ctx->pos]
   Returns operation code
   (if token is number put it's value to ctx->result)
*/
static int
getlex (struct calc *ctx)
{
  int i = ctx->pos, op;
  ctx->histop <<= 1; // shift operations history

  // skip spaces
  if (!(ctx->str[i += strspn(ctx->str + ctx->pos, " \t\r\n")])) {
    ctx->pos = i;
    return EOF;
  }
  ctx->pos = i + 1; // new starting position

  char *p;
  // take current character and  determine the type of the token
  if ((p = (char *)strchr("+-*/()", op = ctx->str[i]))) {
    // this is operation, clarify it
    if (op == '+' && PREVOP(ctx->histop))
      op = 'P'; // unary `+`
    else if (op == '-' && PREVOP(ctx->histop))
      op = 'M'; // unary `-`
    // `)`  behaves as an operand in an error check
    ctx->histop |= op == ')' ? 0 : 1;
  } else if (isdigit(op) || op == '.') {
    // number?
    ctx->result = strtod(ctx->str + i, &p);
    if (p != ctx->str + i) {
      // realy, next calls will detect possible error
      op = 'N';
      ctx->pos = p - ctx->str; // correct new starting position
    }
  } else
    op = '?';

  return op;
}


// Returns operation priority
static int
priority (int op)
{
  static char
    oprs[] = "+-M*/()",
    prio[] = "2243311";

  return op == EOF ? 0 : prio[strchr(oprs, op) - oprs] - '0';
}


/*
  Performs one elementary operation with operands in the stack
  Returns 0 -- error or 1 -- OK
 */
static int
expr (struct calc *ctx, int op)
{
  int n = op == 'M' ? 1 : 2; // number of operands

  if (ctx->nums.sp < n)
    return !(ctx->rc = CALC_NO_NUMS);

  switch (op) {
  case '+':
    ctx->result = ctx->nums.mem[ctx->nums.sp - 1] +
      ctx->nums.mem[ctx->nums.sp - 2];
    break;
  case '-':
    ctx->result = ctx->nums.mem[ctx->nums.sp - 2] -
      ctx->nums.mem[ctx->nums.sp - 1];
    break;
  case '*':
    ctx->result = ctx->nums.mem[ctx->nums.sp - 1] *
      ctx->nums.mem[ctx->nums.sp - 2];
    break;
  case '/':
    ctx->result = ctx->nums.mem[ctx->nums.sp - 2] /
      ctx->nums.mem[ctx->nums.sp - 1];
    break;
  case 'M':
    ctx->result = -(ctx->nums.mem[ctx->nums.sp - 1]);
    break;
    // internal error, unknown op
  default:
    return !(ctx->rc = CALC_ERR_OP);
  }

  ctx->nums.mem[ctx->nums.sp - n] = ctx->result;
  ctx->nums.sp -= (n - 1); // adjust the top of the stack

  return 1;
}

/*
  Push the operation onto the stack,
  popping and then perform the same or lower priority operations.
  Returns 0 -- error or 1 -- OK, last calculation result in ctx->result
 */
static int
eval (struct calc *ctx, int op)
{
  int p1 = priority(op);

  while (!EMPTY(&ctx->ops) && (p1  <= priority(TOP(&ctx->ops)))) {
    int top = POP(&ctx->ops);
    if (top == '(')
      return op == EOF ? !(ctx->rc = CALC_NO_RP) : 1; // 1 -- `(` and ')'

    if (!expr(ctx, top))
      return 0;
  }
  if (op == ')')
    return !(ctx->rc = CALC_NO_LP);

  if (op != EOF && !PUSH(&ctx->ops, op))
    return !(ctx->rc = CALC_OUT_OF_MEM);

  return 1;
}

/*
  Calculate arithmetic expression in str[],
  put result to *pres.
  Returns: success (0) or error code (can be used to call calc_strerr())
    or EOF if str[] is NULL
 */
int
scalc (const char *str, double *pres)
{
  if (!str)
    return EOF;
  *pres = NAN;
  // init context
  struct calc ctx = {str};
  ctx.result = NAN;
  // simulate that previous lexem was operation for simpler errors checking
  ctx.histop = 1;

  int op; // lexem type
  while (ctx.rc == 0 && (op = getlex(&ctx)) != EOF) {
    switch (op) {
      // ignore unar `+`
    case 'P':
      break;
      // push `(` and unar `-` to stack
    case '(':
      if (!PREVOP(ctx.histop)) {
    ctx.rc = CALC_NO_OP;
    break;
      }
    case 'M':
      if(!PUSH(&ctx.ops, op))
    ctx.rc = CALC_OUT_OF_MEM;
      break;
      // push (and eval part of stack) `+` `-` `*` or `/` operations
    case ')':
    case '*':
    case '/':
      if (PREVOP(ctx.histop)) {
    ctx.rc = CALC_NO_VAL;
    break;
      }
    case '+':
    case '-':
      eval(&ctx, op);
      break;
      // push new number to operands stack
    case 'N':
      if (!PREVOP(ctx.histop))
    ctx.rc = CALC_NO_OP;
      else if (!PUSH(&ctx.nums, ctx.result))
      ctx.rc = CALC_OUT_OF_MEM;
      break;
      // invalid input char
    default:
      ctx.rc = CALC_ERR_INPUT;
    }
  }

  if (!ctx.rc) // OK, eval stack
    eval(&ctx, EOF);
  *pres = ctx.result;
  // final stacks check
  if (!ctx.rc) {
    if (ctx.nums.sp == 0 && ctx.ops.sp == 0)
      ctx.rc = CALC_NO_INPUT;
    else if (ctx.nums.sp > 1)
      ctx.rc = CALC_NUMS_ERR;
    else if (ctx.ops.sp)
      ctx.rc = CALC_OPRS_ERR;
  }
  free(ctx.nums.mem);
  free(ctx.ops.mem);

  return ctx.rc;
}

#ifdef STACK_TEST
int
main ()
{
  struct calc cx = {0};

  puts("test PUSH/TOP/POP/EMPTY");

  PUSH(&cx.ops, 'a');
  PUSH(&cx.ops, 'a');
  PUSH(&cx.ops, 'b');
  PUSH(&cx.ops, 'c');
  PUSH(&cx.ops, 0);

  printf("empty top: %f\n", TOP(&cx.nums));
  PUSH(&cx.nums, 9.8);
  printf(" top: %f\n", TOP(&cx.nums));
  PUSH(&cx.nums, 3.14);
  printf(" top: %f\n", TOP(&cx.nums));
  PUSH(&cx.nums, 2.87);
  printf(" top: %f\n", TOP(&cx.nums));

  int i;
  for (i = cx.nums.sp - 1; i >= 0; i--)
    printf("%f\n", cx.nums.mem[i]);

  puts(cx.ops.mem);
  POP(&cx.ops);
  while (!EMPTY(&cx.ops))
    printf("pop: '%c'\n", POP(&cx.ops));

  return puts("END test PUSH/TOP/POP/EMPTY") == EOF;
}
#endif

#ifdef LEXEM_TEST
int
main ()
{
  struct calc cx = {0};
  char str[1000];
  int op;

  puts("test getlex(), enter expressions, stop by ^D");
  while (fputs("> ", stdout), fgets(str, 1000, stdin)) {
    cx = (typeof(cx)){str};
    while (cx.rc == 0 && (op = getlex(&cx)) != EOF)
      printf("op: '%c'  pos: %d res: %f\n",
         op, cx.pos, op == 'N' ? cx.result : NAN);
    printf("Fin: op: %d  pos: %d\n", op, cx.pos);
  }

  cx.str = "900"; cx.rc = cx.pos = 0;
  while (cx.rc == 0 && (op = getlex(&cx)) != EOF)
    printf("Op: '%c'  pos: %d res: %f\n",
       op, cx.pos, op == 'N' ? cx.result : NAN);
  printf("Fin2: op: %d  pos: %d\n", op, cx.pos);

  return puts("End") == EOF;
}
#endif

#ifdef CALC_TEST

int main ()
{
  char str[1000];
  int rc;
  double result;

  puts("test calc1(), enter expressions, stop by ^D");
  while (fputs("> ", stdout),
     (rc = scalc(fgets(str, 1000, stdin), &result)) != EOF)
    printf("`%s` rc = %d result = %.16g %s\n",
       str, rc, result, scalc_strerr(rc));

  return puts(scalc_strerr(rc)) == EOF;
}
#endif