# 【課堂筆記】師大-程式設計（二）

char c;
while (scanf("%c", &c) != EOF) {
    printf("%c", c);
}
char s[20];
while (scanf("%s", s) != EOF) {
    printf("%s", s);
}

#include <stdio.h>
#include <ctype.h>

int main() {
    if(isalnum('a')) printf("是字母或數字\n");
    if(isalpha('a')) printf("是字母\n");
    if(isdigit('1')) printf("是數字\n");
    if(islower('a')) printf("是小寫\n");
    if(isupper('A')) printf("是大寫\n");
    char s[] = "Hello";
    for (int i = 0; s[i] != '\0'; i++) {
        printf("%c", tolower(s[i]));
        printf("%c", toupper(s[i]));
    }
}

#include <stdio.h>
#include <string.h>

int main() {
    char s[] = "Hello";
    int length = strlen(s);
    printf("%d", length);
}

char s[20];
char *ptr = s;
scanf("%s", ptr);
printf("%s", ptr);

char a[] = "hello";
char *b = "hello";
printf("size = %ld\n", sizeof(a)); // 6
printf("size = %ld\n", sizeof(b)); // 8, 指標的大小為 8

#include <stdio.h>
#include <string.h>

int main() {
    char a[] = "hello";
    char b[50]; // 需要確保有足夠的空間
    strcpy(b, a);  // 將 a 複製到 b
    printf("%s\n", b); // hello
    strcat(b, a);  // 將 a 串接到 b
    printf("%s\n", b); // hellohello
    strncpy(b, "abcde", 3);
    printf("%s\n", b); // abclohello
    strncat(b, "zzzzz", 3);
    printf("%s\n", b); // abclohellozzz
}

#include <stdio.h>
#include <string.h>

int main() {
    char s1[] = "aa";
    char s2[] = "ab";
    printf("%d\n", strcmp(s1, s2)); // "aa" < "ab"，回傳 -1
    printf("%d\n", strcmp(s1, s1)); // "aa" == "aa"，回傳 0
    printf("%d\n", strcmp(s2, s1)); // "ab" > "aa"，回傳 1
    printf("%d\n", strncmp(s1, s2, 1)); // 0
}

#include <stdio.h>
#include <string.h>
#define length 5

int main() {
    char a[length][12] = {"banana", "apple", "grape", "orange", "mango"};

    // Bubble Sort
    for (int i = length - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (strcmp(a[j], a[j + 1]) > 0) {
                char temp[12];
                strcpy(temp, a[j]);
                strcpy(a[j], a[j + 1]);
                strcpy(a[j + 1], temp);
            }
        }
    }

    for (int i = 0; i < length; i++) {
        printf("%s\n", a[i]); // apple, banana, grape, mango, orange
    }
}

#include <stdio.h>
#include <string.h>

int main() {
    char s[] = "hello world";
    char *pos = strchr(s, 'o'); // 回傳第一個 'o' 的指標，找不到回傳 NULL
    if (pos) {
        printf("index = %ld\n", pos - s); // index = 4
    }
    pos = strrchr(s, 'o'); // 反方向
    if (pos) {
        printf("index = %ld\n", pos - s); // index = 7
    }
}

#include <stdio.h>
#include <string.h>

int main() {
    char s1[] = "hello world";
    char s2[] = "world";
    char *pos = strstr(s1, s2);  // 回傳 "world" 的起始指標
    if (pos) {
        printf("index = %ld\n", pos - s1); // index = 6
    }
}

#include <stdio.h>
#include <string.h> // strtok
#include <stdlib.h> // atoi

int main() {
    char str[] = "2025/3/11";
    char delim[] = "/";

    char *token = strtok(str, delim);

    while (token != NULL) {
        printf("%d ", atoi(token)); // atoi: string 轉 int
        token = strtok(NULL, delim);
    }
}

#include <stdio.h>
#include <string.h> // strcpy()

struct Student {
    char name[20];
    float score;
};

int main() {
    struct Student s1;
    
    strcpy(s1.name, "Andy"); // 不能用 s1.name = "Andy";
    s1.score = 85.5;
    
    printf("%s\n", s1.name);
    printf("%.1f\n", s1.score);
}

#include <stdio.h>

void print_bin(char* s, int n) {
    printf("%s = ", s);
    for (int i = 7; i >= 0; i--) {
        printf("%d", (n >> i) & 1);
    }
    printf("\n");
}

int main() {
    int a = 170, b = 204;
    print_bin("a", a); // 10101010
    print_bin("b", b); // 11001100
    print_bin("a & b", a & b); // 10001000
    print_bin("a | b", a | b); // 11101110
    print_bin("a ^ b", a ^ b); // 01100110
    print_bin("~a", ~a); // 01010101
    print_bin("a << 1", a << 1); // 01010100
    print_bin("a >> 1", a >> 1); // 01010101
}

#include <stdio.h>
#include <stdlib.h> // malloc, free
#include <assert.h> // assert

// malloc = 「m」emory 「alloc」ation (分配)
// assert = 斷言、肯定地說

int main() {
   int n = 5;

   int *a = malloc(n * sizeof(int));
   assert(a != NULL); // 申請失敗時回傳 NULL

   for (int i = 0; i < n; i++) a[i] = i * i;
   for (int i = 0; i < n; i++) printf("%d ", a[i]);

   free(a); // malloc 申請的記憶體必須手動釋放
}

// Linked list (鏈結序列)
#include <stdio.h>
#include <stdlib.h> 
#include <assert.h>

typedef struct node {
   int data;
   struct node *next;
} Node;

Node *genNode(int data, Node *next) {
   Node *node = malloc(sizeof(Node));
   assert(node != NULL);
   node->data = data;
   node->next = next;
   return node;
}

