Build a Polish Notation Interpreter in C with MPC – Step-by-Step Guide

Polish Notation

Polish Notation (prefix notation) places operators before their operands, eliminating the need for parentheses and operator‑precedence handling.

Using this notation simplifies the grammar and parser for the Lispy language, though it can be less readable for complex expressions.

Syntax Rules

Before implementing the parser we define its syntax: always start with an operator, followed by numbers or expressions; an expression can consist of an operator and numbers or other expressions.

Lexical Rules

We use regular expressions to constrain input, wrapping them in slashes for MPC. For example, a number is defined as /‑?[0-9]+/.

Polish Notation Parser

Based on the analysis we implement a parser using MPC so that Lispy can understand and evaluate arithmetic expressions.

Grammar Implementation

#include <stdio.h>
#include <stdlib.h>
#include "mpc.h"

#ifdef _WIN32
#include <string.h>
#endif

static char buffer[2048];

char *readline(char *prompt) {
    fputs(prompt, stdout);
    fgets(buffer, 2048, stdin);
    char *cpy = malloc(strlen(buffer) + 1);
    strcpy(cpy, buffer);
    cpy[strlen(cpy) - 1] = '\0';
    return cpy;
}

void add_history(char *unused) {}

#ifdef __linux__
#include <readline/readline.h>
#include <readline/history.h>
#endif
#ifdef __MACH__
#include <readline/readline.h>
#endif

long eval_op(long x, char *op, long y) {
    if (strcmp(op, "+") == 0) return x + y;
    if (strcmp(op, "-") == 0) return x - y;
    if (strcmp(op, "*") == 0) return x * y;
    if (strcmp(op, "/") == 0) return x / y;
    return 0;
}

long eval(mpc_ast_t *t) {
    if (strstr(t->tag, "number")) {
        return atoi(t->contents);
    }
    char *op = t->children[1]->contents;
    long x = eval(t->children[2]);
    int i = 3;
    while (strstr(t->children[i]->tag, "expr")) {
        x = eval_op(x, op, eval(t->children[i]));
        i++;
    }
    return x;
}

int main(int argc, char *argv[]) {
    mpc_parser_t *Number   = mpc_new("number");
    mpc_parser_t *Operator = mpc_new("operator");
    mpc_parser_t *Expr     = mpc_new("expr");
    mpc_parser_t *Lispy    = mpc_new("lispy");

    mpca_lang(MPCA_LANG_DEFAULT,
      "number   : /-?[0-9]+/ ;\
       operator : '+' | '-' | '*' | '/' ;\
       expr     : <number> | '(' <operator> <expr>+ ')' ;\
       lispy    : /^/ <operator> <expr>+ $/ ;",
      Number, Operator, Expr, Lispy);

    puts("Lispy Version 0.1");
    puts("Press Ctrl+c to Exit
");

    while (1) {
        char *input = NULL;
        input = readline("lispy> ");
        add_history(input);

        mpc_result_t r;
        if (mpc_parse("<stdin>", input, Lispy, &r)) {
            long result = eval(r.output);
            printf("%li
", result);
            mpc_ast_delete(r.output);
        } else {
            mpc_err_print(r.error);
            mpc_err_delete(r.error);
        }
        free(input);
    }

    mpc_cleanup(4, Number, Operator, Expr, Lispy);
    return 0;
}

Compile with:

gcc -std=c99 -Wall main.c mpc.c -lreadline -lm -o main

Running the program and parsing an expression such as + 5 (* 2 2) produces an AST that shows the structure of the expression, with tags and contents for each node. Leaf nodes hold the actual numbers or operators.

Evaluation

We traverse the AST recursively: number nodes are converted to integers, and operator nodes are applied to their child expressions using eval_op. This yields the final computed value.

/* Example interaction */
Lispy Version 0.1
Press Ctrl+c to Exit

lispy> + 4 5
9
lispy> - 8 3
5
lispy> * 6 2
12
lispy> / 10 5
2
lispy> - (* 10 10) (+ 1 1 1)
97

The tutorial demonstrates how Polish notation can be parsed and evaluated efficiently using MPC, providing a solid foundation for building simple interpreters.