Hi, I've been testing about converting infix to postfix expression. I've made the code and it compiles. My problem is it stops working when I run it. This involves the use of stack and arrays. I just call the method polish to get the strings infix and postfix, and to run the other methods, like findRank to know if it is a well formed postfix exp'n and evaluate it in method evaluate(). Please give me some ideas on how to fix this. This is the code...
/* From Infix Notation to Postfix form,
Knowing if it is Well-Formed,
and Evaluation of its Postfix Expression
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#include <ctype.h>
typedef char StackElemType;
typedef struct stacknode StackNode;
struct stacknode {
StackElemType info;
StackNode *link;
};
struct stack {
StackNode *top;
};
typedef struct stack Stack;
void initStack(Stack *S) {
S->top = NULL;
}
int isEmptyStack(Stack *S) {
return (S->top == NULL);
}
void StackOverflow(void) {
printf("Stack overflow detected.\n");
exit(1);
}
void StackUnderflow(void) {
printf("Stack underflow detected.\n");
exit(1);
}
void push(Stack *S, StackElemType *x) {
StackNode *alpha;
alpha = (StackNode *) malloc(sizeof(StackNode));
if(alpha == NULL)
StackOverflow();
else {
alpha->info = *x;
alpha->link = S->top;
S->top = alpha;
}
}
void pop(Stack *S, StackElemType *x) {
StackNode *alpha;
if(S->top == NULL)
StackUnderflow();
else {
alpha = S->top;
*x = S->top->info;
S->top = S->top->link;
free(alpha);
}
}
int ICP(char x) {
if((x == '+') || (x == '-'))
return 1;
else if((x == '*') || (x == '/'))
return 3;
else if(x == '^')
return 6;
}
int ISP(char x) {
if((x == '+') || (x == '-'))
return 2;
else if((x == '*') || (x == '/'))
return 4;
else if(x == '^')
return 5;
else
return 0;
}
int rank(char x) {
if ((isalpha(x)) || (isdigit(x)))
return 1;
else
return -1;
}
int IsOpnd(char x) {
if ((isalpha(x)) || (isdigit(x)));
return 1;
return 0;
}
double operate(double first, double sec, char opnd) {
int i = 0;
if (opnd == '+')
return (first + sec);
else if (opnd == '-')
return (first - sec);
else if (opnd == '*')
return (first * sec);
else if (opnd == '/')
return (first / sec);
else if (opnd == '^') {
for(i = 1; i < sec; i++) {
first *= first; }
return first;
}
}
double value (char var) {
double num = var - '0';
if(num > 16.0 && num < 43.0)
return (num - 16.0);
else if(num > 48.0 && num < 75.0)
return ((49.0 - num) - 1.0);
else
return num;
}
//Start of methods for Evaluating the Postfix Expression
typedef double StackEvalType;
typedef struct stackEvalnode StackEvalNode;
struct stackEvalnode {
StackEvalType info;
StackEvalNode *link;
};
struct stackEval {
StackEvalNode *top;
};
typedef struct stackEval StackEval;
void initStackEval(StackEval *S) {
S-> top = NULL;
}
int isEmptyStackEval(StackEval *S) {
return (S->top == NULL);
}
void pushEval(StackEval *S, StackEvalType *x) {
//like in the push()
}
void popEval(StackEval *S, StackEvalType *x) {
//like in pop
}
//If it is well formed in findRank(), do method evaluate
double evaluate(char postfix[], double answer) {
Stack T;
initStack(&T);
StackEval S;
initStackEval(&S);
int i;
answer = 0.0;
char x, first, sec;
for(i =0; i < strlen(postfix); i++) {
x = postfix[i];
if(IsOpnd(x)) {
push(&T, &x);
}
else {
pop(&T, &first);
pop(&T, &sec);
answer = operate(value(first), value(sec), x);
pushEval(&S, &answer);
}
}
popEval(&S, &answer);
return answer;
}
void findRank(char postfix[], int r) {
char x;
r = 0;
int i;
double ans;
for(i = 0; postfix[i] != '\0'; i++) {
x = postfix[i];
r += rank(x);
if (r < 1) {
printf("Postfix expression is not well-formed. Rank is %d. \n", r);
break;
}
}
if(r == 1) {
printf("Postfix expression is well-formed. Total rank is %d. \n", r);
printf("Evaluated value is %f", evaluate(postfix, ans));
}
}
//postfix[] needs size so that there are no gibberish things in its value
void polish(char infix[], char postfix[], int r) {
Stack S;
initStack(&S);
postfix = "";
int i;
char x, xtop;
for(i =0; i< strlen(infix); i++) {
x = infix[i];
if(IsOpnd(x)) {
postfix[strlen(postfix)] = x;
postfix[strlen(postfix) + 1] = 0;
}
else if(x == '(')
push(&S, &x);
else if(x == ')') {
while(!isEmptyStack(&S)) {
pop(&S, &xtop);
if(xtop != '(') { //concatenate
postfix[strlen(postfix)] = xtop;
postfix[strlen(postfix) + 1] = 0;
}
else if(isEmptyStack(&S)) {
printf("The postfix expression is %s", postfix);
findRank(postfix, r);
}
}
}
else {
while(!isEmptyStack(&S)) {
pop(&S, &xtop);
if(ICP(x) < ISP(xtop)){ //concatenate
postfix[strlen(postfix)] = xtop;
postfix[strlen(postfix) + 1] = 0;
}
else {
push(&S, &xtop);
push(&S, &x);
}
}
}
}
r = 0;
//End of polish
}
int main() {
char infix [200] = "((A+B)^2)";
char postfix[200];
int r = 0;
polish(infix, postfix, r);
return 0;
}
