Code :
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #define RIGHT 1 #define LEFT 2 #define DIM(table) (sizeof(table) / sizeof(table[0])) typedef char TEXT; typedef TEXT * STRPTR; typedef struct Operator_t * Operator; typedef struct Stack_t * Stack; struct Operator_t { STRPTR token; int arity; int associativity; int priority; }; static struct Operator_t OperatorList[] = { { "-", 1, RIGHT, 15 }, { "~", 1, RIGHT, 15 }, { "*", 2, LEFT, 13 }, { "/", 2, LEFT, 13 }, { "%", 2, LEFT, 13 }, { "+", 2, LEFT, 12 }, { "-", 2, LEFT, 12 }, { "<<", 2, LEFT, 11 }, { ">>", 2, LEFT, 11 }, { "&", 2, LEFT, 8 }, { "^", 2, LEFT, 7 }, { "|", 2, LEFT, 6 } }; struct Stack_t { Stack next; short type; union { Operator ope; float integer; } value; }; enum { TOKEN_UNKNOWN, TOKEN_NUMBER, TOKEN_INCPRI, TOKEN_DECPRI, TOKEN_OPERATOR, TOKEN_SKIP }; enum /* Possible values for 'type' field */ { TYPE_FLOAT, TYPE_OPE }; enum /* Return codes of ParseExpression */ { PERR_SyntaxError = 1, PERR_DivisionByZero, PERR_LValueNotModifiable, PERR_TooManyClosingParens, PERR_MissingOperand, PERR_InvalidOperation }; static Stack NewOperator(Operator ope) { Stack oper = calloc(sizeof *oper, 1); oper->value.ope = ope; oper->type = TYPE_OPE; return oper; } static Stack NewNumber(float val) { Stack num = calloc(sizeof *num, 1); num->value.integer = val; num->type = TYPE_FLOAT; return num; } // Try to parse a number static int GetNumber(Stack * object, STRPTR * exp) { STRPTR cur = *exp; STRPTR str = cur; long nb; // Signed numbers are interpreted as a unsigned preceeded by an unary - if (! isdigit(*str)) return 0; // Try to parse an integer (octal, dec or hexa, like in C) nb = strtoul(cur, &str, 0); if (str > cur) { *object = NewNumber(nb); *exp = str; return 1; } return 0; } // Our main lexical analyser, this should've been the lex part static int GetToken(Stack * object, STRPTR * exp) { STRPTR str; int type = TOKEN_SKIP; // Skip starting space for (str = *exp; isspace(*str); str ++); // Precedence arrangement if (*str == '(') { str ++; type = TOKEN_INCPRI; } else if (*str == ')') { str ++; type = TOKEN_DECPRI; } else if (GetNumber(object, &str)) { type = TOKEN_NUMBER; } else if (*str) // Maybe an operator { Operator best, cur; // Use same rule as C : longest match is winner for (best = NULL, cur = OperatorList; cur < OperatorList + DIM(OperatorList); cur ++) { int length = strlen(cur->token); if (strncmp(str, cur->token, length) == 0 && (best == NULL || strlen(best->token) < length)) best = cur; } if (best) { str += strlen(best->token); *object = NewOperator(best); type = TOKEN_OPERATOR; } else type = TOKEN_UNKNOWN; } *exp = str; return type; } static void PushStack(Stack * top, Stack object) { object->next = *top; (*top) = object; } static Stack PopStack(Stack * top) { Stack ret = *top; if (ret) *top = ret->next; return ret; } // This is the function that takes operand and perform operation according to top most operator // This is the syntax analyser, usually produced by tools like yacc static int MakeOp(Stack * values, Stack * oper) { Stack arg1, arg2; Operator ope = (*oper)->value.ope; int nb, error = 0; #define THROW(err) { error = err; goto error_case; } arg1 = arg2 = NULL; switch (ope->arity) { case 2: arg2 = PopStack(values); if (arg2 == NULL) THROW(PERR_MissingOperand); default: arg1 = PopStack(values); if (arg1 == NULL) THROW(PERR_MissingOperand); } free(PopStack(oper)); nb = ope - OperatorList; switch (nb) { case 0: arg1->value.integer = - arg1->value.integer; PushStack(values, arg1); free(arg2); break; /* case 1: arg1->value.integer = ~ arg1->value.integer; PushStack(values, arg1); free(arg2); break; */ case 2: arg1->value.integer *= arg2->value.integer; PushStack(values, arg1); free(arg2); break; case 3: // Division / if (arg2->value.integer == 0) THROW(PERR_DivisionByZero); arg1->value.integer /= arg2->value.integer; PushStack(values, arg1); free(arg2); break; /*case 4: // Modulus % if (arg2->value.integer == 0) THROW(PERR_DivisionByZero); arg1->value.integer %= arg2->value.integer; PushStack(values, arg1); free(arg2); break; */ case 5: arg1->value.integer += arg2->value.integer; PushStack(values, arg1); free(arg2); break; case 6: arg1->value.integer -= arg2->value.integer; PushStack(values, arg1); free(arg2); break; /* case 7: arg1->value.integer <<= arg2->value.integer; PushStack(values, arg1); free(arg2); break; case 8: arg1->value.integer >>= arg2->value.integer; PushStack(values, arg1); free(arg2); break; case 9: arg1->value.integer &= arg2->value.integer; PushStack(values, arg1); free(arg2); break; case 10: arg1->value.integer ^= arg2->value.integer; PushStack(values, arg1); free(arg2); break; case 11: arg1->value.integer |= arg2->value.integer; PushStack(values, arg1); free(arg2); break; */ } return error; error_case: if (arg1) free(arg1); if (arg2) free(arg2); return error; } int ParseExpression(STRPTR exp, float * result) { Operator ope; STRPTR next; int curpri, pri, error, tok; Stack values, oper, object; for (curpri = error = tok = 0, values = oper = NULL, next = exp; error == 0 && *exp; exp = next) { switch (GetToken(&object, &next)) { case TOKEN_NUMBER: // Number => stack it if (tok == TOKEN_NUMBER) error = PERR_SyntaxError; tok = TOKEN_NUMBER; PushStack(&values, object); break; case TOKEN_INCPRI: curpri += 30; break; case TOKEN_DECPRI: if (tok == TOKEN_OPERATOR) error = PERR_SyntaxError; curpri -= 30; if (curpri < 0) error = PERR_TooManyClosingParens; break; case TOKEN_OPERATOR: // Operator ope = object->value.ope; pri = curpri + ope->priority - (ope->associativity == LEFT); if (ope == OperatorList && tok == TOKEN_NUMBER) ope = object->value.ope = OperatorList + 6, pri = 11 + curpri; // Binary '-' instead while (error == 0 && oper && pri < oper->type) error = MakeOp(&values, &oper); if (error) { free(object); break; } tok = TOKEN_OPERATOR; object->type = curpri + ope->priority; PushStack(&oper, object); break; case TOKEN_UNKNOWN: error = PERR_SyntaxError; } } while (error == 0 && oper) error = MakeOp(&values, &oper); if (error == 0 && values) *result = values->value.integer; while (oper) free(PopStack(&oper)); while (values) free(PopStack(&values)); return error; } int computer(int nb, char * argv[], char * result ) { TEXT locale[256]; TEXT buffer[256]; float res; int err; /* fprintf(stderr, "calc> " ); */ /* fgets(buffer, sizeof buffer, stdin); */ err = ParseExpression(argv, &res); switch (err) { case 0: fprintf(stderr, "result = %f\n", res); break; case PERR_SyntaxError: fprintf(stderr, "Syntax error.\n" ); break; case PERR_DivisionByZero: fprintf(stderr, "Division by zero.\n" ); break; case PERR_TooManyClosingParens: fprintf(stderr, "Too many closing parenthesis.\n" ); break; case PERR_MissingOperand: fprintf(stderr, "Missing operand.\n" ); break; case PERR_InvalidOperation: fprintf(stderr, "Invalid operation.\n" ); break; } sprintf(locale, "%f", res); result = locale; return err; }
|