void printList(Node *node) {
   for (; node; node = node->next)
      printf("%d ", node->data);
   printf("\n");
}

void freeList(Node *node) {
   while (node) {
      Node *next = node->next;
      free(node);
      node = next;
   }
}

Node *buildUnsorted(int *a, int n) {
   Node *head = NULL; // 最新節點永遠放在前端
   int i;
   for (i = 0; i < n; i++)
      head = genNode(a[i], head); // 讓新節點指到舊 head
   return head;
}

Node *insertSorted(Node *head, int data) {
   if (!head || data < head->data) // 空串列或要插入最前面
      return genNode(data, head);

   Node *prev = head;
   // 如果下一個節點存在 且 它的資料小於 data -> 往後找
   while (prev->next && prev->next->data < data)
      prev = prev->next;

   prev->next = genNode(data, prev->next);
   return head;
}

Node *deleteValue(Node *head, int target) {
   if (!head) return NULL;
   if (head->data == target) {
      Node *next = head->next;
      free(head);
      return next;
   }
   Node *prev = head;
   while (prev->next && prev->next->data != target)
      prev = prev->next;
   if (prev->next) {
      Node *dead = prev->next;
      prev->next = dead->next;
      free(dead);
   }
   return head;
}

int main() {
   int a[] = {4, 6, 2, 9, 7};
   int n = sizeof(a)/sizeof(a[0]);

   Node *head = NULL;
   for (int i = 0; i < n; i++)
      head = insertSorted(head, a[i]);

   printList(head);
   head = deleteValue(head, 6); // 刪除 6
   printList(head);

   freeList(head);
}

/*
二元搜尋樹 (Binary Search Tree)
用途：儲存可以「快速搜尋」的資料。
規則：對於任一節點，左子樹都比它小，右子樹都比它大。
時間複雜度：O(log n)
*/

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef struct treenode {
   int data;
   struct treenode *left;
   struct treenode *right;
} TreeNode;

TreeNode *genTreeNode(int data) {
   TreeNode *node = malloc(sizeof(TreeNode));
   assert(node != NULL);
   node->data = data;
   node->left = node->right = NULL;
   return node;
}

TreeNode *insertBsTree(TreeNode *root, int data) {
   if (!root) return genTreeNode(data); // 空樹就直接建立節點
   if (data < root->data)
      root->left = insertBsTree(root->left,  data);
   else
      root->right = insertBsTree(root->right, data);
   return root;
}

void printBsTree(TreeNode *root) {
   if (!root) return;
   printBsTree(root->left); // 先印左子樹
   printf("%d ", root->data); // 中間印自己
   printBsTree(root->right); // 最後印右子樹
}

void freeBsTree(TreeNode *root) {
   if (!root) return;
   freeBsTree(root->left);
   freeBsTree(root->right);
   free(root);
}

int searchBsTree(TreeNode *root, int target) {
   if (!root) return 0; // 找不到
   if (root->data == target) return 1; // 找到
   if (target < root->data)
       return searchBsTree(root->left, target); // 去左邊找
   else
       return searchBsTree(root->right, target); // 去右邊找
}

int main() {
   int a[] = {8, 3, 10, 6, 1};
   int n = sizeof(a)/sizeof(a[0]), i;

   TreeNode *root = NULL;
   for (i = 0; i < n; i++)
      root = insertBsTree(root, a[i]);

   printBsTree(root);
   printf(searchBsTree(root, 6) ? "找到！\n" : "找不到！\n");

   freeBsTree(root);
}

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define STACK_SIZE 100
#define MAX_LEN 256

// 模擬 Object 的 Stack 結構與相關方法
typedef struct {
    int top;
    char elements[STACK_SIZE];

    // 方法函式指標
    void (*init)(void *);
    bool (*isFull)(void *);
    bool (*isEmpty)(void *);
    void (*push)(void *, char);
    int  (*pop)(void *);
} Stack;

// 以下是模擬「物件方法」的實作
void initStack(void *self) {
    ((Stack *)self)->top = 0;
}

bool stackIsFull(void *self) {
    return ((Stack *)self)->top >= STACK_SIZE;
}

bool stackIsEmpty(void *self) {
    return ((Stack *)self)->top == 0;
}

void stackPush(void *self, char c) {
    Stack *s = (Stack *)self;
    if (s->isFull(s)) {
        printf("Error: stack is full\n");
        return;
    }
    s->elements[s->top++] = c;
}

int stackPop(void *self) {
    Stack *s = (Stack *)self;
    if (s->isEmpty(s)) {
        printf("Error: stack is empty\n");
        return -1;
    }
    return s->elements[--s->top];
}

// 初始化一個堆疊「物件」，附上方法
void createStack(Stack *s) {
    s->init    = initStack;
    s->isFull  = stackIsFull;
    s->isEmpty = stackIsEmpty;
    s->push    = stackPush;
    s->pop     = stackPop;
    s->init(s);  // 初始化狀態
}

int main() {
    char input[MAX_LEN];
    Stack stk;
    bool balanced = true;

    printf("請輸入一行括號表達式："); // ([]{})
    scanf("%s", input);

    createStack(&stk);

    for (int i = 0; input[i] && balanced; i++) {
        char ch = input[i];
        switch (ch) {
            case '(': case '[': case '{':
                stk.push(&stk, ch);
                break;
            case ')': balanced = (stk.pop(&stk) == '('); break;
            case ']': balanced = (stk.pop(&stk) == '['); break;
            case '}': balanced = (stk.pop(&stk) == '{'); break;
            default: break;  // 忽略其他字元
        }
    }

    if (balanced && stk.isEmpty(&stk)) {
        printf("✅ 括號平衡\n");
    } else {
        printf("❌ 括號不平衡\n");
    }
}