/*---------------------------------------------------------------------- File : postfix.c Contents: evaluate a postfix expression in integer numbers Author : Christian Borgelt History : 20.05.1998 file created 21.05.1998 first version completed 22.05.1998 comments added ----------------------------------------------------------------------*/ #include #include #include #include "stack.h" /*---------------------------------------------------------------------- Preprocessor Definitions ----------------------------------------------------------------------*/ /* --- token types --- */ #define T_END 256 /* end of input */ #define T_NUM 257 /* a number */ /* --- error codes --- */ #define OK 0 /* no error */ #define E_NONE 0 /* no error */ #define E_NOMEM (-1) /* not enough memory */ #define E_ILLCHAR (-2) /* illegal character */ #define E_EMPTY (-3) /* stack is empty */ #define E_NOTEMP (-4) /* stack is not empty */ #define E_UNKNOWN (-5) /* unknown error */ /*---------------------------------------------------------------------- Constants ----------------------------------------------------------------------*/ const char *errmsgs[] = { /* error messages */ /* E_NONE */ "no error\n", /* E_NOMEM -1 */ "not enough memory\n", /* E_ILLCHAR -2 */ "illegal character in input\n", /* E_EMPTY -3 */ "stack is empty\n", /* E_WEIGHT -4 */ "stack is not empty\n", /* E_UNKNOWN -5 */ "unknown error\n", }; /*---------------------------------------------------------------------- Global Variables ----------------------------------------------------------------------*/ char *prgname; /* program name for error messages */ STACK *stack; /* number stack for evaluation */ /*---------------------------------------------------------------------- Functions ----------------------------------------------------------------------*/ int get_token (int *value) { /* --- get a token */ int c; /* current character */ do { /* skip leading blanks, i.e. */ c = getchar(); /* spaces and tabulators */ } while ((c == ' ') || (c == '\t')); switch (c) { /* test the character read */ case EOF: case '\n': /* if at the end of a line, */ return T_END; /* return `end of input' */ case '+': case '-': case '*': case '/': return c; /* if the character is an operator */ } /* return it */ if ((c < '0') || (c > '9')) /* if the character is not a digit, */ return E_ILLCHAR; /* it is illegal, so abort */ ungetc(c, stdin); /* put back the digit read */ scanf("%i", value); /* and read the number */ return T_NUM; /* return `number' (token type) */ } /* get_token() */ /*---------------------------------------------------------------------- The above function converts a character stream (read from stdin) into a token stream and thus simplifies the task of the function `postfix' considerably. In addition, the function removes any blank characters that may be present in between the tokens. A `token' is a sequence of characters that have to be treated as one input object. For example the sequence of digits 123 has to be treated as one object, since it represents the number onehundred and twenty-three. In a C program a variable name, which can consist of several letters and/or digits, has to be treated as a single object. Of course, a token need not consist of several characters. Some tokens consist only of one character, for example the operator '+'. A token stream is much easier to process than a character stream, since in it the characters that have to be treated together are already grouped and hence the function processing it need not bother about the grouping task. The above function proceeds as follows. First it repeatedly reads a character until the character is not a space or a tabulator, thus skipping any blanks that may be present in front of the next token. In case the character read is a newline or the end of the file has been reached (indicated by the special character EOF), it returns the special token T_END to indicate that the end of the input has been reached. In case the character is an operator it simply returns the character code of the corresponding character. Then it checks whether the character is a digit, since digits are the only other allowed characters apart from operators. If it is no digit, it is clearly an illegal character, so an error code is returned. Otherwise the character is returned to the input stream in order to be able to read the number with the `scanf' function. To indicate that a number has been read it returns the special token T_NUM. Note that the special tokens T_END and T_NUM are defined as 256 and 257, respectively, in order to avoid a conflict with any one character token (characters are represented by the numbers 0 to 255). ----------------------------------------------------------------------*/ int eval (void) { /* --- evaluate a postfix expression */ int token; /* current token, e.g. T_NUM */ int value; /* value of the current token */ int x, y; /* temporary buffers for operands */ while (1) { /* evaluation loop */ token = get_token(&value); /* get the next token and its value */ if (token < 0) return token; /* check for an error */ if (token == T_END) return 0; /* and for end of input */ if (token == T_NUM) { /* if the next token is a number */ if (stk_push(stack, (void*)value) != 0) return E_NOMEM; continue; /* push its value onto the stack */ } /* and continue with the next token */ if (stk_empty(stack)) return E_EMPTY; y = (int)stk_pop(stack, 0); /* get second operand */ if (stk_empty(stack)) return E_EMPTY; x = (int)stk_pop(stack, 0); /* get first operand */ switch (token) { /* evaluate the token, */ case '+': x += y; break; /* which must be an operator, */ case '-': x -= y; break; /* and execute the */ case '*': x *= y; break; /* corresponding operation */ case '/': x /= y; break; } if (stk_push(stack, (void*)x) != 0) return E_NOMEM; /* push the result */ } /* back onto the stack */ } /* eval() */ /*---------------------------------------------------------------------- The above function evaluates a postfix expression using a number stack. Every time it reads a number, it pushes it onto the stack. Every time it reads an operator, it pops two numbers from the stack (if possible, otherwise an error code is returned), combines them according to the operator, and pushes the result back onto the stack. It returns, if the end of the input has been reached. The main function then prints the number on the top of the stack (if any), and checks whether the stack contained only this one number (as it should). ----------------------------------------------------------------------*/ void error (int code, ...) { /* --- print an error message */ const char *msg; /* error message */ va_list args; /* list of variable arguments */ if ((code > 0) || (code < E_UNKNOWN)) code = E_UNKNOWN; /* check error code */ msg = errmsgs[-code]; /* get error message */ fprintf(stderr, "%s: ", prgname); va_start(args, code); /* get variable arguments, */ vfprintf(stderr, msg, args); /* print error message and */ va_end(args); /* end argument evaluation */ exit(code); /* abort the programm */ } /* error() */ /*--------------------------------------------------------------------*/ int main (int argc, char *argv[]) { /* --- main function */ prgname = argv[0]; /* get program name for error msgs. */ stack = stk_create(); /* create a number stack */ if (!stack) error(E_NOMEM); /* for the computations */ argc = eval(); /* evaluate the postfix expression */ if (argc != 0) error(argc); /* and check for an error */ if (stk_empty(stack)) error(E_EMPTY); /* check stack */ printf("%i\n", (int)stk_pop(stack, 0)); /* print result */ if (!stk_empty(stack)) error(E_NOTEMP); /* check stack */ stk_delete(stack); /* delete the number stack */ return 0; /* return 'ok' */ } /* main() */ /*---------------------------------------------------------------------- This program evaluates a postfix expression it reads from stdin and prints the result to stdout. To evaluate an infix expression combine it with the program `in2post' using a pipe: in2post | postfix This program uses the module stack.c. Compile it with gcc -ansi -Wall -pedantic stack.c postfix.c -o postfix ----------------------------------------------------------------------*/