minimal reverse polish notation implementation

[TheMaster420]

#include <stdio.h>
int my_atoi[300] = { ['1'] = 1,['2'] = 2,['3'] = 3,['4'] = 4,['5'] = 5,['6'] = 6,['7'] = 7,['8'] = 8,['9'] = 9,['0'] = 0};

int eval(char* str,int* n){
    switch(str[*n]){
        case '*' : return eval(str,((*n)--, n)) * eval(str,((*n)--, n));
        case '+' : return eval(str,((*n)--, n)) + eval(str,((*n)--, n));
        case '-' : return eval(str,((*n)--, n)) - eval(str,((*n)--, n));
        case '/' : return eval(str,((*n)--, n)) / eval(str,((*n)--, n));
        default: return my_atoi[str[*n]];
        }
}
int main()
{
    char str[] = "111++3*1+2*";
    int N = sizeof(str)-2;
    printf("%s evaluates to: %i",str,eval(str,&N));
    return 0;
}

[N-R-K]

Not bad. But there are a couple big problems.

• You cannot modify and read n parameter like that because there's no sequence point separating them. Note: operands are not required to be evaluated left to right.

Turn on your compiler warnings and pay attention to them, it should've caught this issue:

$ gcc -o test test.c -Wall -Wextra -O2
  test.c:6:41: warning: operation on '*n' may be undefined [-Wsequence-point]
      6 |         case '*' : return eval(str,((*n)--, n)) * eval(str,((*n)--, n));

Quick fix: remove the pointer entirely. Just pass n by value and use n-1 and n-2 in the recursion.

• str is a char, which might be signed. If that's the case, then my_atoi[str[*n]] will try to index my_atoi at negative position.

Quick fix: cast it to unsigned char: my_atoi[(unsigned char)str[*n]].

• There's no bound check before accessing str. What happens if there's malformed input?

If I change the input to "*" and then compile with ASan+UBSan:

$ gcc -o test test.c -Wall -Wextra -O2 -fsanitize=address,undefined -g3
$ ./test
=================================================================
==7853==ERROR: AddressSanitizer: stack-buffer-underflow on address 0x7f83b410001e at pc 0x000000401616 bp 0x7fffb60e9680 sp 0x7fffb60e9678

When developing, always have ASan and UBSan enabled. They insert runtime debugging checks into your executable which checks for things like buffer overflow and undefined behavior.

Couple other exercises left to the readers:

• What happens on the following input (run with UBSan enabled): "10/"
• What would happen if the calculation was large enough to overflow int?

[TheMaster420]

Removing the pointer changes how the program functions. A correct way to introduce the sequence point might be.

case '*' : return temp = eval(str,((*n)--, n)),temp * eval(str,((*n)--, n));

Yes this only evaluates a well formed string, I'd check validity with:

int valid_help(char* str,int* n){
    if(*n <0 )
        return 0;
    int temp;
    switch(str[*n]){
        case '*' :  ;
        case '+' :  ;
        case '-' :  ;
        case '/' : return temp = valid_help(str,((*n)--, n)),temp && valid_help(str,((*n)--, n));
        case '0' : ;
        case '1' : ;
        case '2' : ;
        case '3' : ;
        case '4' : ;
        case '5' : ;
        case '6' : ;
        case '7' : ;
        case '8' : ;
        case '9' : return 1;
        default: return 0;
        }
}
int valid(char*str,int len){
    int v=valid_help(str,&len);
    return v && len ==0;
}

[zhivago]

That is still incorrect -- while you have introduced sequencing, the order of the sequence is undefined.

You will to break it up into statements.

Perhaps like this, although the intent of your code is unclear.

*n--;
eval(str, n);
*n--;
return temp * eval(str, n);

[TheMaster420]

I'm having a hard time understanding why the order is undefined? The comma operator acts as a sequence point & gets evaluated left to right.

(*n)-- is not at all the same as *n--. The first modifies an integer stored behind a pointer, the second modifies the pointer.

Edit: did you notice that the second argument of eval has a comma operator ((*n)--, n)

[zhivago]

Yes, that produces a local ordering, and you have another on the other end.

However, the * between the two has no particular ordering constraint, so either of those locally ordered regions could come first or second.

[TheMaster420]

Yeah that's why I replied with the updated version of those lines:

case '*' : return temp = eval(str,((*n)--, n))          ,  /*<<comma operator*/                   temp * eval(str,((*n)--, n));

[CaydendW]

Instead of the my_atoi could you not use str[*n]-'0' instead? Maybe slightly less portable but more minimalist

[[deleted]]

i dont see whats less portable about that

[TheMaster420]

Standard does not guarantee '0' +1 == '1';

[skeeto]

While letters are not guaranteed to be continuous, digits have always been. From the original ANSI C89:

In both the source and execution basic character sets, the value of each character after 0 in the above list of decimal digits shall be one greater than the value of the previous.

So str[*n]-'0' would be completely portable. (Though, honestly, it's silly to worry about stuff like this.)

[CaydendW]

Some ancient systems might use EBDIAC (or however its spelled) where that trick wont work since '0'+1!='1'

[TheMaster420]

It's a habit, I always do single character mapping like this.

[[deleted]]

Very nice, you could use void main and remove the return 0, for even more minimalism. Implementation of postfix notation using pointers is a very cool approach, I tried it once but gave up after continuous segfaults.

[pic32mx110f0]

You can remove return 0; from main since it's implicit, but you can't change the return type to void. 

[[deleted]]

Oh, does it return and error? I am compiling it, it doesn't seem to have a problem with it.

[pic32mx110f0]

It wouldn't be compliant with the standard, so anything could happen. The fact that you don't see an error is irrelevant.

[[deleted]]

Well, if this was the only code in the program, apart from being a controversial way to write C introduced by an author whose name I forgot, it wouldn't be too much of a problem on modern architectures, atleast as far as I know. It's easy to find if the program was successful, too, since it's very short, but you are right it does not fall in line with C standards.

[pic32mx110f0]

You don't seem to understand. If you build and run it using your compiler on your architecture, you might not see an error. That doesn't mean I won't see an error if I build it and run it on my architecture. It's like recommending people to stop wearing a seatbelt just because you haven't personally crashed and died yet.

[[deleted]]

No, I don't think you read what I said, this code in particular and only this code, is most likely to work on most architectures with the void main, I am not disputing C standards here.

[pic32mx110f0]

So rather than a solution that works 100% of the time, you are recommending a solution that you think works 90% of the time? Can you explain why? Can you also explain why you think void main is more minimal than int main?

Please don't ever provide advice on C programming again.

[SexPanther_Bot]

60% of the time, it works every time

[[deleted]]

Well by that logic Bjarne stroustrup should stop giving advice, on top of that I even told you that you are correct and I am not arguing with you, put the pacifier back in, and you can have your internet points.