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 an 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 ] >