Code:
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#include <ctype.h>
#define MAX 20
typedef struct stackA {
char token[5];
struct stackA *next;
} stack;
typedef struct nodeA {
char token[5];
struct nodeA *next;
} node;
typedef node* node_ptr;
typedef struct {
node *front;
node *rear;
} q;
typedef q* q_ptr;
typedef stack* stack_ptr;
char *convert(char input[]);
char *pop(stack_ptr S);
void push(char s[], stack_ptr S);
int isEmpty(stack_ptr S);
void enqueue(char s[], q_ptr Q);
char *dequeue(q_ptr Q);
int isOperator(char s[]);
char *top(stack_ptr S);
int getISP(char s[]);
int getICP(char s[]);
int main(void) {
char input[MAX], postfix[MAX], try_again;
int choice, error, answer;
do {
clrscr();
error=0;
puts("Enter the infix notation:");
fgets(input,sizeof(input),stdin); /* to prevent buffer overflow*/
strcpy(postfix,convert(input));
printf("\nConverted to postfix: %s",postfix);
puts("\nDo you wish to try again? (type \"N\" to quit, any other to repeat)");
try_again=getchar();
} while(!(try_again == 'N' || try_again == 'n'));
}
char *convert(char input[]) {
char *p, *q, *r, output[MAX];
char s[]=" "; /*used for the strtok() function to separate the tokens*/
int flag=0, ISP, ICP;
q_ptr Q;
stack_ptr S;
S=malloc(sizeof(stack)); /*creates the stack for conversion*/
S->next=NULL;
Q=malloc(sizeof(q)); /*creates the queue for storing individual tokens*/
Q->front=malloc(sizeof(node));
Q->rear=Q->front;
Q->front->next=NULL;
p=strtok(input,s);
enqueue(p, Q);
while((p=strtok(NULL, s)) != NULL) /*separates the string into individual tokens*/
enqueue(p, Q); /*stores the tokens as strings in the queue*/
while((p=dequeue(Q))!=NULL) { /*while there is a token*/
if(isdigit(p[0])) { /*if the token is an operand*/
strcat(output,p);
strcat(output," ");
}
else if(strcmp(p,"(") == 0) /*if the token is a left grouping symbol*/
push(p,S);
else if(strcmp(p,")") == 0) { /*if the token is a right grouping symbol*/
flag=1;
while(flag==1) {
q=pop(S);
if(isOperator(q)) { /*appends the operator to postfix expression*/
strcat(output,q);
strcat(output," ");
}
else if(strcmp(q,"("))
flag=0;
}
}
else if(isOperator(p)) {
q=top(S);
while((ISP=getISP(q)) >= (ICP=getICP(p))) {
strcat(output,pop(S));
strcat(output," ");
q=top(S);
}
push(p,S);
}
else ;
}
while(!isEmpty(S)) {
strcat(output,pop(S));
strcat(output," ");
}
return output;
}
char *pop(stack_ptr S) {
stack_ptr temp;
char s[5];
temp=S->next;
if(temp != NULL) {
S->next=temp->next;
strcpy(s,temp->token);
free(temp);
return s;
}
else return NULL;
}
void push(char *s, stack_ptr S) {
stack_ptr temp;
temp=malloc(sizeof(stack));
strcpy(temp->token,s);
temp->next=S->next;
S->next=temp;
}
int isEmpty(stack_ptr S) {
return ((S->next)==NULL);
}
void enqueue(char *s, q_ptr Q) {
node_ptr temp;
temp=malloc(sizeof(node));
strcpy(temp->token,s);
Q->rear->next=temp;
Q->rear=temp;
Q->rear->next=NULL;
}
char *dequeue(q_ptr Q) {
node_ptr temp;
char s[5];
if((Q->front) == (Q->rear))
return NULL;
else {
temp=Q->front->next;
strcpy(s,temp->token);
Q->front->next=temp->next;
if(Q->rear == temp)
Q->rear=Q->front;
free(temp);
}
return s;
}
int isOperator(char *s) {
if(strcmp(s,"+")==0 || strcmp(s,"-")==0 || strcmp(s,"*")==0 || strcmp(s,"/")==0)
return 1;
else return 0;
}
char *top(stack_ptr S) {
char s[5];
strcpy(s,S->next->token);
return s;
}
int getISP(char *s) {
if(strcmp("+",s)==0)
return 1;
else if(strcmp("-",s)==0)
return 1;
else if(strcmp("*",s)==0)
return 2;
else if(strcmp("/",s)==0)
return 2;
else if(strcmp("(",s)==0)
return 0;
else return 0;
}
int getICP(char *s) {
if(strcmp("-",s)==0)
return 1;
else if(strcmp("-",s)==0)
return 1;
else if(strcmp("*",s)==0)
return 2;
else if(strcmp("/",s)==0)
return 2;
else if(strcmp("(",s)==0)
return 3;
else return 0;
}
Originally Posted by sangken
