Your task is to develop a huge integer calculator that works with integers of up to 100 digits. The calculator has a simple user interface, and 10 variables (n0, n1, ..., n9) into which integers can be stored. For example, a session with your calculator might look like: mac: ./assmt1 > n0=2147483648 > n0+3 > n0? 2147483651 > n1=1000000000000000000 > n1+n0 > n1? 1000000002147483651 > n0? 2147483651 > exit mac: Note: mac: is the terminal prompt and > is the prompt of the calculator. The calculator to be implemented has a very limited syntax: constants or other variables can be assigned to variables using an = operator; variable values can be altered using a single operator and another variable or constant; variable values can be printed using ?. Each line of input command always starts with a variable followed by a single operator, which is then followed by (optional depending on the operator) another variable or a constant. The only exception is the exit command, which has no additional parameters. To allow storage of huge integers, your calculator needs to use arrays of integers, with one digit stored per element in the array. The number of digits in a huge integer needs to be stored as well. We assume a maximum of 100 digits in a huge integer, and use a reverse order representation. For example, 123 will be represented by: #define INT_SIZE 100 typedef int huge_t[INT_SIZE]; huge_t var_n0 = {3, 2, 1}; int var_len0 = 3; Here, array var_n0 stores the digits of 123 in a reversed way. The reverse order representation will make calculations such as addition and multiplication easier. However, if you wish, you are free to change how the digits are stored in the array. By using struct we can further simplify the representation, but you are not required to do so as it has not been covered yet. The expected input format for all stages is identical - a sequence of simple commands as shown above. You may assume that the input is always valid, that is, you do not need to consider input errors. All input integers are unsigned. You do not need to consider negative numbers or subtraction. There will not be n0=+0, n0=+123, n0=-123, n0-123, or n0++123 in the input. It will just be in the forms of, e.g., n0=0, n0=123, n0+123, or n0*123. There will not be leading 0s in the input numbers, e.g., 001. You will be given a skeleton code ?le named assmt1.c for this assignment in LMS. The skeleton code ?le contains a main function where a loop is used to continuously read in user commands, and calls relevant functions to process the commands. The exit function has been implemented already, which can handle the exit command if you compile and run the skeleton code. The echo function for the ? operator to print out a huge integer has been given to you for reference as well, but you need to implement the init function to initialise the variables ?rst before echo can work properly. All the other function bodies are empty. Your task is to add code into them to process the other calculator commands. Note that you should not change the main function, but you are free to modify any other parts of the skeleton code (including adding more functions). You can change echo as well if you wish to change how a huge integer is stored in an array. 3.1 Stage 1 - Getting Started (Up to 3 Marks) Your ?rst task is to understand the skeleton code. Note the use of the type huge_t in the skeleton code. Each of the huge_t variables in the array vars stores a huge integer, with 10 variables available in total, named n0, n1, ..., n9, respectively. In this stage, you will start with implementing the init function to initialise the variable values to be 0. A sample execution session of this stage is shown below. > n0? 0 > n8? 0 3.2 Stage 2 - Reading in a Huge Integer (Up to 8 Marks) Next, you will implement the assign function to enable assigning a constant value to a variable, or the value of a variable to another variable (both could be the same variable, e.g., n0=n0). A sample execution session of this stage is shown below. > n0=2147483648 > n0? 2147483648

> n1=n0 > n1? 2147483648 You should plan carefully, rather than just leaping in and starting to edit the skeleton code. Then, before moving through the rest of the stages, you should test your program thoroughly to make sure its correctness. 3.3 Stage 3 - Adding up Two Huge Integers (Up to 13 Marks) Now add code to the add function to enable adding up two huge integers. Note that the + operator always starts with a variable, e.g., n0, followed by + itself. After that there are two cases: an integer constant or another variable. Your code should be able to handle both cases: adding up a variable with a constant value, and adding up two variables (both could be the same variable). The sum should always be stored in the starting variable of the command. A sample execution session of this stage is shown below. > n0=2147483648 > n0+1 > n0? 2147483649 > n0+2 > n0? 2147483651 > n1=10000000000000000000000000000000000000000 > n1+n0 > n1? 10000000000000000000000000000002147483651 > n0? 2147483651 Note that we assume integers with up to 100 digits. They can still over?ow if we are adding up even larger numbers. In this case, we will simply ignore the over?owed digits and keep the remaining part in the sum. You should also remove any leading 0s in the sum, i.e., your program should not produce numbers like 0001 (which should be 1). 3.4 Stage 4 - Multiplying Two Huge Integers (Up to 15 Marks) The next operator to add is *. You will need to modify the multiply function for this stage. When this stage is done, your program should be able to process the following sample input. > n0=123 > n1=4567 > n0*n1 > n0? 561741 > n1? 4567 > n2=100000000000000000000000000000000000000000000000000 > n2*100000000000000000000000000000000000000000000000000 > n2? 0 When there is an over?ow, we follow the same procedure as in addition. That is, to keep the non-over?owed part only. You should also remove any leading 0s in the product. You need to think carefully about the algorithm to use in this task. You may implement the process to do long multiplication that you learned at school. Some supporting functions may be needed. For example, a function multiply_digit that takes a huge_t variable and multiplies it by a single-digit integer may be useful; as might a function multiply_base that multiplies a huge_t variable by 10. There are also other (more e?cient) ways to do multiplication, and you can be creative if you wish. Just do not try and do it by repeated addition (penalties apply). 3.5 Stage 5 - Supporting the Power of Operator (Up to 15 Marks) This stage is for a challenge. Please do not start on this stage until your program through to Stage 4 is (in your opinion) perfect, and is submitted, and is veri?ed, and is backed up. For a challenge, implement the power function for the power of operator ^ (no need to consider 00): > n0=2 > n0^4 > n0? 16 > n1=2 > n1^n0 > n1? 65536 Hint: You may use repeated multiplications for this stage.

