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.
Reading input
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>
#include <readline/readline.h>
int main() {
while (true) {
char* c = readline("> ");
assert(c != NULL);
printf("Your command: %s\n", c);
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
intdata 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) {
char* c = readline("> ");
assert(c != NULL);
int n = parse_int(c);
printf("Your number: %d\n", n);
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();
char* c = readline("> ");
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_ADD 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();
char* c = readline("> ");
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>
#include <readline/readline.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_ADD 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();
char* c = readline("> ");
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 gcc -o rpn rpn.c -lreadline
Sample session when using the finished program:
stack: [ ] > 60 stack: [ 60 ] > 30 stack: [ 60 30 ] > + stack: [ 90 ] > 5 stack: [ 90 5 ] > / stack: [ 18 ] >