CS201: Data Structures and Algorithms

Assignment 1, Version 1

Printable Version


For your second programming assignment, you are to implement a infix expression calculator using a stack and a queue.


Your executable must be named matilda. The executable reads in a series of strings or numbers, either from a file or from stdin, and will produce, on stdout, whether or not each of the inputs is a palindrome. Here is an example invocation:
    $ echo 999 * 8888 ; > items
    $ matilda items
where $ is the system prompt. The file to be processed (items in the example) is a free-format text file. That is, the numbers, variables, operators, and semicolons found within are separated by arbitrary amounts of whitespace (i.e. spaces, tabs, and newlines) and every line ends with a newline. If a file name is not given, input is to be read from the keyboard:
    $ matilda
    999 * 8888 ;
Keyboard input is ended by entering a ^D character.

The executable must handle the following options:
option example action
-v matilda -v give author's name and exit
-d matilda -d FILENAME print the postfix conversion of the last infix expression
found in FILENAME instead of printing the answer
matilda -d print the postfix conversion of the last infix expression
read in from stdin instead of printing the answer

Here are some example invocations using options:
    $ matilda -v
    Alyssa P. Hacker
    $ matilda -d
    var a = 3 ;
    var b = 4 ;
    b + a ;
    b * a ;

    b a * ;
The last expression shown, b a * ;, is the postfix conversion of the last expression entered, b * a ;. Here is another example:
    $ echo var a = 3 \; > expr
    $ echo var b = 4 \; >> expr
    $ echo b + a \; >> expr
    $ echo b * a \; >> expr
    $ matilda -d expr
    b a * ;
Here is a program that features some handy-dandy option-handling code that you may use verbatim without credit: options.c


Expressions will be composed of literals (integers, real numbers, and quoted strings), variables (tokens beginning with an alphabetic character), and operators ( = + - * / % ^), plus parentheses. All tokens will be surrounded by whitespace. For example, the expression: (x+1)*2; is illegal and should be written as ( x + 1 ) * 2 ;
A token in the input stream can be identified as follows:
The operators have precedence in increasing order from assignment to plus to minus to times to divides to modulus to exponentiation. Parentheses override precedence. All operators are left associative:
    $ matilda -d
    5 + 3 * ( 4 - 2 ) - 1 ;
    5 3 4 2 - * 1 - + ;


An integer and a real combined together yields a real number:
    $ matilda
    3 * 123. ;
Two strings added together results in a concatenation of the two operands:
    $ matilda
    "a b c" + "123" ;
    "a b c123"
Here is a code snippet for safely concatenating two strings a and b, placing the result in c:
    char *c = malloc(sizeof(char) * (strlen(a) + strlen(b) + 1));
    assert(c != 0);
A string combined with a number causes the string to be converted to a number of the same type:
    $ matilda
    3.2 * "123" ;
    $ matilda
    "123.4" * 3 ;
Use atoi or atof to convert a string to an integer or real number, respectively.

Declarations and assignment

Variables are declared with the var keyword:
    $ matilda
    var x = 3 ;
    x ;
All declarations will appear first. The initializer in a variable declaration will be a number or a string: The value of a variable may be changed via assignment:
    $ matilda
    var x = 3 ;
    var y ;
    y = ( x - 1 ) * 4 - 2 ;
    x + y ;
Variables and their values should be stored in a binary search tree for later retrieval during the processing of the postfix expression. A variable will only be declared once, so the binary search tree will contain unique keys. The specification for a binary search tree can be found here: http://beastie.cs.ua.edu/cs201/assign-bst.q.
Assignment is an operator which changes the value of a variable. The value of an assignment is the value assigned:
    $ matilda
    var x = 1 ;
    var y = 2 ;
    x = y = x + y ;
Only a variable can appear to the immediate left of an assignment operator.

Reading the input

You may find the Art and Science of Programming - C Edition scanner to be useful for this task:
    wget troll.cs.ua.edu/ACP-C/scanner.c
    wget troll.cs.ua.edu/ACP-C/scanner.h
You can read a token with the scanner and then examine the token to see what kind of value it is. You may not use scanf to read into a fixed-length character array.

Error checking

The only error checking you must perform is detecting the use of a variable that was not declared:
    $ matilda
    x + 3 ;
    variable x was not declared
After printing the error message on standard error, you should exit the program. Other than this one exception, your program will only be tested with valid input.

You must follow the C programming style guide for this project: http://beastie.cs.ua.edu/cs201/cstyle.html.

Compilation details

You must implement your calculator algorithm in portable C99. You must provide a makefile which responds properly to the commands:
    make test
    make clean
The make command compile the matilda executable, which should compile cleanly with no warnings or errors at the highest level of error checking (the -Wall and -Wextra options.). The make test command should test your program and the make clean command should remove object files and the executable. Here are examples (your files may differ in number and name):
    $ make clean
    rm -f scanner.o value.o node.o queue.o stack.o bst.o convert.o matilda.o matilda
    $ make
    gcc -Wall -std=c99 -c -g scanner.c
    gcc -Wall -std=c99 -c -g value.c
    gcc -Wall -std=c99 -c -g node.c
    gcc -Wall -std=c99 -c -g queue.c
    gcc -Wall -std=c99 -c -g stack.c
    gcc -Wall -std=c99 -c -g bst.c
    gcc -Wall -std=c99 -c -g convert.c
    gcc -Wall -std=c99 -c -g matilda.c
    gcc -Wall -std=c99 scanner.o value.o node.o queue.o stack.o bst.o convert.o matilda.o -o matilda
    $ make
    make: `matilda' is up to date.
    $ make test
    matilda -d mytestfile
    a b * c + 4 1 - /
    matilda mytestfile
The compilation command must name the executable matilda (not matilda.exe for you Cygwin users). The You may develop on any system you wish but your program will be compiled and tested on a Linux system. Only the most foolish students would not thoroughly test their implementations on a Linux system before submission.


All code you hand in must be attributed to its authors. Comment sparingly but well. Do explain the purpose of your program. Do not explain obvious code. If code is not obvious, consider rewriting the code rather than explaining what is going on through comments.


Grading will proceed as with assignment 0. In addition to testing your program, your binary search tree module and your matilda module will be tested individually.


To submit assignments, you need to install the submit system.
You will hand in (electronically) your code for the preliminary assessment and for final testing with the command:
    submit cs201 lusth assign1
Make sure you are in the same directory as your makefile when submitting. The submit program will bundle up all the files in your current directory and ship them to me. Thus it is very important that only the source code and any testing files be in your directory. This includes subdirectories as well since all the files in any subdirectories will also be shipped to me. I will deduct points if you submit object files or executables, so be careful. You may submit as many times as you want before the deadline; new submissions replace old submissions. Old submissions are stored and can be used for backup.