Capstone: a calculator evaluator
The parser of lesson 78 ends with a tree. Evaluating it is a second recursive walk: a number returns its value, an operator evaluates both children and applies the arithmetic. The order of the walk is the order of the parentheses in the source.
Evaluating the tree
The evaluator is one function with a switch on the node kind. The children are evaluated before the operator, so the result of 2*3 is available when the addition above it runs. The whole parser from the previous lesson is here with the evaluator added, so the program is complete.
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
typedef enum { NUMBER, PLUS, MINUS, STAR, SLASH, LPAREN, RPAREN, END } Kind;
struct Node {
Kind kind;
int value;
struct Node *left;
struct Node *right;
};
static const char *cursor;
static Kind token;
static int number_value;
static void next_token(void)
{
while (isspace((unsigned char) *cursor)) {
cursor++;
}
if (isdigit((unsigned char) *cursor)) {
number_value = 0;
while (isdigit((unsigned char) *cursor)) {
number_value = number_value * 10 + (*cursor - '0');
cursor++;
}
token = NUMBER;
return;
}
switch (*cursor) {
case '+': token = PLUS; break;
case '-': token = MINUS; break;
case '*': token = STAR; break;
case '/': token = SLASH; break;
case '(': token = LPAREN; break;
case ')': token = RPAREN; break;
default: token = END; break;
}
if (token != END) {
cursor++;
}
}
static struct Node *make(Kind kind, int value, struct Node *left, struct Node *right)
{
struct Node *node = malloc(sizeof *node);
if (node == NULL) {
exit(1);
}
node->kind = kind;
node->value = value;
node->left = left;
node->right = right;
return node;
}
static struct Node *expression(void);
static struct Node *factor(void)
{
if (token == NUMBER) {
int value = number_value;
next_token();
return make(NUMBER, value, NULL, NULL);
}
if (token == LPAREN) {
next_token();
struct Node *inner = expression();
next_token();
return inner;
}
return NULL;
}
static struct Node *term(void)
{
struct Node *node = factor();
while (token == STAR || token == SLASH) {
Kind op = token;
next_token();
node = make(op, 0, node, factor());
}
return node;
}
static struct Node *expression(void)
{
struct Node *node = term();
while (token == PLUS || token == MINUS) {
Kind op = token;
next_token();
node = make(op, 0, node, term());
}
return node;
}
static int evaluate(const struct Node *node)
{
if (node->kind == NUMBER) {
return node->value;
}
int left = evaluate(node->left);
int right = evaluate(node->right);
switch (node->kind) {
case PLUS: return left + right;
case MINUS: return left - right;
case STAR: return left * right;
case SLASH: return left / right;
default: return 0;
}
}
static void free_tree(struct Node *node)
{
if (node == NULL) {
return;
}
free_tree(node->left);
free_tree(node->right);
free(node);
}
int main(void)
{
cursor = "1+2*3";
next_token();
struct Node *tree = expression();
printf("value: %d\n", evaluate(tree));
free_tree(tree);
return 0;
}
gcc -Wall -Wextra eval.c -o eval
./eval
value: 7
The multiplication is evaluated first because it is lower in the tree, and the addition combines 1 with 6. The same source with a different string computes a different expression; the evaluator does not know the text, only the shape. That separation is why a parser and an evaluator are separate functions even in a program this small.
Variables
A variable is a name the evaluator looks up instead of a number. The lexer gains an identifier token, the tree gains a node that stores the name, and the evaluator asks a small symbol table for the value. The table here is an array of two entries; a hash table from lesson 52 would scale it.
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef enum { NUMBER, IDENT, PLUS, MINUS, STAR, SLASH, LPAREN, RPAREN, END } Kind;
struct Node {
Kind kind;
int value;
char name[16];
struct Node *left;
struct Node *right;
};
struct Symbol {
const char *name;
int value;
};
static const char *cursor;
static Kind token;
static int number_value;
static char name_value[16];
static struct Symbol symbols[2] = {{"x", 3}, {"y", 4}};
static int lookup(const char *name)
{
for (int i = 0; i < 2; i++) {
if (strcmp(symbols[i].name, name) == 0) {
return symbols[i].value;
}
}
return 0;
}
static void next_token(void)
{
while (isspace((unsigned char) *cursor)) {
cursor++;
}
if (isdigit((unsigned char) *cursor)) {
number_value = 0;
while (isdigit((unsigned char) *cursor)) {
number_value = number_value * 10 + (*cursor - '0');
cursor++;
}
token = NUMBER;
return;
}
if (isalpha((unsigned char) *cursor)) {
int length = 0;
while (isalpha((unsigned char) *cursor) && length < 15) {
name_value[length++] = *cursor++;
}
name_value[length] = '\0';
token = IDENT;
return;
}
switch (*cursor) {
case '+': token = PLUS; break;
case '-': token = MINUS; break;
case '*': token = STAR; break;
case '/': token = SLASH; break;
case '(': token = LPAREN; break;
case ')': token = RPAREN; break;
default: token = END; break;
}
if (token != END) {
cursor++;
}
}
static struct Node *make(Kind kind, int value, const char *name, struct Node *left, struct Node *right)
{
struct Node *node = malloc(sizeof *node);
if (node == NULL) {
exit(1);
}
node->kind = kind;
node->value = value;
node->left = left;
node->right = right;
if (name != NULL) {
snprintf(node->name, sizeof node->name, "%s", name);
} else {
node->name[0] = '\0';
}
return node;
}
static struct Node *expression(void);
static struct Node *factor(void)
{
if (token == NUMBER) {
int value = number_value;
next_token();
return make(NUMBER, value, NULL, NULL, NULL);
}
if (token == IDENT) {
struct Node *node = make(IDENT, 0, name_value, NULL, NULL);
next_token();
return node;
}
if (token == LPAREN) {
next_token();
struct Node *inner = expression();
next_token();
return inner;
}
return NULL;
}
static struct Node *term(void)
{
struct Node *node = factor();
while (token == STAR || token == SLASH) {
Kind op = token;
next_token();
node = make(op, 0, NULL, node, factor());
}
return node;
}
static struct Node *expression(void)
{
struct Node *node = term();
while (token == PLUS || token == MINUS) {
Kind op = token;
next_token();
node = make(op, 0, NULL, node, term());
}
return node;
}
static int evaluate(const struct Node *node)
{
if (node->kind == NUMBER) {
return node->value;
}
if (node->kind == IDENT) {
return lookup(node->name);
}
int left = evaluate(node->left);
int right = evaluate(node->right);
switch (node->kind) {
case PLUS: return left + right;
case MINUS: return left - right;
case STAR: return left * right;
case SLASH: return left / right;
default: return 0;
}
}
static void free_tree(struct Node *node)
{
if (node == NULL) {
return;
}
free_tree(node->left);
free_tree(node->right);
free(node);
}
int main(void)
{
cursor = "x+2*y";
next_token();
struct Node *tree = expression();
printf("value: %d\n", evaluate(tree));
free_tree(tree);
return 0;
}
gcc -Wall -Wextra vars.c -o vars
./vars
value: 11
With x equal to 3 and y equal to 4, the expression x+2*y is 3 + 8. The name is copied into the node because the lexer's buffer is reused for the next token; the same ownership rule as the word counter in lesson 76. An unknown name returns zero, which the parser could reject instead.
Division by zero
Integer division by zero is undefined and the processor raises a signal, so the evaluator checks the right operand before the division. The check turns a crash into a message and a status of 1, which a caller can handle. The expression 8/(3-3) reaches the check with a zero from a computed value, not a literal.
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
typedef enum { NUMBER, PLUS, MINUS, STAR, SLASH, LPAREN, RPAREN, END } Kind;
struct Node {
Kind kind;
int value;
struct Node *left;
struct Node *right;
};
static const char *cursor;
static Kind token;
static int number_value;
static void next_token(void)
{
while (isspace((unsigned char) *cursor)) {
cursor++;
}
if (isdigit((unsigned char) *cursor)) {
number_value = 0;
while (isdigit((unsigned char) *cursor)) {
number_value = number_value * 10 + (*cursor - '0');
cursor++;
}
token = NUMBER;
return;
}
switch (*cursor) {
case '+': token = PLUS; break;
case '-': token = MINUS; break;
case '*': token = STAR; break;
case '/': token = SLASH; break;
case '(': token = LPAREN; break;
case ')': token = RPAREN; break;
default: token = END; break;
}
if (token != END) {
cursor++;
}
}
static struct Node *make(Kind kind, int value, struct Node *left, struct Node *right)
{
struct Node *node = malloc(sizeof *node);
if (node == NULL) {
exit(1);
}
node->kind = kind;
node->value = value;
node->left = left;
node->right = right;
return node;
}
static struct Node *expression(void);
static struct Node *factor(void)
{
if (token == NUMBER) {
int value = number_value;
next_token();
return make(NUMBER, value, NULL, NULL);
}
if (token == LPAREN) {
next_token();
struct Node *inner = expression();
next_token();
return inner;
}
return NULL;
}
static struct Node *term(void)
{
struct Node *node = factor();
while (token == STAR || token == SLASH) {
Kind op = token;
next_token();
node = make(op, 0, node, factor());
}
return node;
}
static struct Node *expression(void)
{
struct Node *node = term();
while (token == PLUS || token == MINUS) {
Kind op = token;
next_token();
node = make(op, 0, node, term());
}
return node;
}
static int evaluate(const struct Node *node)
{
if (node->kind == NUMBER) {
return node->value;
}
int left = evaluate(node->left);
int right = evaluate(node->right);
if (node->kind == SLASH && right == 0) {
printf("error: division by zero\n");
exit(1);
}
switch (node->kind) {
case PLUS: return left + right;
case MINUS: return left - right;
case STAR: return left * right;
case SLASH: return left / right;
default: return 0;
}
}
static void free_tree(struct Node *node)
{
if (node == NULL) {
return;
}
free_tree(node->left);
free_tree(node->right);
free(node);
}
int main(void)
{
cursor = "8/(3-3)";
next_token();
struct Node *tree = expression();
printf("value: %d\n", evaluate(tree));
free_tree(tree);
return 0;
}
gcc -Wall -Wextra zero.c -o zero
./zero; echo "status: $?"
error: division by zero
status: 1
The message goes to standard output here for simplicity; a real calculator sends it to standard error and leaves the result undefined. The check is in the evaluator, not the parser, because only the evaluator knows the value of the divisor.
The unchecked division
Without the check, the same operation ends the process. The C standard leaves integer division by zero undefined, and on x86_64 the processor raises a division error that the kernel turns into SIGFPE. The shell reports 136, which is 128 plus that signal number.
#include <stdio.h>
int main(void)
{
int left = 8;
int right = 0;
printf("%d\n", left / right);
return 0;
}
gcc -Wall -Wextra div0.c -o div0
./div0; echo "status: $?"
status: 136
There is no compiler warning, because the divisor is a variable and the error is a run-time condition. The fix is the explicit check from the previous section; a compiler can only warn about a literal zero, as the arithmetic lessons showed. The name SIGFPE is historical: it covers integer division too.
Exercises
- Add unary minus to the parser and the evaluator and test -3+5.
- Add a pow precedence level between term and factor and evaluate 2*3^2.
- Make an unknown variable an error in the evaluator, with the name and the offset printed before exit.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
How does the evaluator compute a binary node?
Answer
It evaluates both children, then applies the operator
The recursive walk returns the left and right values, and the switch applies the arithmetic to them.
-
Why is a variable name copied into its node?
Answer
The lexer buffer is reused for the next token
The lexer writes each identifier into one buffer, so a node that keeps the name must copy it.
-
Where is division by zero checked?
Answer
In the evaluator, before the division
Only the evaluator knows the divisor's value, so it tests the right operand before the operation.
-
What does an unchecked integer division by zero do on x86_64?
Answer
It raises
SIGFPEand the shell reports 136The processor raises the division error, the kernel turns it into a signal, and 128 plus the signal number is 136.
-
What does the evaluator print for
1+2*3?Answer
value: 7
The multiplication runs first and gives 6, and the addition with 1 gives 7.
-
What does this program print for x and y?
#include <stdio.h> struct Symbol{const char*name;int value;}; int main(void){struct Symbol s[2]={{"x",3},{"y",4}};printf("%d %d\n",s[0].value,s[1].value);return 0;}Answer
3 4
The table stores x with value 3 and y with value 4.
-
This program is run with
./zero; echo "status: $?". What does the shell print?#include <stdio.h> #include <stdlib.h> int main(void){int left=8,right=3-3;if(right==0){printf("division by zero\n");return 1;}printf("%d\n",left/right);return 0;}Answer
division by zero / status: 1
The right operand is zero, so the program prints the message and returns 1.
-
What exit status does the shell report for the code shown?
#include <stdio.h> int main(void){int left=8,right=0;printf("%d\n",left/right);return 0;}Answer
136
The process dies on the division error before printing, and the shell reports the signal as 136.
-
What does an unknown variable currently return in the evaluator?
Answer
Zero, because the lookup falls through
The lookup returns zero when no name matches, and the evaluator uses that value silently.
-
What is the fix for the unchecked division crash?
Answer
Check the divisor before the division
The evaluator tests the right operand and reports the error with a status instead of performing the undefined operation.
The code on this page was run with gcc (Alpine 15.2.0) 15.2.0 on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev