CS1101C Lab 4 (Odd Week)

Prefix Recursive Arithmetic

The name of your C program file must be called prefix.c, files with any other name will not be marked.

Preliminary

Recursive Operations

Recursive Multiplication

multiply(x,y) = x + multiply(x,y-1)

int multiply(int x, int y);

multiply(42,5)   =  210
multiply(-42,5)  = -210
multiply(42,-5)  = -210
multiply(-42,-5) =  210

Recursive Modulus

Next, we look at the modulus operation. The modulus operation for finding the remainder can also be formulated as a recurrence relation rather easily. Write a recursive function with the following prototype.

int modulus(int dividend, int divisor);

modulus(42,5)   =  2
modulus(-42,5)  = -2
modulus(42,-5)  =  2
modulus(-42,-5) = -2

Moreover, there is a need to account for division by 0. The following code segment is provided for you (to be included in your recursive function) so as to print out an error message and terminate the program immediately. You will also need to include the stdlib.h header file.

if (!divisor)
{
   fprintf(stderr, "Arithmetic Exception (division by zero error)\n");
   exit(1);
}

Recursive Division

Lastly, we shall look at the division operator. Since modulus above allows for a negative remainder, the quotient result of division will also depend on this such that the following will hold for any integer i.

dividend = quotient * i + remainder

int divide(int dividend, int divisor);

divide(42,5)   =  8
divide(-42,5)  = -8
divide(42,-5)  = -8
divide(-42,-5) =  8

Testing your functions

To ensure that all three recursive functions work before moving on, write a main method that would request the user for two integral numbers and an operation. The sample run of the program is below.

$ gcc -Wall prefix.c -o prefix

$ ./prefix
Enter two integer numbers: 42 5
Enter an operator (1 for * ; 2 for / ; 3 for % ) : 1
The answer is 210.

$ ./prefix
Enter two integer numbers: -42 5
Enter an operator (1 for * ; 2 for / ; 3 for % ) : 2
The answer is -8.

$ ./prefix
Enter two integer numbers: -42 -5
Enter an operator (1 for * ; 2 for / ; 3 for % ) : 3
The answer is -2.

$ ./prefix
Enter two integer numbers: -42 0
Enter an operator (1 for * ; 2 for / ; 3 for % ) : 2
Arithmetic Exception (division by zero error)

$

Bonus Part: Prefix Expression Evaluation

It is very common to write mathematical expressions as infix expressions where parentheses are vital to ensure the ordering of various operations. Examples of infix expressions are 4*3 and (4*3)+(5-2). However, parenthesis can be removed if we rewrite the above using prefix expressions. For the above example, the prefix expressions are * 4 3 and + * 4 3 - 5 2 respectively. Here you will need to use your deductive and inference skills again to determine how valid prefix expressions can be written.

The astute reader will realise that prefix evaluation is actually a recursive process. Your task now is to write a prefix expression evaluator as a recursive function prefix to evaluate a given prefix expression into a final answer. The prototype of the prefix function is given below

int prefix();

• Addition operator: +
• Subtraction operator: -
• Multiplication operator: *
• Division operator: /
• Modulus operator: %
• Unary minus operator: ~

The following main method is provided for you in which the user will enter a valid prefix expression (a valid expression can include blank spaces). In order to read the individual characters within the function prefix, use the getchar(); or scanf("%c",...); functions.

int main(void)
{
   printf("Enter a prefix expression: ");
   printf("The answer is %d.\n", prefix());

   return 0;
}

Sample Run

$ gcc -Wall prefix.c -o prefix

$ ./prefix
Enter prefix expression: *43
The answer is 12.

$ ./prefix
Enter prefix expression: + * 4 3 - 5 2
The answer is 15.

$ ./prefix
Enter prefix expression: +*43   -       52
The answer is 15.

$ ./prefix
Enter prefix expression: *43
The answer is 12.

$ ./prefix
Enter prefix expression: / ~ + * 8 5 2 ~ 5
The answer is 8.

$ ./prefix
Enter prefix expression: /~+*852~5
The answer is 8.

$ ./prefix
Enter prefix expression: %%962
The answer is 1.

$ ./prefix
Enter prefix expression: //44%44
Arithmetic Exception (division by zero error)

$

Note and Ponder

1. Looping constructs, i.e. while and for keywords, are not allowed.

2. Multiplication, division and modulus operators of any form are not allowed.

3. Assume that all user input is valid. No error checking is required.

4. To print the % symbol, use the %% format specifier in your printf statement.

5. If your program does not work as you expect (logical errors), use extra printf statements to print out all the values of your variables to aid in your debugging.

6. Most importantly, have lots of fun programming!

A total of 16 different hosts have accessed this document in the last 445 days; your host, nsrp-source.comp.nus.edu.sg, has accessed it 7 times.

If you're interested, complete statistics for this document are also available, including breakdowns by top-level domain, host name, and date.