Why this matters
A calculator that reads 3 4 + instead of 3 + 4 looks odd, but reverse Polish notation (RPN) is everywhere underneath: the Java and Python virtual machines, WebAssembly and PostScript are stack machines that execute exactly this kind of postfix code, and compilers translate your infix expressions into it. Hewlett-Packard calculators and the Unix dc tool use it directly. It needs no parentheses and no precedence rules, so an evaluator is small enough to build in an afternoon, yet it exercises tokenizing, number parsing, a stack, careful error handling, and finally function pointers.
How RPN works
Operators come after their operands. Evaluate left to right with a stack:
- a number: push it;
- an operator: pop its operands, compute, push the result.
At the end, exactly one value should remain: the answer.
input: 5 1 2 + 4 * + 3 - (infix: 5 + (1 + 2) * 4 - 3)
token stack after
5 5
1 5 1
2 5 1 2
+ 5 3 pops 2 and 1, pushes 1 + 2
4 5 3 4
* 5 12 pops 4 and 3, pushes 3 * 4
+ 17
3 17 3
- 14 pops 3 and 17, pushes 17 - 3
The order of popping matters. The top of the stack is the right operand: for 10 4 -, pop 4 into b, pop 10 into a, compute a - b.
What we are building
$ printf '3 4 +\n7 2 /\n1 0 /\n2 sqrt\n' | ./rpn
7
3.5
error: division by zero
1.41421
$ echo $?
1
One expression per line, results on stdout, errors on stderr, and an exit status that tells a script whether everything succeeded. Errors do not stop the program: a bad line is reported and the next one is evaluated, which is what you want from a tool processing a file of expressions.
Step 1: the stack
A fixed-size array plus a count is all a stack needs:
stack: [ 5 ][ 3 ][ 4 ][ ][ ] ... depth = 3
0 1 2 3
^top ^next free slot
depth is both the number of items and the index of the next free slot, so stack[depth++] = v pushes and stack[--depth] pops. Both functions report failure (full or empty) through their return value instead of crashing or silently corrupting memory, and pop delivers the value through an out-parameter. This is the C convention you have seen all along: the return value says whether it worked; pointers carry the results.
Step 2: tokens, numbers and errors
Tokenizing. strtok(line, " \t\n") returns the first token and writes a '\0' after it in line; later calls with NULL continue where it left off. It modifies the buffer and keeps hidden state, so it cannot be used on string literals or on two strings at once (strtok_r fixes the latter), but for splitting one line it is just right. The tokens are pointers into line, valid until the next fgets overwrites it.
Numbers. strtod parses a double and reports, through its end pointer, where it stopped. A token is a valid number only if strtod consumed something (end != tok) and everything (*end == '\0'): that rejects abc, 3x and 1.2.3, while accepting -2.5, 1e3 and 0x10.
Operators versus negative numbers. - is an operator; -3 is a number. Checking "exactly one character, and it is one of +-*/" before trying strtod keeps them apart.
Errors as values. eval_token returns NULL on success or a pointer to a constant message. String literals live for the whole program, so returning them is safe, and the caller decides how to report. Keeping detection (deep in the evaluator) separate from reporting (in main) is what lets one function print the error to stderr, record the failure for the exit status, and move on.
The full error policy:
| situation | message |
|---|
| operator with too few operands | error: stack underflow |
| more than 64 values | error: stack overflow |
x 0 / | error: division by zero |
| not a number or operator | error: unknown token 'abc' |
| several values left at the end | error: too many values |
Division by zero is checked explicitly. For double, dividing by zero is actually defined in IEEE 754 (it gives inf or nan), but for a calculator an error message is friendlier than printing inf.
Step 3: a dispatch table
With four operators, a switch is fine. With twenty it becomes a wall of nearly identical cases. The standard C answer is a dispatch table: data that maps names to functions.
typedef const char *(*op_fn)(void); /* pointer to a function taking nothing,
returning an error message or NULL */
static const struct {
const char *name;
op_fn fn;
} ops[] = {
{"+", op_add}, {"-", op_sub}, {"*", op_mul}, {"/", op_div},
{"neg", op_neg}, {"sqrt", op_sqrt}, /* ... */
};
for (size_t i = 0; i < sizeof ops / sizeof ops[0]; i++)
if (strcmp(tok, ops[i].name) == 0)
return ops[i].fn(); /* call through the pointer */
Adding an operation is now one function and one table row; the lookup never changes. This is how command interpreters, virtual machines and protocol handlers are commonly organized in C, and it is the same idea as qsort's comparator: code chosen at run time through a function pointer. The typedef makes the pointer type readable; without it the struct member would be const char *(*fn)(void).
Each operation checks its own preconditions (enough operands, valid domain) before touching the stack. Note op_sqrt pops before checking the domain: on error the line is abandoned anyway, so the stack state no longer matters.
Common mistakes
- Popping in the wrong order, computing
b - a. Test with 10 4 - and 8 2 /, never only with + and *. - Treating
-3 as an operator or - as a number. Decide on the operator test first. - Accepting partial numbers by ignoring
strtod's end pointer, so 3x silently becomes 3. - Returning a pointer to a local array as the error message. Literals are fine; a local
char msg[64] dies when the function returns. - Forgetting to reset the stack between lines, so leftovers from a failed line pollute the next one.
- Printing errors to stdout. Then
./rpn < exprs.txt > results.txt mixes errors into the results.
Recap
- RPN evaluates with a stack: push numbers, pop operands for operators, one value remains.
- The top of the stack is the right-hand operand.
strtok splits a line in place; strtod with an end pointer validates numbers.- Return error messages as values; report them in one place, on stderr, and reflect failure in the exit status.
- A dispatch table of
{name, function pointer} turns a growing switch into data.
Going further: add variables (x = stores the top of the stack in x, x alone pushes it), or write the reverse direction, a converter from infix to RPN using Dijkstra's shunting-yard algorithm, which needs a second stack for operators. Try dc in the sandbox terminal: echo '5 1 2 + 4 * + 3 - p' | dc.
Exercise 2 · write code
Step 1: the stack
Implement a fixed-size stack of doubles with these functions:
int push(double v); /* 0 on success, -1 if the stack is full (STACK_MAX items) */
int pop(double *out); /* 0 and the top value in *out, or -1 if empty (leave *out alone) */
int size(void); /* number of items on the stack */
void clear(void); /* remove everything */
The stack is the array stack plus the count depth, already declared. main is a demo that prints:
size 3
pop 3
pop 2
size 1
empty: -1
File: main.c
Starting point
#include <stdio.h>
#define STACK_MAX 64
static double stack[STACK_MAX];
static int depth;
int push(double v)
{
return -1;
}
int pop(double *out)
{
return -1;
}
int size(void)
{
return 0;
}
void clear(void)
{
}
int main(void)
{
double v;
push(1);
push(2);
push(3);
printf("size %d\n", size());
pop(&v);
printf("pop %g\n", v);
pop(&v);
printf("pop %g\n", v);
printf("size %d\n", size());
clear();
printf("empty: %d\n", pop(&v));
return 0;
}
Example
expected output
size 3
pop 3
pop 2
size 1
empty: -1
Hint 1
depth is both the number of items and the index of the next free slot.
Hint 2
push: check for full, then stack[depth++] = v;. pop: check for empty, then *out = stack[--depth];.
Reference solution
#include <stdio.h>
#define STACK_MAX 64
static double stack[STACK_MAX];
static int depth;
int push(double v)
{
if (depth == STACK_MAX)
return -1;
stack[depth++] = v;
return 0;
}
int pop(double *out)
{
if (depth == 0)
return -1;
*out = stack[--depth];
return 0;
}
int size(void)
{
return depth;
}
void clear(void)
{
depth = 0;
}
int main(void)
{
double v;
push(1);
push(2);
push(3);
printf("size %d\n", size());
pop(&v);
printf("pop %g\n", v);
pop(&v);
printf("pop %g\n", v);
printf("size %d\n", size());
clear();
printf("empty: %d\n", pop(&v));
return 0;
}
Exercise 3 · write code
Step 2: evaluate expressions
Write the evaluator. Each input line is one RPN expression with tokens separated by spaces or tabs. A token is either one of the operators + - * / or a number (anything strtod accepts completely, such as 3, -2.5 or 1e3).
For each line, start with an empty stack, process the tokens, and then:
- if exactly one value is left, print it with
printf("%g\n", value); - on an error, print one message to stderr and go on with the next line:
error: stack underflow (an operator needs two values and there are fewer),error: division by zero,error: unknown token 'TOKEN' (with the offending token),error: stack overflow (more than 64 values),error: too many values (more than one value left at the end of the line);
- skip blank lines silently.
Exit with status 0 if every line succeeded and 1 if any line had an error. The check also compares your stderr messages.
$ printf '3 4 +
7 2 /
1 0 /
' | ./prog
7
3.5
error: division by zero
File: main.c
Starting point
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define STACK_MAX 64
static double stack[STACK_MAX];
static int depth;
static int push(double v)
{
if (depth == STACK_MAX)
return -1;
stack[depth++] = v;
return 0;
}
static int pop(double *out)
{
if (depth == 0)
return -1;
*out = stack[--depth];
return 0;
}
/* Evaluate one token. Return NULL on success, or an error message such as
"stack underflow". */
static const char *eval_token(const char *tok)
{
(void)tok;
return "unknown token";
}
int main(void)
{
char line[1024];
int failed = 0;
while (fgets(line, sizeof line, stdin) != NULL) {
depth = 0;
/* split line into tokens with strtok(line, " \t\n") and strtok(NULL, " \t\n"),
call eval_token on each, stop at the first error, then print
the result or the error */
}
return failed;
}
Example
input
3 4 +
5 1 2 + 4 * + 3 -
10 4 -
7 2 /
-3 -4 *
1e3 8 /
expected output
7
14
6
3.5
12
125
Example
input
2 2 +
expected output
4
Hint 1
A token is an operator if it is exactly one character long and that character is in "+-*/". Note that "-3" is a number, not an operator.
Hint 2
Pop the right operand first: pop(&b); pop(&a); then compute a - b or a / b.
Hint 3
strtod(tok, &end) parsed the whole token only if end != tok and *end == '\0'.
Hint 4
Remember which token failed so the unknown-token message can include it; strtok returns pointers into your line buffer, which stays valid until the next fgets.
Reference solution
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define STACK_MAX 64
static double stack[STACK_MAX];
static int depth;
static int push(double v)
{
if (depth == STACK_MAX)
return -1;
stack[depth++] = v;
return 0;
}
static int pop(double *out)
{
if (depth == 0)
return -1;
*out = stack[--depth];
return 0;
}
/* Evaluate one token. Return NULL on success, or an error message such as
"stack underflow". */
static const char *eval_token(const char *tok)
{
if (strlen(tok) == 1 && strchr("+-*/", tok[0]) != NULL) {
double a, b;
if (depth < 2)
return "stack underflow";
pop(&b); /* the right operand is on top */
pop(&a);
switch (tok[0]) {
case '+': return push(a + b) ? "stack overflow" : NULL;
case '-': return push(a - b) ? "stack overflow" : NULL;
case '*': return push(a * b) ? "stack overflow" : NULL;
default:
if (b == 0.0)
return "division by zero";
return push(a / b) ? "stack overflow" : NULL;
}
}
char *end;
double v = strtod(tok, &end);
if (end == tok || *end != '\0')
return "unknown token";
if (push(v) != 0)
return "stack overflow";
return NULL;
}
int main(void)
{
char line[1024];
int failed = 0;
while (fgets(line, sizeof line, stdin) != NULL) {
depth = 0;
const char *err = NULL;
const char *bad = NULL;
int tokens = 0;
for (char *tok = strtok(line, " \t\n"); tok != NULL; tok = strtok(NULL, " \t\n")) {
tokens++;
err = eval_token(tok);
if (err != NULL) {
bad = tok;
break;
}
}
if (tokens == 0)
continue; /* blank line */
if (err == NULL && depth != 1)
err = "too many values";
if (err == NULL) {
printf("%g\n", stack[0]);
continue;
}
if (strcmp(err, "unknown token") == 0)
fprintf(stderr, "error: unknown token '%s'\n", bad);
else
fprintf(stderr, "error: %s\n", err);
failed = 1;
}
return failed;
}
Exercise 4 · write code
Step 3: a dispatch table and more operations
A growing if/switch chain gets unwieldy. Refactor the operators into a dispatch table: an array of { name, function pointer } pairs, searched by name. Each operation is a function const char *op_xxx(void) that checks the stack depth, pops what it needs, pushes the result, and returns NULL or an error message.
Support these operations (the starter has the first four as functions and an empty table):
| name | effect | errors |
|---|
+ - * / | as before | stack underflow, division by zero |
^ | a b: push pow(a, b) | stack underflow |
neg | a: push -a | stack underflow |
sqrt | a: push sqrt(a) | stack underflow, domain error if a < 0 |
dup | a: push a twice | stack underflow, stack overflow |
swap | a b: push b then a | stack underflow |
Everything else (numbers, errors on stderr, too many values, exit status) is unchanged.
$ printf '2 3 ^ neg
2 sqrt
3 dup *
1 2 swap -
' | ./prog
-8
1.41421
9
1
File: main.c
Starting point
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define STACK_MAX 64
static double stack[STACK_MAX];
static int depth;
static int push(double v)
{
if (depth == STACK_MAX)
return -1;
stack[depth++] = v;
return 0;
}
static int pop(double *out)
{
if (depth == 0)
return -1;
*out = stack[--depth];
return 0;
}
/* An operation pops what it needs, pushes its result, and returns NULL
or an error message. */
typedef const char *(*op_fn)(void);
static const char *op_add(void)
{
double a, b;
if (depth < 2)
return "stack underflow";
pop(&b);
pop(&a);
push(a + b);
return NULL;
}
static const char *op_sub(void)
{
double a, b;
if (depth < 2)
return "stack underflow";
pop(&b);
pop(&a);
push(a - b);
return NULL;
}
static const char *op_mul(void)
{
double a, b;
if (depth < 2)
return "stack underflow";
pop(&b);
pop(&a);
push(a * b);
return NULL;
}
static const char *op_div(void)
{
double a, b;
if (depth < 2)
return "stack underflow";
pop(&b);
pop(&a);
if (b == 0.0)
return "division by zero";
push(a / b);
return NULL;
}
/* TODO: op_pow, op_neg, op_sqrt, op_dup, op_swap */
static const struct {
const char *name;
op_fn fn;
} ops[] = {
{"+", op_add},
/* TODO: the rest */
};
static const char *eval_token(const char *tok)
{
/* TODO: look tok up in ops[] and call its function */
char *end;
double v = strtod(tok, &end);
if (end == tok || *end != '\0')
return "unknown token";
if (push(v) != 0)
return "stack overflow";
return NULL;
}
int main(void)
{
char line[1024];
int failed = 0;
while (fgets(line, sizeof line, stdin) != NULL) {
depth = 0;
const char *err = NULL;
const char *bad = NULL;
int tokens = 0;
for (char *tok = strtok(line, " \t\n"); tok != NULL; tok = strtok(NULL, " \t\n")) {
tokens++;
err = eval_token(tok);
if (err != NULL) {
bad = tok;
break;
}
}
if (tokens == 0)
continue;
if (err == NULL && depth != 1)
err = "too many values";
if (err == NULL) {
printf("%g\n", stack[0]);
continue;
}
if (strcmp(err, "unknown token") == 0)
fprintf(stderr, "error: unknown token '%s'\n", bad);
else
fprintf(stderr, "error: %s\n", err);
failed = 1;
}
return failed;
}
Example
input
2 3 ^ neg
2 sqrt
3 dup *
1 2 swap -
expected output
-8
1.41421
9
1
Example
input
5 1 2 + 4 * + 3 -
7 2 /
expected output
14
3.5
Hint 1
Loop over the table: for (size_t i = 0; i < sizeof ops / sizeof ops[0]; i++) if (strcmp(tok, ops[i].name) == 0) return ops[i].fn();
Hint 2
Check the table before trying strtod, so that names like "neg" are found. (strtod would reject them anyway, but "-" must not be mistaken for a number either.)
Hint 3
dup: check depth >= 1, then push(stack[depth - 1]), reporting overflow if push fails.
Hint 4
pow and sqrt come from <math.h>; the build already links -lm.
Reference solution
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define STACK_MAX 64
static double stack[STACK_MAX];
static int depth;
static int push(double v)
{
if (depth == STACK_MAX)
return -1;
stack[depth++] = v;
return 0;
}
static int pop(double *out)
{
if (depth == 0)
return -1;
*out = stack[--depth];
return 0;
}
/* An operation pops what it needs, pushes its result, and returns NULL
or an error message. */
typedef const char *(*op_fn)(void);
static const char *op_add(void)
{
double a, b;
if (depth < 2)
return "stack underflow";
pop(&b);
pop(&a);
push(a + b);
return NULL;
}
static const char *op_sub(void)
{
double a, b;
if (depth < 2)
return "stack underflow";
pop(&b);
pop(&a);
push(a - b);
return NULL;
}
static const char *op_mul(void)
{
double a, b;
if (depth < 2)
return "stack underflow";
pop(&b);
pop(&a);
push(a * b);
return NULL;
}
static const char *op_div(void)
{
double a, b;
if (depth < 2)
return "stack underflow";
pop(&b);
pop(&a);
if (b == 0.0)
return "division by zero";
push(a / b);
return NULL;
}
static const char *op_pow(void)
{
double a, b;
if (depth < 2)
return "stack underflow";
pop(&b);
pop(&a);
push(pow(a, b));
return NULL;
}
static const char *op_neg(void)
{
double a;
if (depth < 1)
return "stack underflow";
pop(&a);
push(-a);
return NULL;
}
static const char *op_sqrt(void)
{
double a;
if (depth < 1)
return "stack underflow";
pop(&a);
if (a < 0)
return "domain error";
push(sqrt(a));
return NULL;
}
static const char *op_dup(void)
{
if (depth < 1)
return "stack underflow";
if (push(stack[depth - 1]) != 0)
return "stack overflow";
return NULL;
}
static const char *op_swap(void)
{
double a, b;
if (depth < 2)
return "stack underflow";
pop(&b);
pop(&a);
push(b);
push(a);
return NULL;
}
static const struct {
const char *name;
op_fn fn;
} ops[] = {
{"+", op_add}, {"-", op_sub}, {"*", op_mul}, {"/", op_div}, {"^", op_pow},
{"neg", op_neg}, {"sqrt", op_sqrt}, {"dup", op_dup}, {"swap", op_swap},
};
static const char *eval_token(const char *tok)
{
for (size_t i = 0; i < sizeof ops / sizeof ops[0]; i++)
if (strcmp(tok, ops[i].name) == 0)
return ops[i].fn();
char *end;
double v = strtod(tok, &end);
if (end == tok || *end != '\0')
return "unknown token";
if (push(v) != 0)
return "stack overflow";
return NULL;
}
int main(void)
{
char line[1024];
int failed = 0;
while (fgets(line, sizeof line, stdin) != NULL) {
depth = 0;
const char *err = NULL;
const char *bad = NULL;
int tokens = 0;
for (char *tok = strtok(line, " \t\n"); tok != NULL; tok = strtok(NULL, " \t\n")) {
tokens++;
err = eval_token(tok);
if (err != NULL) {
bad = tok;
break;
}
}
if (tokens == 0)
continue;
if (err == NULL && depth != 1)
err = "too many values";
if (err == NULL) {
printf("%g\n", stack[0]);
continue;
}
if (strcmp(err, "unknown token") == 0)
fprintf(stderr, "error: unknown token '%s'\n", bad);
else
fprintf(stderr, "error: %s\n", err);
failed = 1;
}
return failed;
}