Results 1 to 10 of 10

Thread: C Reverse Polish notation expression evaluator

  1. #1

    Thread Starter
    Fanatic Member BenJones's Avatar
    Join Date
    Mar 2010
    Location
    Wales UK
    Posts
    745

    Post C Reverse Polish notation expression evaluator

    Code:
    // 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;
    }
    Last edited by BenJones; Aug 26th, 2024 at 11:30 AM. Reason: Updated code

  2. #2
    PowerPoster wqweto's Avatar
    Join Date
    May 2011
    Location
    Sofia, Bulgaria
    Posts
    5,525

    Re: C Reverse Polish notation expression evaluator

    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
    Code:
    #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:

    Code:
    Result: 2
    Result: 0.6044928011
    cheers,
    </wqw>

  3. #3

    Thread Starter
    Fanatic Member BenJones's Avatar
    Join Date
    Mar 2010
    Location
    Wales UK
    Posts
    745

    Re: C Reverse Polish notation expression evaluator

    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.

  4. #4
    Frenzied Member 2kaud's Avatar
    Join Date
    May 2014
    Location
    England
    Posts
    1,116

    Re: C Reverse Polish notation expression evaluator

    @benJones. A couple of comments:

    1) Have you come across the c tertiary operator?

    Code:
     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:

    Code:
    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

    Code:
     stk_ptr++;
        stk[stk_ptr] = value;
    becomes:

    Code:
        stk[++stk_ptr] = value;
    and similar elsewhere.

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

    Code:
    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.
    Last edited by 2kaud; Aug 25th, 2024 at 06:54 AM.
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  5. #5

    Thread Starter
    Fanatic Member BenJones's Avatar
    Join Date
    Mar 2010
    Location
    Wales UK
    Posts
    745

    Re: C Reverse Polish notation expression evaluator

    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.

  6. #6
    Frenzied Member 2kaud's Avatar
    Join Date
    May 2014
    Location
    England
    Posts
    1,116

    Re: C Reverse Polish notation expression evaluator

    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.
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  7. #7

    Thread Starter
    Fanatic Member BenJones's Avatar
    Join Date
    Mar 2010
    Location
    Wales UK
    Posts
    745

    Re: C Reverse Polish notation expression evaluator

    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.

  8. #8

    Thread Starter
    Fanatic Member BenJones's Avatar
    Join Date
    Mar 2010
    Location
    Wales UK
    Posts
    745

    Re: C Reverse Polish notation expression evaluator

    Made some simple chnages see the update

  9. #9
    Frenzied Member 2kaud's Avatar
    Join Date
    May 2014
    Location
    England
    Posts
    1,116

    Re: C Reverse Polish notation expression evaluator

    Code:
    value = stk[stk_ptr];
    stk_ptr--;
    becomes:

    Code:
    value = stk[stk_ptr--];
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  10. #10

    Thread Starter
    Fanatic Member BenJones's Avatar
    Join Date
    Mar 2010
    Location
    Wales UK
    Posts
    745

    Re: C Reverse Polish notation expression evaluator

    Quote Originally Posted by 2kaud View Post
    Code:
    value = stk[stk_ptr];
    stk_ptr--;
    becomes:

    Code:
    value = stk[stk_ptr--];
    Thanks updated now

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width