### Problem with postfix expressions evalutation (stacks)

I am solving this problem on evaluating reverse polish notation expressions or postfix expressions involving integers between -2000000 and 2000000. The procedure is pretty straightforward:

 ``` if x is a number, put the number in stack if x is the operator +, pop two values b and a, and push a+b in stack if x is the operator -, pop two values b and a, and push a-b in stack if x is the operator *, pop two values b and a, and push a*b in stack if x is the operator /, pop two values b and a, and push a/b in stack```

My program is able to print correct results for the given sample inputs. However, when I submitted it to an online judge, it was judged as Incorrect. Here's the code:

 ``1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192`` ``````#include #include #include #include #include #include #include using namespace std; int main() { int N, i = 0; bool undefined; string dummy; cin >> N; getline(cin, dummy); long long a, b; string sequence; while (i < N) { stack s; getline(cin, sequence); stringstream sin(sequence); undefined = false; string tokens; while (sin >> tokens) { if (isdigit(tokens[0]) || isdigit(tokens[1])) { s.push(atoi(tokens.c_str())); } else { switch(tokens[0]) { case '+': b = s.top(); s.pop(); a = s.top(); s.pop(); s.push(a + b); break; case '-': b = s.top(); s.pop(); a = s.top(); s.pop(); s.push(a - b); break; case '*': b = s.top(); s.pop(); a = s.top(); s.push(a * b); break; case '/': b = s.top(); s.pop(); if (b == 0) undefined = true; else { a = s.top(); s.pop(); s.push(a / b); } break; } } } if (undefined) cout << "UNDEFINED" << endl; else { cout << s.top() << endl; s.pop(); } i++; } return 0; }``````

Here's the sample input
 ```5 4 5 + 3 2 / 4 3 - + 2 0 / 2000000 -2000000 * 2000000 1000000 43000 + *```

And here is the ouput
 ```5 4 5 + 3 2 / 4 3 - + 2 0 / 2000000 -2000000 * 2000000 1000000 43000 + *```

I really feel my algorithm is right. But what could be wrong in my code? Can anyone point the flaws and how I can fix it? Providing critical test input can also help. Thanks in advance!
I think it would be really educational to learn how to use the debugger. If you are using an IDE there should be a built in one that is easy to use. If not, then it is a bit trickier, but not impossible to use one from a command line. For example gdb, can be used from the cmd line, or incorporated into an IDE.

You can set breakpoints, have a watchlist of variable values, and step through the code 1 line at a time.

The whole process can be quicker and less boring than what one might expect initially.

Hope all goes well.

Edit:

Here is a link to K&R C Programming - it has a RPN program.

Last edited on
stupid question but on line 21 you have
`long long a, b;`

would this not work?
`long a, b;`

`long long` is a type in C++.

You can also have `unsigned long long`

Sometimes, it is not necessary - on my system a long is 64bits.

I tend to use the stdint.h header, it has types like `uint64_t` which is an unsigned 64 bit quantity. It has others like `int8_t` which is a signed 8 bit - I find this less confusing than using a `char` as a small `int`.
Last edited on
Topic archived. No new replies allowed.