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;
}

Edited 2 Years Ago by blue_Student: wrong titel

(1) Use your compiler's debugger so that you can step through the execution of the program and see where it stops.

(2) or scatter some print statements around.

This article has been dead for over six months. Start a new discussion instead.