---
# System prepended metadata

title: Lab8

---

# Lab&HW 8 Preprocessing and multiple files for large program

[TOC]

## Forum Link

https://hackmd.io/@mE_mKnTkS9me4b6LFOmF6w/Bk9uUmL4T#Homework-8-1-grading

## Lab 8-1 & 8-2 stack with static capacity

Stack is a data structure follow the rule “FILO(First In Last Out)” or “LIFO(Last In First Out)”
For example, if we want to do the following operation: push A, push B, pop, push C, pop, pop, will look like
![](https://i.imgur.com/hvsSVSW.png)

### **Lab 8-1 requirnments**

For the Lab 8-1, you just have to write the code to implement the stack with static size in c and submit it to the [online judge](https://oj.cerana.tech/contest/16/problem/1) to test the logic part of your program. 

I have already finished most of the code, you just only have to implement the functions of stack. 

**Template for Lab 8-1**
```cpp=
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct stack {
    int *_contents;
    int _top, _capacity;
} Stack;

void make_empty(Stack *s, int size);
bool is_empty(const Stack *s);
int size(const Stack *s);
void push(Stack *s, int i); // TODO
void pop(Stack *s);	// TODO
int peek(const Stack *s); // TODO
void clear_stack(Stack *s);
void print_stack(const Stack *s);

int main() {
    char op[10];
    Stack s;
    make_empty(&s, 64);

    while(scanf("%s", op) != EOF) {
        if (strcmp(op, "push") == 0) {
            int i;
            scanf("%d", &i);
            push(&s, i);
        } else if (strcmp(op, "pop") == 0) {
            pop(&s);
        } else if (strcmp(op, "peek") == 0) {
            if(is_empty(&s))
                peek(&s);
            else 
                printf("%d\n", peek(&s));
        } else if (strcmp(op, "size") == 0) {
            printf("%d\n", size(&s));
        } else if (strcmp(op, "is_empty") == 0) {
            printf("%s\n", is_empty(&s) ? "The stack is empty. " : "The stack is not empty. ");
        } else if (strcmp(op, "clear") == 0) {
            print_stack(&s);
            clear_stack(&s);
        } else {
            printf("Invalid operation\n");
        }
    }
}

void make_empty(Stack *s, int capacity) {
    s->_contents = (int *)malloc(capacity * sizeof(int));
    s->_top = 0;
    s->_capacity = capacity;
}

void clear_stack(Stack *s) {
    s->_top = 0;
    free(s->_contents);
}

bool is_empty(const Stack *s) {
    return s->_top == 0;
}

int size(const Stack *s) {
    return s->_top;
}

void print_stack(const Stack *s) {
    printf("Current stack contains: ");
    for (int i = s->_top - 1; i >= 0; i--) {
        printf("%d ", s->_contents[i]);
    }
    puts("");
}
```


### **Lab 8-2 requirnments**

For the Lab 8-2, you have to let the implementation of your code in Lab 8-1 to be in the header file `.h` and the main functions in the source `.c` file. Moreover, you should use the custom_assert that taught in class and `DEBUG` macro to make the debug mode of your program. 
After finished Lab8-2, you have to explain to the TA about how you done it and submit the files to the e3.

**How to use macro**

In the `stack.c` file, you should use the macro `DEBUG` to check whether the debug mode is on or not. If the debug mode is on, you should print the debug message.

For example, if you want to print the debug message like **current elements in stack** in the `int peek(const Stack *s)` function, you should write the code like this:
```c=stack.c
int peek(const Stack *s) {
#ifdef DEBUG
    print_stack(s);
    printf("Peeking at stack\n");
#endif
    if (is_empty(s)) {
        assert("The stack is empty. ");
        return 0;
    } else {
        return s->_contents[s->_top - 1];
    }
}
```

**Custom assert**

You can refer to `custom_assert.c` and `custom_assert.h` to write your `.c` and `.h` files. 

```cpp=
// custom_assert.h
#ifndef CUSTOM_ASSERT_H
#define CUSTOM_ASSERT_H

#define assert(EX) custom_assert(EX, __FILE__, __LINE__)

void custom_assert(const char *, char *, int);

#endif
```

```cpp=
// custom_assert.c
#include <stdio.h>
#include "custom_assert.h"

void custom_assert(const char *msg, char *file, int line){
    char buffer[100];
    sprintf (buffer,"assertion failed: %s:%d: %s\n", file, line, msg);
    printf("%s", buffer);
}
```

**How to use Makefile**
TA had written a simple `Makefile` for you. You can simply run `make` in your terminal, if your file structure is valid(like below) the program will automatically compile and link the files. 

> If your are using IDE(e.g. Codeblock, DevC++, Eclipse), you'll have to figure out how to config it up yourself. 

> If you are using terminal, you can run `make` for compile without DEBUG flag and `make debug` with DEBUG flag. 

```makefile=
// Makefile
CC=gcc
EXE=main
OBJDIR=obj
OBJ=$(addprefix $(OBJDIR)/, stack.o custom_assert.o $(EXE).o)

$(OBJDIR)/%.o: %.c
	@mkdir -p $(OBJDIR)
	@$(CC) -c $< -o $@

all: $(OBJ)
	 $(CC) $(OBJ) -o $(EXE)

run: all
	 ./$(EXE)

debug: CC += -DDEBUG -g
debug: all
.PHONY: debug

clean:
	rm -f $(OBJDIR)/*.o $(EXE)
	rmdir $(OBJDIR)
.PHONY: clean
```

**lab 8-2 file structure**
```
{student_id}_lab8-2
├── main.c
├── custom_assert.c
├── custom_assert.h
├── stack.c
├── stack.h
├── Makefile
```

## Homework 8-1: Simple browser history manager

For Homework 8-1, you need to modify the stack that you implemented in Lab 8-2 to implement a simple history manager. 

It sounds hard, right? Don't worry! TAs has already implemented most of the code [here](https://github.com/YJack0000/ICP-hw8-template). 
(You can download it on the github page)
![upload_dde4787dc6a1dcfe915fa638154796ce](https://hackmd.io/_uploads/BJRYUqUET.png)

You just have to understand the relation and the usage of functions and objects, then implement a few function to the `browser.c`. The rest of file should remain the same, TA will only copy your `browser.c` when testing your code. 

While doing this homework, you will review concepts that were covered in previous labs and homeworks, including the `struct`, `macro` and `pointer`. 

**Challenge branch**
If you find it is not hard enough for you, you can start with the [challenge branch](https://github.com/YJack0000/ICP-hw8-template/tree/challenge). There is more files remain empty, and you should think how to implement `webpage.c` and `webpage_stack.c` by yourself. You will get a lot of experience through this exercise. 
![upload_3d8b06078d16d4f09626cb2b88b0d107](https://hackmd.io/_uploads/B1U68cUN6.png)

**!!!Notice!!!**
The `Makefile` in the repository are not containing `run` and `debug`. If you want to use it while you are writing the homework, you should try to add by yourself. 
However, TA will only check outcome of your program and wil not check your DEBUG mode program. 


### **Homework 8-1 requirnments**

For the Homework 8-1, you have to make the program to work like the following example. 

**Input Description**
Inputs containes `t` commands, where `0 < t < 1500`

The browser will start with a blank page. (i.e. the stack is empty, and the current page is null)

The total number of pages will not exceed `1000`.
The length of the `title`of each page will not exceed `255`.
The length of the `url` of each page will not exceed `2047`.

The command will be one of the following:
```bash
new <url> <title>   # create a new page with the given url and title
current             # print the current page data
back                # navigate back to the previous page
forward             # navigate forward to the next page
```

Sample input 1:
```
current
new https://www.google.com google
current
new https://www.facebook.com facebook
current
forward
back
current
back
```

Sample output 1:
```
---
Empty
---
---
Title: google
URL: https://www.google.com
---
---
Title: facebook
URL: https://www.facebook.com
---
Cannot navigate forward
---
Title: google
URL: https://www.google.com
---
Cannot navigate back
```

Description for sample 1:
```
current -> Now there is no page yet, Print "empty"
new https://www.google.com google -> Now the current page is google
current -> Print the current page, which is google
new https://www.facebook.com facebook -> Now the current page is facebook, and the google where move to stack
current -> Print current page, which is facebook
forward -> Go to the next page, which is nothing. So print "Cannot navigate forward"
back -> Go back to google, and the facebook will be in the history for forward page
current ->  Current page is google 
back -> There is no page before google, so print "Cannot navigate back"
```

Sample input 2:
```
new https://www.google.com google
new https://www.facebook.com facebook
new https://www.youtube.com youtube
new https://www.instagram.com instagram
current
back
back
new https://www.nycu.edu.tw nycu
current
forward
back
current
```


Sample output 2:
```
---
Title: instagram
URL: https://www.instagram.com
---
---
Title: nycu
URL: https://www.nycu.edu.tw
---
Cannot navigate forward
---
Title: facebook
URL: https://www.facebook.com
---
```

### **Homework 8-1 grading** 
The assignment will have 5 test cases, and they won't be overly challenging. As long as you can successfully execute and complete the sample case, you can score 40 points.

However, if you simply print out the answer, or if you cram all the code into one file, it will be considered as a score of 0 points. Please make good use of this assignment to practice writing programs with multiple files and to become more skilled with structs and pointers. 

## Homework 8-2: Debugger Report

**Assignment:**
    Please refer to the following code (code file HW8_Debugger.c has been
posted on e3), and use a C program debugger (e.g., GDB) to identify and fix all bugs
in the code.

**Restrictions:**
You are not allowed to add or delete any lines of code. Only modify
variable declarations, operators, conditional statements, output formats, output
format, etc., to make the code compilable.

There are a total of 4 places that need modification. Please indicate the 4 locations
that need modification and describe the changes made, following the order of lines
in the code.

**Response template:**
> Line **<number>**: **<your explanation>**

**Code:**
```cpp
#include <stdio.h>
#include <string.h>

#define MSG_LEN 60

// Caesar cipher
void Caesar(char *message, int k) { // Receive the message and the shift number
    int idx = 0; // Declare idx to store the index of the message
    while(message[idx] != '\0') { // Use while loop to iterate the string, until the end of the string
        char *c = &message[idx];// Use pointer and idx to access the character of string
        if (*c > 'A' && *c < 'Z') { // If the character is uppercase
            *c = (*c - 'A' + k) % 26 + 'A'; // Use the formula to shift the character, and wrap around if the character is out of range
        }
        else if (*c > 'a' && *c < 'z') { // If the character is lowercase
            *c = (*c - 'a' + k) % 26 + 'a'; // Use the formula to shift the character, and wrap around if the character is out of range
        }
        idx++; // Increment idx
    }
}

// Reverse the string
void reverse(char *message) { // Receive the message
    int temp;
    char *p = message + strlen(message)-1;// Declare a temp variable and a pointer to the end of the string
    while (*p >= 0) { // Use while loop to iterate the string, until the pointer is at the beginning of the string
        // Swap the character at the beginning and the end of the string
        temp = *message;
        *message++ = *p;
        *p-- = temp;
    }
}

int read_line(char str[], int n) {
    int ch, i = 0;
    while (1) {
        ch = getchar();
        if (ch == '\n' || ch == EOF)
            break;
        if (i < n)
            str[i++] = ch;
    }
    i++;
    str[i] = '\0';
    return i;
}

int main() {
    int n; // Declare n to store the number of test cases
    scanf("%d", &n); // Read the input of test cases
    getchar(); // Use getchar() to read the newline character, otherwise the newline character will be read in the next read_line()
    while (n > 0) { // Use while loop to iterate the test cases
        char msg[MSG_LEN]; // Declare msg to store the message, +1 for the null character
        int k; // Caeser cipher shift number
        read_line(msg, MSG_LEN-1); // Read the message
        scanf("%d", &k); // Read the shift number
        getchar(); // Use getchar() to read the newline character
        Caesar(msg, k);// Call the Caesar function
        reverse(msg);// Call the reverse function
        printf("%s\n", msg);// Print the message
        n--;
    }
    return 0;
}
```

## Submission
Compress your lab & homework to `.zip` file
- lab
```
{student_id}_lab8
├── {student_id}_lab8-1
|   └──{student_id}_lab8-1.c
└── {student_id}_lab8-2
    └──main.c
    └──custom_assert.c
    └──custom_assert.h
    └──stack.c
    └──stack.h
    └──Makefile
    
```
compress `{student_id}_lab8` to `{student_id}_lab8.zip` and submit to e3
- homework
```
{student_id}_hw8
├── {student_id}_hw8-1
|   └──main.c
|   └──browser.c
|   └──browser.h
|   └──webpage.c
|   └──webpage.h
|   └──webpage_stack.c
|   └──webpage_stack.h
|   └──Makefile
└── {student_id}_hw8-2
    └──{student_id}_hw8-2.pdf
```
compress `{student_id}_hw8` to `{student_id}_hw8.zip` and submit to e3

![](https://hackmd.io/_uploads/HJ8iRH9Za.png)

---
    
