Implementing a term rewriting system in a procedural language

How can I implement a term rewriting system in a procedural language like C? More precisely, I want to implement a system where, for example, a user can input the following rules:

add .a 0 = a
add .a (suc .b) = suc (add .a .b)
2 = suc 1
1 = suc 0

whereupon the user can input a term like add 2 2 to obtain

add 2 2
= add 2 (suc 1)
= suc (add 2 1)
= suc (add 2 (suc 0))
= suc (suc (add 2 0))
= suc (suc 2)
= suc (suc (suc 1))
= suc (suc (suc (suc 0)))

In these examples, the .token notation is used to distinguish variables from constants.

Parsing the input string itself into a tree-like data structure does not seem too difficult, but I am unsure about how to proceed with pattern matching, variable substitution, evaluation order, and so forth, which are required to actually apply the rules to the input term.

Examples I have seen online tend to use languages like Haskell or Lisp that already have this capability, but I am interested in building it from the ground up using a procedural langauge. Are there any resources (preferably available online) I could use to learn this?