# How to Program a Reverse Polish Notation (RPN) Calculator in C

We are going through the steps of developing a stack-based RPN calculator in C.

First the program needs to read the input from the terminal, one line at a time:

```#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
while (true) {
assert(c != NULL);
free(c);
}
}```

You might need to first install the `readline` library for development. This library is maintained by the GNU project and provides -- among other things -- a nicer handling of the keyboard arrow keys.

On Debian Linux, the development library is available as the `libreadline-dev` package.

`sudo apt install libreadline-dev`

Filly, when compiling, we must link the `readline` library by passing a command-line argument.

`gcc -o rpn1 rpn1.c -lreadline`

## Parsing Positive Integer Numbers

A simple function to parse a string of ASCII digits into an integer number is shown below.

```int parse_int(char* s) {
int acc = 0;
char* p = s;
while (*p != '\0' && *p != '\r' && *p != '\n') {
assert((*p) >= '0' && (*p) <= '9');
acc *= 10;
acc += (*p) - '0';
p++;
}
return acc;
}```

Note that it has two main flaws or limitations:

• First, it does not handle integer overflows. If the provided sequence of digits represents a number greater than what the `int` data type can store, it will overflow and produce the wrong result.
• Second, it does not handle negative numbers, represented by a leading hyphen or minus sign.

We can adapt `main` so that we can test that the function works correctly for a few numbers:

```int main() {
while (true) {
assert(c != NULL);
int n = parse_int(c);
free(c);
}
}```

Although the output is exactly the same as the step before, there's a very critical distinction: Now the number is being held as an integer in the `n` variable, instead of a sequence of ASCII digits in the `c` variable.

## The Stack Data Structure

The stack is central to how a RPN calculator works.

By inputting numbers, we push those numbers into the stack.

By inputting operators, we pop numbers from the stack and push back the result.

For example:

```stack: [ ]
> 123
stack: [ 123 ]
> 456
stack: [ 123 456 ]
> +
stack: [ 579 ]```

Let's setup some storage for the stack, implement the push and pop operations and a printing routine.

```#define STACK_SIZE 128
int stack[STACK_SIZE];
int stack_i = 0;

void stack_push(int n) {
assert(stack_i < STACK_SIZE);
stack[stack_i] = n;
stack_i++;
}

int stack_pop() {
assert(stack_i > 0);
stack_i--;
return stack[stack_i];
}

int stack_print() {
printf("stack: [");
for (int i = 0; i < stack_i; i++) {
printf(" %d", stack[i]);
}
printf(" ]\n");
}
```

Finally, let's adjust `main` to push every new number typed in into the stack.

```int main() {
while (true) {
stack_print();
assert(c != NULL);
int n = parse_int(c);
stack_push(n);
free(c);
}
}```

## Performing Arithmetic Operations

For this final step, let's make the calculator, well, calculate.

We start by define a few operations and matching strings to either one of the possible operations or to a sentinel “invalid” operation;

```#define OP_INVALID -1
#define OP_SUB 2
#define OP_MUL 3
#define OP_DIV 4
#define OP_REM 5

int parse_op(char* str) {
if (strcmp(str, "+") == 0) return OP_ADD;
if (strcmp(str, "-") == 0) return OP_SUB;
if (strcmp(str, "*") == 0) return OP_MUL;
if (strcmp(str, "/") == 0) return OP_DIV;
if (strcmp(str, "%") == 0) return OP_REM;
return OP_INVALID;
}```

Performing the operation itself requires manipulating the stack. We need to: 1) pop the operands in the correct order; 2) perform the operation; and 3) push back the result into the stack. The code goes as follows:

```void perform_op(int op) {
int right = stack_pop();
int left = stack_pop();
int result = 0;
switch (op) {
case OP_ADD: result = left + right; break;
case OP_SUB: result = left - right; break;
case OP_MUL: result = left * right; break;
case OP_DIV: result = left / right; break;
case OP_REM: result = left % right; break;
default: assert(!"Invalid op value");
}
stack_push(result);
}
```

Finally, we adjust the `main` function to first try to interpret the input as an operator.

If it doesn't match a supported operator, we assume it is an integer and push it into the stack.

```int main() {
while (true) {
stack_print();
assert(c != NULL);
int op = parse_op(c);
if (op == OP_INVALID) {
int n = parse_int(c);
stack_push(n);
} else {
perform_op(op);
}
free(c);
}
}```

## The Full Program

The source code is available below. The following improvements could be made and are left as an exercise to the reader:

• More gracefully handle invalid input (instead of just aborting the program by failing an assert).
• More gracefully handle integer overflows.
• Handle division by zero.
• Switch to floating point arithmetic so that the “/” division operator yields more expected results.
• Implement more operators and operations, such as `sqrt`, `sin`, `cos`.
• Implement variable assignment and variable value retrieval.
```// SPDX-License-Identifier: MIT
// 2023 Victor Breder

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int parse_int(char* s) {
int acc = 0;
char* p = s;
while (*p != '\0' && *p != '\r' && *p != '\n') {
assert((*p) >= '0' && (*p) <= '9');
acc *= 10;
acc += (*p) - '0';
p++;
}
return acc;
}

#define STACK_SIZE 128
int stack[STACK_SIZE];
int stack_i = 0;

void stack_push(int n) {
assert(stack_i < STACK_SIZE);
stack[stack_i] = n;
stack_i++;
}

int stack_pop() {
assert(stack_i > 0);
stack_i--;
return stack[stack_i];
}

int stack_print() {
printf("stack: [");
for (int i = 0; i < stack_i; i++) {
printf(" %d", stack[i]);
}
printf(" ]\n");
}

#define OP_INVALID -1
#define OP_SUB 2
#define OP_MUL 3
#define OP_DIV 4
#define OP_REM 5
int parse_op(char* str) {
if (strcmp(str, "+") == 0) return OP_ADD;
if (strcmp(str, "-") == 0) return OP_SUB;
if (strcmp(str, "*") == 0) return OP_MUL;
if (strcmp(str, "/") == 0) return OP_DIV;
if (strcmp(str, "%") == 0) return OP_REM;
return OP_INVALID;
}

void perform_op(int op) {
int right = stack_pop();
int left = stack_pop();
int result = 0;
switch (op) {
case OP_ADD: result = left + right; break;
case OP_SUB: result = left - right; break;
case OP_MUL: result = left * right; break;
case OP_DIV: result = left / right; break;
case OP_REM: result = left % right; break;
default: assert(!"Invalid op value");
}
stack_push(result);
}

int main() {
while (true) {
stack_print();
assert(c != NULL);
int op = parse_op(c);
if (op == OP_INVALID) {
int n = parse_int(c);
stack_push(n);
} else {
perform_op(op);
}
free(c);
}
}```

Compilation instructions:

```# sudo apt install libreadline-dev

Sample session when using the finished program:

```stack: [ ]
> 60
stack: [ 60 ]
> 30
stack: [ 60 30 ]
> +
stack: [ 90 ]
> 5
stack: [ 90 5 ]
> /
stack: [ 18 ]
>```