Saturated Reverse Polish Notation (SRPN) calculator

If you’ve found this page it’s likely you’ve been set an assignment for you CS studies around SRPN.

This article gives a brief overview of what SRPN is and how you may approach coding an SRPN yourself.

Hints are labelled as HINT. Spoilers as SPOILER. I’d recommend only reading the SPOILER section if you’re really stuck.

What is SRPN

Let’s start at the end.

Polish Notation is where you write the operators (namely, +, /, — , *,^ and %) before the operands (operands are numbers like 42, 101, -2 etc).

We’re used to seeing in-fix notation in real life. 2 plus 3 equals 5.

2 + 3

However, with Polish notation, you write the operator first then the operands. plus the next two operands, 2,3, which equals 5

+ 2 3

Reverse Polish Notation is where you write the operators after the operands.

2 3 +

Again we look for the operator, the plus, to the left of the plus is 3 then 2. 3 + 2 = 5.

Saturated Reverse Polish Notation

Saturated means that once a calculation reaches a specified value you stop and do not wrap around.

for example. The limit of signed type in C is MAX 2,147,483,647 and MIN -2,147,483,648.

If I performed the following calculation in SPRN

2147483645 10 +

The answer would be 2,147,483,647. We have hit the maximum int limit. If we do not impose this saturation criterion the calculation will wrap around and produce a large negative value.

Summary

• Polish Notation: Write the operators ( +, /, — , *,^ and %) and before the operands
• Reverse: Write the operators after the operands
• Saturated: Whichever limit is specified, do not wrap around

HINT : What data type is best to solve this problem

If we take a slightly longer example

2 3 4 + *

How do we evaluate this?

• Look for the first operator from left to right. That’s the “+”
• to perform the “+” operation we need two operands, the 2 operands directly to the left of the operator.
• take the 4, and then add 3 to it. = 7
• now the equation is

2 7 *

• again find the next operator, the multiply “*”
• take the 2 operands to the left of it
• take the 7 multiple it by 2 to equal 14

Taking this step by step visually you can see that we are in effect using a Stack data type to pop numbers off the stack, operate on them, and push the result back onto the stack. Finally, we can peek at the answer 14

SPOILERS

I suggest if you’re doing this as an assignment you implement the above calculator and then start figuring out the edge cases for yourself. The below are SPOILERS in the sense they tell you the edge case, but I have not included any implementation.

1. How to handle an equation with no spaces. For example 23+
2. How to handle stack underflow. For example 23++, once the first operand is complete there is just 5 on the stack with nothing for the second “+” to operate on (remember operators need 2 operands).
3. How to handle negative numbers. What does 2–2 equal? how about -2–2?
4. How would you handle a user entering in a really big/small number to start.
5. How do you handle MIN and MAX saturation?
6. How do you account for divide by zero and similar mathematical quirks?
7. How do you guard against non-integer inputs?
8. Is there are limit to how many numbers can be held on the stack?

Finally — here is an excellent Computerphile video which explains a lot of the above and more!

https://www.youtube.com/watch?v=7ha78yWRDlE