#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 */
tAdd, /* + */
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]) {
case tAdd:
/* 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;
}