the skeleton code as follows:

#include #include #include #include

#define INT_SIZE 100 /* max number of digits per integer value */ #define LINE_LEN 103 /* maximum length of any input line */ #define NUM_VARS 10 /* number of different huge int "variables" */

#define ASN_OP '=' /* assignment operator */ #define ECH_OP '?' /* echo operator */ #define ADD_OP '+' /* addition operator */ #define MUL_OP '*' /* multiplication operator */ #define POW_OP '^' /* power of operator */

#define OPR1_POS 1 /* position of the first operand */ #define OPR2_POS 3 /* position of the second operand */ #define OP_POS 2 /* position of the operator */

#define CH_ZERO '0' /* character 0 */

#define EXIT_CMD "exit" /* command to exit */ #define PROMPT "> " /* command prompt */ #define CMT_FLAG '%' /* indicator for comment line */

typedef int digit_t; /* a decimal digit */ typedef digit_t huge_t[INT_SIZE]; /* one huge int "variable" */

/* add your constant and type definitions here */

/****************************************************************/

/* function prototypes */ void read_line(char *line, int max_len); void init(huge_t vars[], int lens[]); void echo(huge_t vars[], int lens[], int opr1_index); void assign(huge_t vars[], int lens[], int opr1_index, char *opr2_str); void add(huge_t vars[], int lens[], int opr1_index, char *opr2_str); void multiply(huge_t vars[], int lens[], int opr1_index, char *opr2_str); void power(huge_t vars[], int lens[], int opr1_index, char *opr2_str);

/* add your function prototypes here */

/****************************************************************/

/* main function controls all the action, do NOT modify this function */ int main(int argc, char *argv[]) { char line[LINE_LEN+1]; /* to hold the input line */ huge_t vars[NUM_VARS]; /* to hold 10 huge integers */ int lens[NUM_VARS]; /* to hold the length of the 10 vars */ int opr1_index; /* index of the first operand in command */ char op; /* operator in command */ init(vars, lens); while (1) { printf(PROMPT); /* print prompt */ read_line(line, LINE_LEN); /* read one line of command */

if (line[0] == CMT_FLAG) { /* print comment in the test data */ printf("%s ", line); /* used to simplify marking */ continue; } if (strcmp(line, EXIT_CMD) == 0) { /* see if command is "exit" */ return 0; } opr1_index = line[OPR1_POS] - CH_ZERO;/* first var number at line[1] */ op = line[OP_POS]; /* operator at line[2] */

if (op == ECH_OP) { /* print out the variable */ echo(vars, lens, opr1_index); continue; } /* do the calculation, second operand starts at line[3] */ if (op == ASN_OP) { assign(vars, lens, opr1_index, line+OPR2_POS); } else if (op == ADD_OP) { add(vars, lens, opr1_index, line+OPR2_POS); } else if (op == MUL_OP) { multiply(vars, lens, opr1_index, line+OPR2_POS); } else if (op == POW_OP) { power(vars, lens, opr1_index, line+OPR2_POS); } } /* all done; take some rest */ return 0; }

/* read a line of input into the array passed as argument */ void read_line(char *line, int max_len) { int i = 0, c; while (((c = getchar()) != EOF) && (c != ' ') && (c != ' ')) { if (i < max_len) { line[i++] = c; } else { printf("Invalid input line, toooooooo long. "); exit(0); } } line[i] = '\0'; }

/* print out a huge integer */ void echo(huge_t vars[], int lens[], int opr1_index) { int i; /* print the digits in a reverse order */ for (i = lens[opr1_index]-1; i >= 0; i--) { printf("%d", vars[opr1_index][i]); } printf(" "); }

/****************************************************************/

/* add code below to complete the function bodies, * add more functions where appropriate. */

/* set the vars array to zeros */ void init(huge_t vars[], int lens[]) { }

/* process the '=' operator */ void assign(huge_t vars[], int lens[], int opr1_index, char *opr2_str) { }

/* process the '+' operator */ void add(huge_t vars[], int lens[], int opr1_index, char *opr2_str) { }

/* process the '*' operator */ void multiply(huge_t vars[], int lens[], int opr1_index, char *opr2_str) {

}

/* process the '^' operator */ void power(huge_t vars[], int lens[], int opr1_index, char *opr2_str) {

}