C Reverse Polish notation expression evaluator

[BenJones]

// Small Reverse Polish notation expression evaluator
// By Ben Jones a.k.a DreamVB
// Date 25/8/24
// Last-Update 20:46 pm

//Thanks to 2kaud for giving me some ideas for fixes

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

#define MAX_TOKENS 1024
#define MAX_BUFFER 30
#define MAX_STACK 256
#define MAX_VARS 256
#define MAX_VAR_NAME 30

#define ERR_EMPTY_EXPR 100
#define ERR_UNDERFLOW 101
#define ERR_DIVBY_ZERO 102
#define ERR_UNK_TOKEN 103
#define ERR_OVERFLOW 104


#define PI 3.14159265358979323846

//Variable data
struct TVars{
    char name[MAX_VAR_NAME];
    double value;
};

struct TVars _vars[MAX_VARS];
int var_count = 0;

double stk[MAX_STACK] = {0.0};
int stk_ptr = -1;

void _die(int);
int var_index(char *);
void set_var(char*, double);
double get_var_value(char *);

double rpn_exp(char *);
int is_number(char *);
int is_op(char);
void u_case(char *);
//Maths functions
double sqr(double);
double _max(double, double);
double _min(double, double);
//Stack stuff
int stk_size(void);
double stk_pop();
void stk_push(double);

void _die(int ab_code){
    //Display banner and error message and exit.
    printf("Ben's Reverse Polish Notation Calculator.\n");
    printf("Version 1.4");
    printf("\nError Code: 0x%x\n",ab_code);
    printf("Error: ");

    //Display error message
    switch(ab_code){
        case ERR_EMPTY_EXPR:
            printf("Empty expression.");
            break;
        case ERR_UNDERFLOW:
            printf("Stack underflow.");
            break;
        case ERR_DIVBY_ZERO:
            printf("Division by zero.");
            break;
        case ERR_UNK_TOKEN:
            printf("Unknown token found.");
            break;
        case ERR_OVERFLOW:
            printf("Stack overflow");
            break;
    }

    printf("\n");
    //Play a beep
    printf("%c",7);
    exit(EXIT_FAILURE);
}

int var_index(char *vname){
    //Find the index of a variable in the variable type
    int ndx = -1;
    register int x;

    for(x = 0; x < var_count;x++){
        //Compare two values
        if(strcmp(_vars[x].name,vname) == 0){
            //Variable found set ndx to x
            ndx = x;
            //Break out of loop
            break;
        }
    }
    //Return found index
    return ndx;
}

void set_var(char* vname, double vdata){
    //Adds or sets a variables data
    char temp[MAX_VAR_NAME];
    //We need to copy vname to temp
    strcpy(temp,vname);
    //Upper-case temp
    u_case(temp);
    //Find the variable index
    int ndx = var_index(temp);
    //If error index was found add a new variable and data
    if(ndx == -1){
        //Copy temp to _vars[n].name
        strcpy(_vars[var_count].name,temp);
        //Set the variables data
        _vars[var_count].value = vdata;
        var_count++;
    }else{
        //Editing a variable using existing index
        _vars[ndx].value = vdata;
    }
}

double get_var_value(char *name){
    char temp[MAX_VAR_NAME];
    //Copy name to temp
    strcpy(temp,name);
    //Upper-case temp
    u_case(temp);
    //Find the variable index
    int ndx = var_index(temp);
    return ndx == -1 ?  0.0 : _vars[ndx].value;
}

void stk_push(double value){
    if(stk_ptr >= MAX_STACK - 1){
        _die(ERR_OVERFLOW);
    }
    stk[++stk_ptr] = value;
}

double stk_pop(){
    double value;
    if(stk_ptr < -1){
        _die(ERR_UNDERFLOW);
    }
    value = stk[stk_ptr--];
    return value;
}

int stk_size(){
    return stk_ptr;
}

double sqr(double x){
    return x * x;
}

double _max(double a, double b){
    //Just finds the maximum of two values
    return a > b ? a : b;
}

double _min(double a, double b){
    //Just finds the minimum of two values
    return a < b ? a : b;
}

int is_op(char c){
    //This function return 1 of we have an operator or 0 if not
    return strchr("+-*/%^", c) ? 1 : 0;
}

void u_case(char *s){
    //Upper-case string
    while(*s){
        *s = toupper(*s);
        ++s;
    }
}

int is_number(char *s){
    //Check to see if we have a number.
    char* s0;
    double number;
    number = strtod(s, &s0);
    return s0 == s ? 0 : 1;
}

