# Practice (C)

```#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

typedef enum { false , true } bool;

/* actions */
typedef enum {
S,                 /* shift */
R,                 /* reduce */
A,                 /* accept */
E1,                /* error: missing right parenthesis */
E2,                /* error: missing operator */
E3,                /* error: unbalanced right parenthesis */
E4                 /* error: invalid function argument */
} actEnum;

/* tokens */
typedef enum {
/* operators */
tSub,               /* - */
tMul,               /* * */
tDiv,               /* / */
tPow,               /* ^ (power) */
tUmi,               /* - (unary minus) */
tFact,              /* f(x): factorial */
tPerm,              /* p(n,r): permutations, n objects, r at a time */
tComb,              /* c(n,r): combinations, n objects, r at a time */
tComa,              /* comma */
tLpr,               /* ( */
tRpr,               /* ) */
tEof,               /* end of string */
tMaxOp,             /* maximum number of operators */
/* non-operators */
tVal                /* value */
} tokEnum;

tokEnum tok;            /* token */
double tokval;          /* token value */

#define MAX_OPR         50
#define MAX_VAL         50
char opr[MAX_OPR];      /* operator stack */
double val[MAX_VAL];    /* value stack */
int oprTop, valTop;     /* top of operator, value stack */
bool firsttok;          /* true if first token */

char parseTbl[tMaxOp][tMaxOp] = {
/* stk     ------------------- input ------------------------ */
/*         +   -   *   /   ^   M   f   p   c   ,   (   )   \$  */
/*         --  --  --  --  --  --  --  --  --  --  --  --  -- */
/* + */  { R,  R,  S,  S,  S,  S,  S,  S,  S,  R,  S,  R,  R },
/* - */  { R,  R,  S,  S,  S,  S,  S,  S,  S,  R,  S,  R,  R },
/* * */  { R,  R,  R,  R,  S,  S,  S,  S,  S,  R,  S,  R,  R },
/* / */  { R,  R,  R,  R,  S,  S,  S,  S,  S,  R,  S,  R,  R },
/* ^ */  { R,  R,  R,  R,  S,  S,  S,  S,  S,  R,  S,  R,  R },
/* M */  { R,  R,  R,  R,  R,  S,  S,  S,  S,  R,  S,  R,  R },
/* f */  { R,  R,  R,  R,  R,  R,  R,  R,  R,  R,  S,  R,  R },
/* p */  { R,  R,  R,  R,  R,  R,  R,  R,  R,  R,  S,  R,  R },
/* c */  { R,  R,  R,  R,  R,  R,  R,  R,  R,  R,  S,  R,  R },
/* , */  { R,  R,  R,  R,  R,  R,  R,  R,  R,  R,  R,  R,  E4},
/* ( */  { S,  S,  S,  S,  S,  S,  S,  S,  S,  S,  S,  S,  E1},
/* ) */  { R,  R,  R,  R,  R,  R,  E3, E3, E3, R,  E2, R,  R },
/* \$ */  { S,  S,  S,  S,  S,  S,  S,  S,  S,  E4, S,  E3, A }
};

int error(char *msg) {
printf("error: %s\n", msg);
return 1;
}

int gettok(void) {
static char str[82];
static tokEnum prevtok;
char *s, *ptr;

/* scan for next symbol */
if (firsttok) {
firsttok = false;
prevtok = tEof;
gets(str);
if (*str == 'q') exit(0);
s = strtok(str, " ");
} else {
s = strtok(NULL, " ");
}

/* convert symbol to token */
if (s) {
switch(*s) {
case '+': tok = tAdd; break;
case '-': tok = tSub; break;
case '*': tok = tMul; break;
case '/': tok = tDiv; break;
case '^': tok = tPow; break;
case '(': tok = tLpr; break;
case ')': tok = tRpr; break;
case ',': tok = tComa; break;
case 'f': tok = tFact; break;
case 'p': tok = tPerm; break;
case 'c': tok = tComb; break;
default:
tokval = strtod(s, &ptr);
if (*ptr) {
printf("error: non-numeric data encountered\n");
return 1;
}
tok = tVal;
break;
}
} else {
tok = tEof;
}

/* check for unary minus */
if (tok == tSub) {
if (prevtok != tVal && prevtok != tRpr) {
tok = tUmi;
}
}

prevtok = tok;
return 0;
}

int shift(void) {
if (tok == tVal) {
if (++valTop >= MAX_VAL)
return error("val stack overflow");
val[valTop] = tokval;
} else {
if (++oprTop >= MAX_OPR)
return error("opr stack overflow");
opr[oprTop] = (char)tok;
}
if (gettok()) return 1;
return 0;
}

double fact(double n) {
double i, t;
for (t = 1, i = 1; i <= n; i++)
t *= i;
return t;
}

int reduce(void) {
switch(opr[oprTop]) {
/* apply E := E + E */
if (valTop < 1) return error("syntax error");
val[valTop-1] = val[valTop-1] + val[valTop];
valTop--;
break;
case tSub:
/* apply E := E - E */
if (valTop < 1) return error("syntax error");
val[valTop-1] = val[valTop-1] - val[valTop];
valTop--;
break;
case tMul:
/* apply E := E * E */
if (valTop < 1) return error("syntax error");
val[valTop-1] = val[valTop-1] * val[valTop];
valTop--;
break;
case tDiv:
/* apply E := E / E */
if (valTop < 1) return error("syntax error");
val[valTop-1] = val[valTop-1] / val[valTop];
valTop--;
break;
case tUmi:
/* apply E := -E */
if (valTop < 0) return error("syntax error");
val[valTop] = -val[valTop];
break;
case tPow:
/* apply E := E ^ E */
if (valTop < 1) return error("syntax error");
val[valTop-1] = pow(val[valTop-1], val[valTop]);
valTop--;
break;
case tFact:
/* apply E := f(E) */
if (valTop < 0) return error("syntax error");
val[valTop] = fact(val[valTop]);
break;
case tPerm:
/* apply E := p(N,R) */
if (valTop < 1) return error("syntax error");
val[valTop-1] = fact(val[valTop-1])/fact(val[valTop-1]-val[valTop]);
valTop--;
break;
case tComb:
/* apply E := c(N,R) */
if (valTop < 1) return error("syntax error");
val[valTop-1] = fact(val[valTop-1])/
(fact(val[valTop]) * fact(val[valTop-1]-val[valTop]));
valTop--;
break;
case tRpr:
/* pop () off stack */
oprTop--;
break;
}
oprTop--;
return 0;
}

int parse(void) {

printf("\nenter expression (q to quit):\n");

/* initialize for next expression */
oprTop = 0; valTop = -1;
opr[oprTop] = tEof;
firsttok = true;
if (gettok()) return 1;

while(1) {

/* input is value */
if (tok == tVal) {
/* shift token to value stack */
if (shift()) return 1;
continue;
}

/* input is operator */
switch(parseTbl[opr[oprTop]][tok]) {
case R:
if (reduce()) return 1;
break;
case S:
if (shift()) return 1;
break;
case A:
/* accept */
if (valTop != 0) return error("syntax error");
printf("value = %f\n", val[valTop]);
return 0;
case E1:
return error("missing right parenthesis");
case E2:
return error("missing operator");
case E3:
return error("unbalanced right parenthesis");
case E4:
return error("invalid function argument");
}
}
}

int main(void) {
while(1) parse();
return 0;
}
```