In Programming Paradigms, students explore all sorts of different languages such as Scheme, Python, Java, and JavaScript in order to familiarize themselves with various programming paradigms such as functional programming, object-oriented programming, and event-driven programming. For instance, at the beginning of the semester, the students had to implement a Tic-tac-toe evaluator in Scheme. Unfortunately, they had to use a janky Scheme implementation called Guile which produces lovely error messages such as:

ERROR: In procedure car: Wrong type (expecting pair): ()

Not satisfied with this inferior Scheme1, you decide to make your own arithmetic Scheme interpreter that supports the following EBNF grammar:

<digit>         = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<number>        = {<digit>}
<op>            = - | + | * | /
<expression>    = (<op> <expression> ...) | <number>

Given the above definition, note the following:

  1. You only have to support natural numbers (i.e. 0, 1, 10, 100, ...)

  2. You only have to support basic arithmetic operators: addition, subtraction, multiplication, and division.

  3. You have to support variable length expressions (that is operations that take two or more arguments) or numeric literals.

  4. You do not have to worry about syntax errors or invalid input. You can safely assume that any given test input will follow these rules.

Blast From the Past

If you need more guidance on how to solve this project, you can check out the Project 01: Arithmetic Scheme Interpreter write-up from a previous instance of the Data Structures course (note that version only supports binary operations, you need to support variable length operations).

If you have already written a Scheme interpreter, challenge yourself by writing one in a different language.


You interpreter will be given multiple lines of input where each line is a single Scheme expression as defined by the EBNF grammar above. You should process these expressions until you reach EOF.

Example Input

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


For each Scheme expression (that is for each line), output the final evaluation result.

Example Output



To submit your work, follow the same procedure you used for Reading 00:

$ cd path/to/cse-30872-fa19-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitLab

$ git checkout -b challenge22               # Create and checkout challenge22 branch

$ $EDITOR challenge22/program.cpp           # Edit your code

$ git add challenge22/program.cpp           # Stage your changes
$ git commit -m "challenge22: done"         # Commit your changes

$ git push -u origin challenge22            # Send changes to GitLab

To check your code, you can use the .scripts/ script or curl:

$ .scripts/
Submitting challenge22 assignment ...

Submitting challenge22 code ...
  Result Success
   Score 6.00
    Time 0.26

$ curl -F source=@challenge22/program.cpp
{"score": 6, "result": "Success"}

Once you have commited your work and pushed it to GitLab, member to create a merge request. Refer to the Reading 11 TA List to determine your corresponding TA for the merge request.

  1. Some better Scheme implementations: Racket, Chicken Scheme, and my former love Gauche Scheme