In the March 1992 issue of “The C Users Journal”, Rex Jaeschke has a column called “Doctor C’s Pointers”. He has been running a series of articles on data structures in C. In one of the column on stacks, he presents a infix notation to postfix notation translator/convertor.
Infix notation is what is used in C, Pascal, Basic, etc. It looks like what we all learned in Algebra I. A equation would look like this: ( 3 + 7 ) – 8.
Postfix notation is more stack oriented. It is used in HP calculators, the languages Forth and Postscript, and is also called Reverse Polish Notation (RPN). (Infix notation is sometimes called Polish Notation after it’s Polish inventor) The above equation would look like this: 3 7 + 8 -.
The C program below takes in an infix equation and converts it to a postfix equation. Sample input would be:
c - d * e + f
(c - d * e) + f
(((a - b) / (c + d)) * e)
The program has a #define TRACE that allows you to see the process as it goes along.
intopost1_c
/* File: intopost1_c
fuctions for pushing and popping
*/
#define STACK_SIZE 30
static int stack[STACK_SIZE];
static int stack_ptr = 0;
push(value)
int value;
{
#ifdef TRACE
printf("pushing: %c¥n",value);
#endif
if ( stack_ptr == STACK_SIZE )
printf("Stack is full¥n");
else
stack[stack_ptr++] = value;
}
pop()
{
if (stack_ptr == 0) {
printf("Stack is empty¥n");
return(0);
}
#ifdef TRACE
printf("popping: %c¥n",stack[stack_ptr-1]);
#endif
return stack[--stack_ptr];
}
intopost2_c
#include <ctype_h>
/*-----------------------------------------------------
FUNCTION: intopost - converts infix to postfix
A. Push a ( on the stack. This sentinel allows us to
detect when we have flushed out the stack on completion in
step I.
B. Ingnore white space.
C. Pass alphabetic characters through to postfix list.
D. Push any ( on the stack. These sentinels allows us to
detect when we have flushed out the stack when handling )
and operators.
E. Have a ) so pop off the stack and put into postfix list
until a ( is popped. Discard that (.
F. Have a * or /. Pop off any operators of equal or higher
precedence and put them into postfix list. If a ( or lower
precedence operator (such as + or -) is popped, put it back
and stop looking. Push new * or/.
G. Have a + or -. Pop off any operators of equal or higher
precedence (that include all of them) and put them into
postfix list. If a ( is popped, put it back and stop
looking. Push new + or -.
H. Report unknown character on input.
I. Have processed all input characters. Now flush stack
until we find the matching ( put there in step A.
J. Terminate the postfix list.
-----------------------------------------------------
*/
intopost( infix, postfix)
char *infix, *postfix;
{
int st;
/* A */ push ('(');
while (*infix != '¥0') {
#ifdef TRACE
printf("*infix: %c¥n",*infix);
#endif
/* B */ if ( isspace(*infix)) {
;
}
/* C */ else if (isalpha(*infix)) {
*postfix++ = *infix;
}
/* D */ else if (*infix == '(') {
push('(');
}
/* E */ else if (*infix == ')') {
while ((st = pop()) != '(')
*postfix++ = st;
}
/* F */ else if (*infix == '*' || *infix == '/') {
while (1) {
if ((st = pop()) == '(' || st == '+'
|| st == '-') {
push(st);
break;
}
*postfix++ = st;
}
push(*infix);
}
/* G */ else if (*infix == '+' || *infix == '-') {
while (1) {
if ((st = pop()) == '(') {
push(st);
break;
}
*postfix++ = st;
}
push(*infix);
}
/* H */ else {
printf("Unknown input character %c¥n",
*infix);
}
++infix;
continue;
}
/* I */ while ((st = pop()) != '(')
*postfix++ = st;
/* J */ *postfix = '¥0';
}
intopost3_c
/* convert infix notation to postfix notation */
#define TRACE
#include <stdio_h>
#include "intopost1_c"
#include "intopost2_c"
main()
{
char infix_str[200];
char postfix_str[200];
while (1) {
printf("Enter Infix: ");
if (gets(infix_str) == NULL)
break;
intopost(infix_str, postfix_str);
printf(" postfix: %s¥n", postfix_str);
}
return 0;
}