Projects developed under the Programming Lab college chair during the 2017/2018 school year
Python implementation of an interpreter of an arithmetic expression language with variable definitions. Arithmetic expressions must be in prefix notation (e.g. (* 2 6) or (+ 5 x), and variables must be defined by assignments of the form (define x 5). The interpreter argument is a string of expressions.
To handle variables we used a table that associates variables with their value. This table is updated by define statements and is used to evaluate variables. It is maintained as a global variable and implemented as a list of (variable, value) pairs.
The interpreter's inner workings are mainly divided in three distinct functions:
- Tokenize, which splits the initial string into a list of words
- Parse, which takes as argument a list of words (tokens) and return a list of tuples that represent each expression
- Avalia, which takes as argument the list of tuples returned by the parser and returns the result of the evaluation of the expressions
For the expr = “(define x 5) ( + (* 2 x) 7)”
tokenize(expr) = [´(´, ´define´, ´x´, ´5´, ´)´ , ´(´, ´+´ , ´(´, ´*´ , ´2´, ´x´, ´)´ , ´7´, ´)´ ]
parse(tokenize(expr) = [ ( ´define´, ´x´, 5 ) , ( ´+´ , ( ´*´, 2 , ´x´) , 7 ) ]
avalia(parse(tokenize(expr) = 17
Implementation of a recursive function that compute the nth fibonacci number, with an optimized alterative using an array of partial results such that a[i] contains the fibonacci number of order i (dynamic programming). Implementation of a module of arithmetic for big-numbers that are used for a third version of the fibonacci succession, to calculate larger values.
A big-number is represented by a list of its digits. The goal is to represent structures for big-numbers (using lists) and their constructors and access functions and to implement the basic arithmetic functions for big-numbers (addition, difference, multiplication, and division). To facilitate these operations, assume that the digits are in the list in reverse order. Example:
123 + 49 = 172 is represented by:
[3, 2, 1] + [9, 4] = [2, 7, 1]
Compile:
"gcc bignum.c list.c main.c"
Execute:
"./a.out 'OPTION'(EXEMPLOS or FIB);