# Reverse Polish Notation in C (using a Finite State Machine)

I recently learned about Finite State Machines (FSM) and thought I'd use that to implement a Reverse Polish Notation (RPN) calculator.

I wanted it to also work nicely with the unix pipe. For example, if we have an input file with a set of RPN expressions, I can do something like:

\$ cat file.txt | rpn

Where rpn is the name of my executable.

For those who don't know, RPN is a type of postfix notation that helps with disambiguating order of operations in a mathematical expression, for example:

5 4 + == 5 + 4 == 9

4 1 - 3 2 + * == (4 - 1) * (3 + 2) == 15

Here's the implementation:

#include <stdio.h>
#include <ctype.h>

#define MAXLEN 1000

typedef int(*opfunc)(int, int);

typedef enum
{
START,
NUMBER,
SPACE,
MINUS,
NEWLINE, // used to flush a calculation
OPERATOR,
ERROR
} State;

int add(int a, int b) { return a + b; }
int mul(int a, int b) { return a * b; }
int div(int a, int b) { return a / b; }

opfunc getop(char c)
{
switch (c) {
case '+':
case '*':
return mul;
case '/':
return div;
default:
return NULL;
}
}

int main()
{
State state = START;
int c, number, stack[MAXLEN], sign = 1, stackpos = 0;
char message[MAXLEN];
opfunc op = NULL;
while (state != ERROR && ((c = getchar()) != EOF)) {
if (state == START) {
if (isdigit(c)) {
number = c - '0';
state = NUMBER;
} else if (c == '\n') {
continue;
} else if (isspace(c)) {
state = SPACE;
} else if (c == '-') {
state = MINUS;
} else {
state = ERROR;
strcpy(message, "Invalid character at start of line");
}
} else if (state == NUMBER) {
if (isdigit(c)) {
number = (number * 10) + (c - '0');
} else if (c == '\n') {
stack[stackpos++] = sign * number;
sign = 1;
state = NEWLINE;
} else if (isspace(c)) {
stack[stackpos++] = sign * number;
sign = 1;
state = SPACE;
} else {
state = ERROR;
strcpy(message, "Invalid character at the end of number");
}
} else if (state == MINUS) {
if (isdigit(c)) {
number = c - '0';
sign = -1;
state = NUMBER;
continue;
}
if (stackpos < 2) {
state = ERROR;
strcpy(message, "More operands required");
} else if (isspace(c)) {
int right = stack[--stackpos];
int left = stack[--stackpos];
stack[stackpos++] = left - right;
state = c == '\n' ? NEWLINE : SPACE;
} else {
state = ERROR;
strcpy(message, "Invalid character after '-'");
}
} else if (state == SPACE) {
if (isdigit(c)) {
number = c - '0';
state = NUMBER;
} else if (c == '\n') {
state = NEWLINE;
} else if (c == '-') {
state = MINUS;
} else if (!isspace(c)) {
op = getop(c);
if (op == NULL) {
state = ERROR;
strcpy(message, "Expected one of +/*");
} else {
if (stackpos < 2) {
state = ERROR;
strcpy(message, "More operands required");
continue;
}
int right = stack[--stackpos];
int left = stack[--stackpos];
if (right == 0 && c == '/') {
state = ERROR;
strcpy(message, "Division by zero");
} else {
stack[stackpos++] = op(left, right);
state = OPERATOR;
}
}
}
} else if (state == OPERATOR) {
if (c == '\n') {
state = NEWLINE;
} else if (isspace(c)) {
state = SPACE;
} else {
strcpy(message, "Expected space or newline after operator");
state = ERROR;
}
}
if (state == NEWLINE) {
if (stackpos > 1) {
state = ERROR;
strcpy(message, "Too many operands");
} else {
if (stackpos == 1) {
printf("result: %d\n", stack[0]);
stackpos = 0;
}
state = START;
}
}
}
if (state == ERROR) {
printf("%s\n", message);
} else if (stackpos > 1) {
printf("Too many operands\n");
} else if (stackpos == 1) {
printf("result: %d\n", stack[0]);
}
return 0;
}

• Obviously you'd use < to take input from a file, rather than pulling out cat for that! Aug 1 at 8:37

## Make sure you have all required #includes

The code uses strcpy but doesn't #include <string.h>.

## Use a switch instead of long if ...else chain

The parser logic is much easier to see if a switch statement is used instead of the long if...else chain.

## Consider overflow errors

If I enter 12345678901234567890, on my machine the program reports:

result: -350287150

Some detection and warning of this overflow would be helpful to the user. One way to do this is to make sure that, when multiplying by the next digit, that the new number calculated is not less than the old one.

## Consider handling unary +

The code handles unary - but, in an odd asymmetry, does not handle unary +. I realize that unsigned numbers are treated as positive (which is certainly the expected and correct behavior) but it sometimes helps when adding a long list of numbers, say, "debits and credits" to be able to indicate which is which with an explicit sign.

• Thanks! Could you elaborate on the switch case usage? Aside from checking the state variable, how can it help avoid the chain? Some of the conditions are not checks against constant expressions, for example. Aug 1 at 21:24
• Only the outermost if would be replaced with case statements. The others would remain within each case for the reasons you mention. Aug 1 at 22:15

Enable all warnings

Good compilers will aid in quicker, good code development

• warning: implicit declaration of function 'strcpy' [-Wimplicit-function-declaration]
• warning: incompatible implicit declaration of built-in function 'strcpy'
• warning: conversion from 'int' to 'char' may change value [-Wconversion]
• error: conflicting types for 'div'

Detecting overflow

add(), mul(), div() could all test arguments and report overflow rather than the undefined behavior of current code. Sample code

Extract from main()

Make this nifty parser a stand-alone set of routines and call from main() with a string.