double rpn_exp(char *expr){
    register int x;
    register int y;
    register int total;
    char buffer[MAX_BUFFER] = {'\0'};
    char tokens[MAX_TOKENS][MAX_BUFFER];
    double a = 0.0;
    double b = 0.0;
    y = 0;
    total = 0;

    //Break up the string into parts breaking were there is a space
    for(x = 0;x < strlen(expr);x++){
        if(isspace(expr[x])){
            //Check buffer length
            if(strlen(buffer) > 0){
                //Copy buffer to tokens array
                strcpy(tokens[total],buffer);
                //INC tokens count
                total++;
                //Reset y to zero
                y = 0;
            }
        }else{
            //Not a space so must be other char so build the buffer string
            buffer[y] = toupper(expr[x]);
            //INC y
            y++;
        }
        //Add ending for buffer
        buffer[y] = '\0';
    }
    //Check if there is anything left in buffer
    if(strlen(buffer) > 0){
        //Copy buffer to tokens array
        strcpy(tokens[total],buffer);
        //INC tokens array count
        total++;
    }
    //Reset x
    x = 0;

    //Check that we have tokens
    if(total < 1){
        _die(ERR_EMPTY_EXPR);
    }
    //Below here we parse the tokens and do the calculations
    for(x = 0; x < total;x++){
        //Check if we have a number
        if(is_number(tokens[x])){
            //Push the number onto the stack
            stk_push(atof(tokens[x]));
        }else{
            //Not a number maybe a operator of function
            //Pop off the two top items on the stack
            if(is_op(tokens[x][0])){
                if(stk_size() < 1){
                    _die(ERR_UNDERFLOW);
                }
                b = stk_pop();
                a = stk_pop();
                //Do the calc and push back the result onto the stack
                switch(tokens[x][0]){
                    case '+':
                        stk_push(a + b);
                        break;
                    case '-':
                        stk_push(a - b);
                        break;
                    case '*':
                        stk_push(a * b);
                        break;
                    case '/':
                        //Need to test for division by zero
                        if(a != 0.0){
                            stk_push(a / b);
                        }
                        else{
                            _die(ERR_DIVBY_ZERO);
                        }
                        break;
                    case '%':
                        //Need to test for division by zero
                        if(a != 0.0){
                            stk_push(fmod(a,b));
                        }else{
                            _die(ERR_DIVBY_ZERO);
                        }
                        break;
                    case '^':
                        stk_push(pow(a,b));
                        break;

                }
            }
            else{
                //Some functions
                if(strcmp(tokens[x],"MIN") == 0){
                    stk_push(_min(stk_pop(),stk_pop()));
                }else if(strcmp(tokens[x],"MAX") == 0){
                    stk_push(_max(stk_pop(),stk_pop()));
                }else if(strcmp(tokens[x],"DUP") == 0){
                    a = stk_pop();
                    stk_push(a);
                    stk_push(a);
                }else if(strcmp(tokens[x],"PI") == 0){
                    stk_push(PI);
                }else if(strcmp(tokens[x],"SQR") == 0){
                    stk_push(sqr(stk_pop()));
                }else if(strcmp(tokens[x],"SQRT") == 0){
                    stk_push(sqrt(stk_pop()));
                }else if(strcmp(tokens[x],"SIN") == 0){
                    stk_push(sin(stk_pop()));
                }else if(strcmp(tokens[x],"COS") == 0){
                    stk_push(cos(stk_pop()));
                }else if(strcmp(tokens[x],"TAN") == 0){
                    stk_push(tan(stk_pop()));
                }else if(strcmp(tokens[x],"ASIN") == 0){
                    stk_push(asin(stk_pop()));
                }else if(strcmp(tokens[x],"ACOS") == 0){
                    stk_push(acos(stk_pop()));
                }else if(strcmp(tokens[x],"ATAN") == 0){
                    stk_push(atan(stk_pop()));
                }else if(strcmp(tokens[x],"EXP") == 0){
                    stk_push(exp(stk_pop()));
                }else if(strcmp(tokens[x],"LN") == 0){
                    stk_push(log(stk_pop()));
                }else if(strcmp(tokens[x],"LOG10") == 0){
                    stk_push(log10(stk_pop()));
                }else{
                    //Must be a variable
                    if(var_index(tokens[x]) != -1){
                        stk_push(get_var_value(tokens[x]));
                    }else{
                        _die(ERR_UNK_TOKEN);
                    }
                }
            }
        }
    }
    //Return the top item of the stack.
    return stk_pop();
}

