I have found numerous examples involving only arithmetic operations but mine requires to deal with functions - min(x, y), max(x, y), sqrt(x), abs(x), fact(x). What I don't understand is how my program can interpret those functions and set the precedence for them.
Examples:
4 + 5 -> 4 5 +
abs(‐5) -> ‐5 abs
120 – (45+3) -> 120 45 3 + ‐
(3^2 + 4^5)*fact(3) -> 3 2 ^ 4 5 ^ + 3 fact *
min(3‐(4‐7) , (2+4)/3) -> 3 4 7 ‐ ‐ 2 4 + 3 / min

The code below is one of the examples I found on the internet. Since I'm dealing with functions, I guess I'll have to use an array of char so I can read functions but I'm having trouble where to start. Thanks for your help.

[edit] I have an idea came up. Still not sure about the precedence of function, but please leave your input. I'll be back in few moments ;p

Recommended Answers

All 2 Replies

Well, C and C++ are infix expression languages, so you need to read the postfix input, convert it to an evaluation tree, and then process the tree. I've done this before (about 25 years ago), but it isn't particularly simple. A good text on the subject is Donald Knuth's seminal book, "The Art of Computer Programming, Volume 1, Fundamental Algorithms". He goes into this in detail. If you are a serious computer programming student, his 3 (now 4 or 5 - he just released another volume or two after 40 something years) volume set is something that should have a prominent place on your book shelf. I've had my set for 30 years now, and I still refer to it from time to time.

#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define MAX 10
#define EMPTY -1

struct stack {
    char data[MAX];
    int top;
};

int isempty(struct stack *s) {
    return (s->top == EMPTY) ? 1 : 0;
}

void emptystack(struct stack* s) {
    s->top = EMPTY;
}

void push(struct stack* s, int item) {
    if (s->top == (MAX - 1)) {
        printf("\nSTACK FULL");
    } else {
        ++s->top;
        s->data[s->top] = item;
    }
}

char pop(struct stack* s) {
    char ret = (char) EMPTY;
    if (!isempty(s)) {
        ret = s->data[s->top];
        --s->top;
    }
    return ret;
}

void display(struct stack s) {
    while (s.top != EMPTY) {
        printf("\n%d", s.data[s.top]);
        s.top--;
    }
}

int isoperator(char e) {
    if (e == '+' || e == '-' || e == '*' || e == '/' || e == '^')
        return 1;
    else
        return 0;
}

int precedence(char e) {
    int pri = 0;

    if (e == '*' || e == '/' || e == '^')
        pre = 2;
    else if (e == '+' || e == '-')
        pre = 1;
    else
        pre = 3;
    return pre;
}

void infix2postfix(char* infix, char * postfix, int insertspace) {
    char *i, *p;
    struct stack X;
    char n1;
    emptystack(&X);
    i = &infix[0];
    p = &postfix[0];

    while (*i) {
        while (*i == ' ' || *i == '\t') {
            i++;
        }

        if (isdigit(*i)) {
            while (isdigit(*i)) {
                *p = *i;
                p++;
                i++;
            }
            /*SPACE CODE*/
            if (insertspace) {
                *p = ' ';
                p++;
            }
            /*END SPACE CODE*/
        }

        if (*i == '(') {
            push(&X, *i);
            i++;
        }

        if (*i == ')') {
            n1 = pop(&X);
            while (n1 != '(') {
                *p = n1;
                p++;
                /*SPACE CODE*/
                if (insertspace) {
                    *p = ' ';
                    p++;
                }
                /*END SPACE CODE*/
                n1 = pop(&X);
            }
            i++;
        }

        if (isoperator(*i)) {
            if (isempty(&X))
                push(&X, *i);
            else {
                n1 = pop(&X);
                while (precedence(n1) >= precedence(*i)) {
                    *p = n1;
                    p++;
                    /*SPACE CODE*/
                    if (insertspace) {
                        *p = ' ';
                        p++;
                    }
                    /*END SPACE CODE*/
                    n1 = pop(&X);
                }
                push(&X, n1);
                push(&X, *i);
            }
            i++;
        }

        if (isalpha(*i)) {
        }
        /*SPACE CODE*/
        if (insertspace) {
            *p = ' ';
            p++;
        }
        /*END SPACE CODE*/
    }

    while (!isempty(&X)) {
        n1 = pop(&X);
        *p = n1;
        p++;
        /*SPACE CODE*/
        if (insertspace) {
            *p = ' ';
            p++;
        }
        /*END SPACE CODE*/
    }
    *p = ' ';
}

int main() {
    char in[50], post[50];

    strcpy(&post[0], "");
    printf("Enter Infix Expression : ");
    fflush(stdin);
    gets(in);
    infix2postfix(&in[0], &post[0], 0);
    printf("Postfix Expression is : %s\n", &post[0]);

    return 0;
}

I'm trying to implement a case when *i is an alphabet which means it's a start of function in the infix expression. I want to read till it's no longer alphabet, save it in array of char and push/pop into stack. I gave alphabet pre(precedence) of 3. And that's where I'm stuck. I'm gonna go to bed, wake up with fresh brain and continue working on it. I appreciate your input.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.