int main()
{
    set_var("first",20);
    set_var("second",50);

    printf("%lf\n",rpn_exp("10 2 / 5 *"));
    printf("%lf\n",rpn_exp("22 7 /"));
    printf("%lf\n",rpn_exp("5 dup +"));
    printf("%lf\n",rpn_exp("2 4 ^"));
    printf("%lf\n",rpn_exp("10 50 max"));
    printf("%lf\n",rpn_exp("3 2 min"));
    printf("%lf\n",rpn_exp("3 sqr"));
    printf("%lf\n",rpn_exp("20 sqrt"));
    printf("%lf\n",rpn_exp("PI"));
    printf("%lf\n",rpn_exp("first second +"));

    return EXIT_SUCCESS;
}

[wqweto]

Nice effort but literally asked ChatGPT this:

Need reverse polish notation evaluator in plain C which understands standard operators and SQR, SIN, COS, TAN, ASIN, ACOS, ATAN, EXP, LN, LOG10 functions

. . . and got this output:

Here's a C program that evaluates Reverse Polish Notation (RPN) expressions, supporting standard arithmetic operators (+, -, *, /, %) and additional mathematical functions (SQR, SIN, COS, TAN, ASIN, ACOS, ATAN, EXP, LN, LOG10).

RPN Evaluator in C

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_STACK 100
#define MAX_TOKEN_LEN 20

// Stack structure to hold the operands
typedef struct {
    double data[MAX_STACK];
    int top;
} Stack;

void push(Stack *s, double value) {
    if (s->top == MAX_STACK - 1) {
        printf("Stack overflow\n");
        exit(EXIT_FAILURE);
    }
    s->data[++(s->top)] = value;
}

double pop(Stack *s) {
    if (s->top == -1) {
        printf("Stack underflow\n");
        exit(EXIT_FAILURE);
    }
    return s->data[(s->top)--];
}

int isOperator(const char *token) {
    return strlen(token) == 1 && strchr("+-*/%", token[0]) != NULL;
}

int isFunction(const char *token) {
    return strcmp(token, "SQR") == 0 || strcmp(token, "SIN") == 0 ||
           strcmp(token, "COS") == 0 || strcmp(token, "TAN") == 0 ||
           strcmp(token, "ASIN") == 0 || strcmp(token, "ACOS") == 0 ||
           strcmp(token, "ATAN") == 0 || strcmp(token, "EXP") == 0 ||
           strcmp(token, "LN") == 0 || strcmp(token, "LOG10") == 0;
}

double evaluateOperator(double a, double b, char op) {
    switch (op) {
    case '+':
        return a + b;
    case '-':
        return a - b;
    case '*':
        return a * b;
    case '/':
        return a / b;
    case '%':
        return fmod(a, b);
    default:
        printf("Unknown operator: %c\n", op);
        exit(EXIT_FAILURE);
    }
}

double evaluateFunction(const char *func, double x) {
    if (strcmp(func, "SQR") == 0)
        return x * x;
    else if (strcmp(func, "SIN") == 0)
        return sin(x);
    else if (strcmp(func, "COS") == 0)
        return cos(x);
    else if (strcmp(func, "TAN") == 0)
        return tan(x);
    else if (strcmp(func, "ASIN") == 0)
        return asin(x);
    else if (strcmp(func, "ACOS") == 0)
        return acos(x);
    else if (strcmp(func, "ATAN") == 0)
        return atan(x);
    else if (strcmp(func, "EXP") == 0)
        return exp(x);
    else if (strcmp(func, "LN") == 0)
        return log(x);
    else if (strcmp(func, "LOG10") == 0)
        return log10(x);
    else {
        printf("Unknown function: %s\n", func);
        exit(EXIT_FAILURE);
    }
}

void evaluateRPN(const char *expression) {
    Stack stack = {.top = -1};
    char token[MAX_TOKEN_LEN];
    const char *delimiter = " ";
    char *expCopy = strdup(expression); // Duplicate the expression string for tokenizing
    char *ptr = strtok(expCopy, delimiter);

    while (ptr != NULL) {
        if (isOperator(ptr)) {
            double b = pop(&stack);
            double a = pop(&stack);
            push(&stack, evaluateOperator(a, b, ptr[0]));
        } else if (isFunction(ptr)) {
            double x = pop(&stack);
            push(&stack, evaluateFunction(ptr, x));
        } else { // Operand
            push(&stack, atof(ptr));
        }
        ptr = strtok(NULL, delimiter);
    }

    printf("Result: %.10g\n", pop(&stack));
    free(expCopy);
}

int main() {
    const char *expression = "3 4 + 2 * 7 /"; // Example expression
    evaluateRPN(expression);

    const char *complexExpression = "9 2 / SIN 2 SQR + 1 + LOG10"; // More complex expression
    evaluateRPN(complexExpression);

    return 0;
}

Explanation:

1. Stack Operations:

- push: Adds a value to the stack.
- pop: Removes and returns the top value from the stack.

2. Token Identification:

- isOperator: Checks if the token is a standard arithmetic operator.
- isFunction: Checks if the token is one of the supported mathematical functions.

3. Evaluation Functions:

- evaluateOperator: Evaluates binary operations (+, -, *, /, %).
- evaluateFunction: Evaluates mathematical functions (SQR, SIN, COS, TAN, etc.).

4. RPN Evaluation:

- The evaluateRPN function processes the RPN expression token by token.
- For operators and functions, it pops the necessary operands, applies the operation or function, and pushes the result back onto the stack.
- Finally, the result of the expression is printed.

5. Main Function:

- Demonstrates how to evaluate simple and complex RPN expressions.

Example Expressions:

- "3 4 + 2 * 7 /": This evaluates to (3 + 4) * 2 / 7 = 2.
- "9 2 / SIN 2 SQR + 1 + LOG10": This evaluates the sine of 9 / 2, squares 2, adds the results, adds 1, and then computes the log base 10 of the result.

This program should cover most common operations and mathematical functions that you would need in an RPN evaluator.

When run the code actually outputs this:

Result: 2
Result: 0.6044928011

cheers,
</wqw>

[BenJones]

Thanks for the info I never needed to use ChatGPT I used the one on bing but noticed it gives back not very good code, plus I learn better writeing things my self then cheating and using something to do the work for me.

anyway I done a quick update added var support now and a few other functions.

[2kaud]

@benJones. A couple of comments:

1) Have you come across the c tertiary operator?

 if(ndx == -1){
        //If error index return 0.0
        return 0.0;
    }else{
        //Return variables value at index ndx
        return _vars[ndx].value;
    }

becomes simply:

return ndx == -1 ?  0.0 : _vars[ndx].value;

and similar in other parts (eg _max(), _min() etc).

2) is_number() doesn't flag as error where there is more than one . is within a number. Rather than do a check for is-a-number and then later doing a atof() conversion, you could use strtod() which does the conversion and returns a pointer to the char which caused the conversion to stop. You then check this to determine if it is a valid number of not.

3) ++s and s++ (and --s and s--) return a value. ++s the value after the inc and s-- the value before the inc. These can be used where a value is required. eg

 stk_ptr++;
    stk[stk_ptr] = value;

becomes:

    stk[++stk_ptr] = value;

and similar elsewhere.

4) Do you know about strchr()? This will simplify is_op()

int is_op(char c){
    return strchr("+-*/%", c) ? 1 : 0;
    // Or simply
   // return !!strchr("+-*/%", c);
}

5) strtok() will simplify the code to break up the input string into parts. You then don't need the buffer and tokens arrays as strtok() replaces delim with null and hence expr can be used directly for evaluation. The downside, of course, is that the c_string used must be able to be modified so can't be used with a const char*. Even with a simple string copy from a const char* to a char* if required strtok() has many advantages.

[BenJones]

Thanks 2kaud for the suguestions I look into it today sometime. I not long took up C agian so I am a little rusty on things. thanks agian helps a lot.

[2kaud]

Once you're got reverse polish (postfix) expression evaluator, are you going to do an infix to postfix convertor so that you have a standard calculator that understands brackets, functions etc? There are two common ways of doing this - shunting yard and recursive descent. There's also ^ for raised to (eg 2^4 is 16). Note that +- and */ are evaluated left to right for the same precedence but multiple ^ are evaluated right to left (eg 2^3^4 is 2^(3^4) ). Note that functions (sin etc) will need brackets.

[BenJones]

I am thinking of doing postfix in the future I did an expression evaluator years back in visual basic that could do as you suggested so I may also have a go at converting that over to., my idea for making this little RPN was to try and make some kind of forth like interpreter just see how things pan out for now. I investigate that shunting yard, Thank agian for your help.

[BenJones]

Made some simple chnages see the update

[2kaud]

value = stk[stk_ptr];
stk_ptr--;

becomes:

value = stk[stk_ptr--];

[BenJones]

value = stk[stk_ptr];
stk_ptr--;

becomes:

value = stk[stk_ptr--];

Thanks updated now