---
# System prepended metadata

title: 程式設計Ⅱ【筆記Ⅱ】
tags: [Programming]

---

# 程式設計Ⅱ【筆記Ⅱ】

* [name=Ivy Lin]
* [筆記Ⅰ](https://hackmd.io/lvLLSXxoTo6hLxpEyBIJbQ)
* [筆記ⅠⅠⅠ](https://hackmd.io/JpCPopTTTLyZ91yi279ewA)
* [//筆記Ⅳ](https://hackmd.io/Ts0lnTMpQgGPGw7cvc3X-A)

# 第四週 <*2023.10.3*>

### ***Binary Tree***

### **遍歷樹的規則**

* *pre-order*
    > 中 - 左 - 右
* *in-order*
    > 左 - 中 - 右
* *post-order*
    > 右 - 中 - 左


### 從樹=>各種排列

> 從一棵樹得知它的各種order排列(使用遞迴)


### 實作

```clike=
#include <stdio.h>
#include <stdlib.h>
typedef struct _Node
{
    int num;
    struct _Node *left;
    struct _Node *right;
} Node;

Node *new_node(int number)
{
    Node *p = (Node *)malloc(sizeof(Node));
    p->num = number;
    p->left = NULL;
    p->right = NULL;
    return p;
}

void in_order(Node *root)
{
    if (root)
    {
        in_order(root->left);
        printf(" %d ", root->num);
        in_order(root->right);
    }
}

void pre_order(Node *root)
{
    if (root)
    {
        printf(" %d ", root->num);
        pre_order(root->left);
        pre_order(root->right);
    }
}

void post_order(Node *root)
{
    if (root)
    {
        post_order(root->right);
        printf(" %d ", root->num);
        post_order(root->left);
    }
}
int main()
{
    Node *root;
    root = new_node(2);
    root->left = new_node(7);
    root->right = new_node(5);
    root->left->left = new_node(3);
    root->left->right = new_node(6);

    printf("in_order tree =>");
    in_order(root);
    printf("\n");
    
    printf("pre_order tree =>");
    pre_order(root);
    printf("\n");
    
    printf("post_order tree =>");
    post_order(root);
    printf("\n");
    return 0;
}
```




### 利用其中兩種解法得出樹的結構

> 利用 pre-order來決定root，尋找inorder中的root點並將區域切成左右兩塊，遞迴施作即可找到樹的結構


```clike=
#include <stdio.h>
#include <stdlib.h>
#define max 100
// int cur;
typedef struct _Node
{
    int num;
    struct _Node *left;
    struct _Node *right;
} Node;
int pre_seq[max];
int in_seq[max];

Node *new_node(int number)
{
    Node *p = (Node *)malloc(sizeof(Node));
    p->num = number;
    p->left = NULL;
    p->right = NULL;

    return p;
}

void post_order(Node *root)
{
    if (root)
    {
        post_order(root->left);
        post_order(root->right);
        printf(" %d ", root->num);
    }
}

int find_in_seq(int start, int end, int num)
{
    for (int i = start; i <= end; i++)
    {
        if (in_seq[i] == num)
            return i;
    }
    return -1;
}

// 要知道inorder的哪個位置
Node *build_tree(int start, int end)
{
    // 找到目前的節點本人在哪
    static int cur = 0;
    if (start > end)
        return NULL;
    Node *p = new_node(pre_seq[cur]);
    cur++;
    if (start < end)
    {
        int inde = find_in_seq(start, end, p->num);

        p->left = build_tree(start, inde - 1); // tree

        p->right = build_tree(inde + 1, end);
    }
    // tree

    return p;
}

int main()
{
    Node *root;
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &in_seq[i]);
    for (int i = 0; i < n; i++)
        scanf("%d", &pre_seq[i]);

    root = build_tree(0, n - 1);

    //  post_order(root);

    return 0;
}

```


### 砍樹

> 將每個節點都free掉
> 需要從葉子節點開始free(要不然會少free)


//delete的函式
```clike=
void delete(Node *p)
{
    if (p != NULL)
    {
        delete (p->left);
        delete (p->right);
        free(p);
    }
}
```


### 尋找最大值

>先從左邊最大和自己比較
>再找尋右邊最大值
>最終回傳total max

```clike=
int find_max(Node *p)
{
    if (p != NULL)
    {
        int left_max = find_max(p->left);
        if (left_max < p->num)
            left_max = p->num;

        int right_max = find_max(p->right);

        return (left_max > right_max) ? left_max : right_max;
    }
    else
        return -1;
}
```

### 畫出一棵樹

> 使用 GVEdit 程式就可以把上面的 binary tree 描述檔，轉成圖片

 程式需要的格式=>
 ```clike=
 digraph T {
    2 -> 7;
    2 -> 5;
    7 -> 3;
    7 -> 6;
    6 -> 8;
    6 -> 11;
    5 -> 9;
    9 -> 4;
}
```

實作程式碼 =>
```clike=
void printTree(FILE *fout, Node *tree)
{
    if (tree!=NULL) {
        if (tree->left!=NULL)
            fprintf(fout, "%d -> %d;\n", tree->data, tree->left->data);
        if (tree->right!=NULL)
            fprintf(fout, "%d -> %d;\n", tree->data, tree->right->data);
        printTree(fout, tree->left);
        printTree(fout, tree->right);
    }
}

void writeGV(Node *tree)
{
    FILE *fout = fopen("tree.gv", "w");
    fprintf(fout, "digraph T {\n");
    printTree(fout, tree);
    fprintf(fout, "}\n");
}
```

# 第5週 <*2023.10.10*>
> 上機

# 第6週 <*2023.10.17*>

## ***分析 Binary Expression 以及建構 Syntax Tree***

### ***Expression 運算(bool)***

> 利用優先運算子讀取數學運算式，讓電腦可以計算
> 作法:
    > 自行定義一個型態，對照輸入的字串遞迴計算

```clike=
// bool states
#include <stdio.h>
#include <stdlib.h>
#include <ctype>
#include <string.h>
typedef enum
{
    VA,
    VB,
    VC,
    VD,
    OP_AND,
    OP_OR,
    END
} TokenSet; // 將每個變數取名字!(可以直接寫變數名稱當作值來使用)
char sym[] = "ABCD&|";
char expr[256];
TokenSet getnext(int reset)
{
    static int idx;
    TokenSet ret = END;
    if (reset)
    {
        idx = 0;
        return END;
    }

    // isspace => 判斷現在的這格是不是空白字元
    while (expr[idx] != '\0' && isspace(expr[idx]))
        idx++;

    if (expr[idx] == '\0')
        return END;
    else
    {
        // 另一種寫法:(size_t)i<strlen(sym)
        // 將i強制轉為(size_t)的型式=>無符號整數(通常用於表達內存和索引)
        int l = strlen(sym);
        for (int i = 0; i < l - 1; i++)
            if (sym[i] == expr[idx])
                ret = i;
        idx++;
        return ret;
    }
}

void evaluate(int A, int B, int C, int D)
{
    TokenSet tok;
    int ev1, ev2;
    tok = getnext(0);

    switch (tok)
    {
    case VA:
        return A;
    case VB:
        return B;
    case VC:
        return C;
    case VD:
        return D;
    case OP_AND:
        ev1 = evaluate(A, B, C, D);
        ev2 = evaluate(A, B, C, D);
        return ev1 && ev2;
        // break;
    case OP_OR:
        ev1 = evaluate(A, B, C, D);
        ev2 = evaluate(A, B, C, D);
        return ev1 || ev2;
    case END:
        tok = getnext(1);
        return evaluate(A, B, C, D);
    }

    return 0;
}

int main()
{

    fgets(expr, sizeof(expr), stdin);
    int len = strlen(expr);
    if (len > 0 && expr[len - 1] == '\n')
    {
        --len;
        expr[len] = '\n';
    }

    for (int i = 0; i < 16; i++)
    {
        printf("%d%d%d%d:%d\n", (i & 8) >> 3, (i & 4) >> 2, (i & 2) >> 1, (i & 1));
        evaluate((i & 8) >> 3, (i & 4) >> 2, (i & 2) >> 1, i % 1);
    }
    return 0;
}
```

### ***Expression 運算(十進位)***

```clike=
//程設一的範例
#include <stdio.h>
#include <ctype.h>

int calculate(void);

int main(void)
{
    printf("=%d\n", calculate());
    return 0;
}

int calculate(void)
{
    int c;
    int ans;
    int op1, op2;

    c = getchar();
    if (isspace(c))
    {
        ans = calculate();
    }
    else if (c == '+')
    {
        printf("(");
        op1 = calculate();
        printf("+");
        op2 = calculate();
        printf(")");
        ans = op1 + op2;
    }
    else if (c == '-')
    {
        printf("(");
        op1 = calculate();
        printf("-");
        op2 = calculate();
        printf(")");
        ans = op1 - op2;
    }
    else if (c == '*')
    {
        printf("(");
        op1 = calculate();
        printf("*");
        op2 = calculate();
        printf(")");
        ans = op1 * op2;
    }
    else if (isdigit(c))
    {
        ungetc(c, stdin);
        scanf("%d", &ans);
        printf("%d", ans);
    }

    return ans;
}
```


### ***建立 Syntax Tree***
```clike=
//範例程式碼
# include <string.h>
# include <stdlib.h>
# include <ctype.h>

# define MAXEXPR 256

char expr[MAXEXPR];
int pos;

typedef enum {VAR_A, VAR_B, VAR_C, VAR_D, OP_AND, OP_OR, END
             } TokenSet;
char sym[]="ABCD&|()";

typedef struct _Node {
    TokenSet data;
    struct _Node *left, *right;
} BTNode;

BTNode* EXPR();
BTNode* FACTOR();

/* create a node without any child.*/
BTNode* makeNode(char c){
    int i;
    BTNode *node = (BTNode*) malloc(sizeof(BTNode));
    for (i = 0; (unsigned int)i < strlen(sym); i++)
        if (c==sym[i]) node->data = i;
    node->left = NULL;
    node->right = NULL;
    return node;
}

/* clean a tree.*/
void freeTree(BTNode *root){
    if (root!=NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

/* print a tree by pre-order. */
void printPrefix(BTNode *root){
    if (root != NULL) {
        printf("%c",sym[root->data]);
        printPrefix(root->left);
        printPrefix(root->right);
    }
}

/* FACTOR = VAR | (EXPR) */
BTNode* FACTOR(){
    char c;
    BTNode *node = NULL;

    if (pos>=0) {
        c = expr[pos--];
        if (c>= 'A' && c<='D'){ // apply the rule FACTOR = VAR
            // make a new node for VAR
            node = makeNode(c);
        } else if (c==')') {  // apply the rule FACTOR = (EXPR)
            // get the node pointer from recusive call of EXPR()
            node = EXPR();
            if(expr[pos--]!= '(') {  // the left parenthesis is needed
                printf("Error: not matching parenthesis!\n");
                freeTree(node);
            }
        }
    }
    return node;
}

/* parse an infix expression and generate a syntax tree.
 EXPR = FACTOR| EXPR OP FACTOR */
BTNode* EXPR(){
    char c;
    BTNode *node = NULL, *right=NULL;

    if (pos>=0) {   // if the expression has length > 1.
        // get the pointer to the right child from calling the function FACTOR()
        right = FACTOR();
        if (pos>0) {
            c = expr[pos];
            if (c=='&' || c=='|'){  // apply the rule EXPR = EXPR OP FACTOR
                // make a new node for the OP
                node = makeNode(c);
                // set the node's right child as ...
                node->right = right;
                pos--; // this step is important

                // set the node's left child from recursive call of EXPR()
                node->left = EXPR();
            } else node = right; // apply the rule EXPR = FACTOR
        } else
            node = right; // apply the rule EXPR = FACTOR
    }
    return node;
}

int main(void)
{
      size_t len;
    fgets(expr, sizeof(expr), stdin);
    len = strlen(expr);
    if (len > 0 && expr[len-1] == '\n') {
        --len;
        expr[len] = '\0';
    }
    pos = strlen(expr) - 1;
    BTNode *root = EXPR();
    printPrefix(root);
    freeTree(root);
    return 0;
}
```

> 利用樹狀結構，遍歷樹的方式來計算*prefix expression*的字串

```clike=
//程式碼本人+註解們

// FACTOR | EXPR 語法規則
/*
FACTOE = VAR 或 (EXPR)
EXPR = FACTOR 或 EXPR OP FACTOR
*/
/*
演算法本人
1)先使用EXPR的與法 => 從最底層取出一個FACTOR
2)如果有一個OP在此FACTOR中 => FACTOR是OP的右小孩
                         => 遞迴其他的部分並讓其成為OP的左小孩
*/
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
// Enum
typedef enum
{
    VAR_A,
    VAR_B,
    VAR_C,
    VAR_D,
    OP_AND,
    OP_OR,
    END
} TokenSet;

// Structure
typedef struct _Node
{
    TokenSet data;
    struct _Node *left, *right;
} BTNode;

// Globol
char expr[256];
int pos;
char sym[] = "ABCD&|()";
BTNode *EXPR();
BTNode *FACTOR();

// Make tree
BTNode *makeNode(char c)
{
    int i;
    BTNode *node = (BTNode *)malloc(sizeof(BTNode));
    for (i = 0; (unsigned int)i < strlen(sym); i++)
        if (c == sym[i])
            node->data = i;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Free tree
void freeTree(BTNode *root)
{
    if (root != NULL)
    {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

// Print tree => Count ans
void printPrefix(BTNode *root)
{
    if (root != NULL)
    {
        printf("%c", sym[root->data]);
        printPrefix(root->left);
        printPrefix(root->right);
    }
}
int evalPrefix(BTNode *root, int A, int B, int C, int D)
{
    int ev1, ev2;
    if (root != NULL)
    {
        printf("%c", sym[root->data]);
        if (root->data == OP_AND)
        {
            ev1 = evalPrefix(root->left, A, B, C, D);
            ev2 = evalPrefix(root->right, A, B, C, D);
            return ev1 && ev2;
        }
        else if (root->data == OP_OR)
        {
            ev1 = evalPrefix(root->left, A, B, C, D);
            ev2 = evalPrefix(root->right, A, B, C, D);
            return ev1 || ev2;
        }
        else
        {
            switch (root->data)
            {
            case VAR_A:
                return A;
            case VAR_B:
                return B;
            case VAR_C:
                return C;
            case VAR_D:
                return D;
            }
        }
    }
}

// Function1 FACTOR
BTNode *FACTOR()
{
    char c;
    BTNode *node = NULL;

    if (pos >= 0)
    {
        c = expr[pos--];
        if (c >= 'A' && c <= 'D')
        { // apply the rule FACTOR = VAR
            // make a new node for VAR
            node = makeNode(c);
        }
        else if (c == ')')
        { // apply the rule FACTOR = (EXPR)
            // get the node pointer from recusive call of EXPR()
            node = EXPR();
            if (expr[pos--] != '(')
            { // the left parenthesis is needed
                printf("Error: not matching parenthesis!\n");
                freeTree(node);
            }
        }
    }
    return node;
}
// Function2 EXPR
BTNode *EXPR()
{
    char c;
    BTNode *node = NULL, *right = NULL;

    if (pos >= 0)
    { // if the expression has length > 1.
        // get the pointer to the right child from calling the function FACTOR()
        right = FACTOR();
        if (pos > 0)
        {
            c = expr[pos];
            if (c == '&' || c == '|')
            { // apply the rule EXPR = EXPR OP FACTOR
                // make a new node for the OP
                node = makeNode(c);
                // set the node's right child as ...
                node->right = right;
                pos--; // this step is important

                // set the node's left child from recursive call of EXPR()
                node->left = EXPR();
            }
            else
                node = right; // apply the rule EXPR = FACTOR
        }
        else
            node = right; // apply the rule EXPR = FACTOR
    }
    return node;
}

// Main
int main(void)
{
    size_t len;
    fgets(expr, sizeof(expr), stdin);
    len = strlen(expr);
    if (len > 0 && expr[len - 1] == '\n')
    {
        --len;
        expr[len] = '\0';
    }
    pos = strlen(expr) - 1;
    BTNode *root = EXPR();
    printPrefix(root);

    printf("%d\n", evalPrefix(root, 0, 1, 1, 1));
    freeTree(root);
    return 0;
}
```


# 第7週 <*2023.10.24*>


* ***Project***
> [Wikipedia](http://rosettacode.org/wiki/Arithmetic_Evaluator/C)
1. 目的: 寫出一個計算機
2. 實作:
    * 用Token記住元素(Operator、Int 等等)
    * 將對應的字串紀錄在陣列中
    * 寫出函數來取出Token

3. 程式碼

* C語言的標頭檔
> ***<引用防護>***
    * 像是以下使用#ifndef #endif 等等，為了避免重覆引用和定義(有些編譯器不允許符號定義兩次)
        * 基本格式(參考google開源)
```clike=
#ifndef 標頭檔的命名_H_
#define 標頭檔的命名_H_    
...
#endif //標頭檔的命名_H_ 
```

> ***<定義函數宣告>***
        * 基本的宣告以及如何使用函數
    * #include 引用路徑 / 順序
    
> [標頭檔介紹參考資料](https://tw-google-styleguide.readthedocs.io/en/latest/google-cpp-styleguide/headers.html)
> [計算機參考程式碼](https://github.com/htchen/calculator_tree/blob/master/main_trial3.c)
    

* 運算規則
    1. statement  := END | expr END
    2. expr       := term expr_tail
    3. expr_tail  := ADDSUB(加或減) term expr_tail | NIL(空字串)
    4. term       := facter term_tail
    5. term_tail  := MULDIV factor term_tail | NIL(空字串)
    6. factor     := INT | ADDSUB(加或減) INT | ADDSUB(加或減) ID | ID ASSIGN expr | ID | LPAREN expr RPAREN



* ***標頭檔本人 lex.h***
```clike=
//使用標頭檔慣用的保護程式架構(ifndef-define-endif)
//定義globol => TokenSet
//定義基本函數宣告(前面加上extern代表函數在其他檔案中定義)
#ifndef __LEX__
#define __LEX__
#define MAXLEN 256
typedef enum
{
    UNKNOWN,
    END,
    INT,
    ID,
    ADDSUB,
    MULDIV,
    ASSIGN,
    LPAREN,
    RPAREN
} TokenSet;

extern int match(TokenSet token);
extern void advance(void);
extern char *getLexeme(void);
#endif // __LEX__
```


* ***檔案1 lex.c***
```clike=
#include <stdio.h>
#include <ctype.h>
#include <string.h>
//引用自行定義的標頭檔 
#include "lex.h"

//定義此檔案會使用的globol
static TokenSet getToken(void);
static TokenSet lookahead = UNKNOWN;
static char lexeme[MAXLEN];


//主函式
TokenSet getToken(void)
{
    int i;
    char c;

    while ((c = fgetc(stdin)) == ' ' || c == '\t')
        ; // ©¿²¤ªÅ¥Õ¦r¤¸

    if (isdigit(c))
    {
        lexeme[0] = c;
        c = fgetc(stdin);
        i = 1;
        while (isdigit(c) && i < MAXLEN)
        {
            lexeme[i] = c;
            ++i;
            c = fgetc(stdin);
        }
        ungetc(c, stdin);
        lexeme[i] = '\0';
        return INT;
    }
    else if (c == '+' || c == '-')
    {
        lexeme[0] = c;
        lexeme[1] = '\0';
        return ADDSUB;
    }
    else if (c == '*' || c == '/')
    {
        lexeme[0] = c;
        lexeme[1] = '\0';
        return MULDIV;
    }
    else if (c == '\n')
    {
        lexeme[0] = '\0';
        return END;
    }
    else if (c == '=')
    {
        strcpy(lexeme, "=");
        return ASSIGN;
    }
    else if (c == '(')
    {
        strcpy(lexeme, "(");
        return LPAREN;
    }
    else if (c == ')')
    {
        strcpy(lexeme, ")");
        return RPAREN;
    }
    else if (isalpha(c) || c == '_')
    {
        lexeme[0] = c;
        c = fgetc(stdin);
        i = 1;
        while (isalpha(c) || isdigit(c) || c == '_')
        {
            lexeme[i] = c;
            ++i;
            c = fgetc(stdin);
        }
        ungetc(c, stdin);
        lexeme[i] = '\0';
        return ID;
    }
    else
    {
        return UNKNOWN;
    }
}



//len.h中宣告過的函式 => 直接定義函數內容
void advance(void)
{
    lookahead = getToken();
}
int match(TokenSet token)
{
    if (lookahead == UNKNOWN)
        advance();
    return token == lookahead;
}
char *getLexeme(void)
{
    return lexeme;
}
```


* ***main函式 main.c***






### Syntax Tree

* 改建成Syntax Tree的版本
    * lex.c / lex.h和原本相同
    * [完整程式碼參考](https://github.com/htchen/calculator_tree)
```clike=
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
//引用標頭檔
#include "lex.h"

//宣告檔案會使用到的函式
void error(ErrorType errorNum);

//宣告會使用到的struct
typedef struct
{
    char name[MAXLEN];
    int val;
} Symbol;
typedef struct _Node
{
    char lexeme[MAXLEN];
    TokenSet token;
    int val;
    struct _Node *left, *right;
} BTNode;
typedef enum
{
    MISPAREN,
    NOTNUMID,
    NOTFOUND,
    RUNOUT,
    NAN
} ErrorType;

//global
#define TBLSIZE 65535
Symbol table[TBLSIZE];
int sbcount = 0;
void statement(void);
BTNode *expr(void);
BTNode *term(void);
BTNode *factor(void);
int getval(void);
int setval(char *, int);





/* create a node without any child */
BTNode *makeNode(TokenSet tok, const char *lexe)
{
    BTNode *node = (BTNode *)malloc(sizeof(BTNode));
    strcpy(node->lexeme, lexe);
    node->token = tok;
    node->val = 0;
    node->left = NULL;
    node->right = NULL;
    return node;
}

/* clean a tree */
void freeTree(BTNode *root)
{
    if (root != NULL)
    {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

/* print a tree by pre-order */
void printPrefix(BTNode *root)
{
    if (root != NULL)
    {
        printf("%s ", root->lexeme);
        printPrefix(root->left);
        printPrefix(root->right);
    }
}

/* traverse the syntax tree by pre-order
   and evaluate the underlying expression */
int evaluateTree(BTNode *root)
{
    int retval = 0, lv, rv;
    if (root != NULL)
    {
        switch (root->token)
        {
        case ID:
        case INT:
            retval = root->val;
            break;
        case ASSIGN:
        case ADDSUB:
        case MULDIV:
            lv = evaluateTree(root->left);
            rv = evaluateTree(root->right);
            if (strcmp(root->lexeme, "+") == 0)
                retval = lv + rv;
            else if (strcmp(root->lexeme, "-") == 0)
                retval = lv - rv;
            else if (strcmp(root->lexeme, "*") == 0)
                retval = lv * rv;
            else if (strcmp(root->lexeme, "/") == 0)
            {
                if (rv == 0)
                    error(NAN);
                else
                    retval = lv / rv;
            }
            else if (strcmp(root->lexeme, "=") == 0)
                retval = setval(root->left->lexeme, rv);
            break;
        default:
            retval = 0;
        }
    }
    return retval;
}

int getval(void)
{
    int i, retval, found;

    if (match(INT))
    {
        retval = atoi(getLexeme());
    }
    else if (match(ID))
    {
        i = 0;
        found = 0;
        retval = 0;
        while (i < sbcount && !found)
        {
            if (strcmp(getLexeme(), table[i].name) == 0)
            {
                retval = table[i].val;
                found = 1;
                break;
            }
            else
                i++;
        }
        if (!found)
        {
            if (sbcount < TBLSIZE)
            {
                strcpy(table[sbcount].name, getLexeme());
                table[sbcount].val = 0;
                sbcount++;
            }
            else
                error(RUNOUT);
        }
    }
    return retval;
}

int setval(char *str, int val)
{
    int i, retval = 0;
    i = 0;
    while (i < sbcount)
    {
        if (strcmp(str, table[i].name) == 0)
        {
            table[i].val = val;
            retval = val;
            break;
        }
        else
            i++;
    }
    return retval;
}

//  expr        := term expr_tail
//  expr_tail   := ADDSUB term expr_tail | NIL
BTNode *expr(void)
{
    BTNode *retp, *left;
    retp = left = term();
    while (match(ADDSUB))
    { // tail recursion => while
        retp = makeNode(ADDSUB, getLexeme());
        advance();
        retp->right = term();
        retp->left = left;
        left = retp;
    }
    return retp;
}

//  term        := factor term_tail
//  term_tail := MULDIV factor term_tail | NIL
BTNode *term(void)
{
    BTNode *retp, *left;
    retp = left = factor();
    while (match(MULDIV))
    { // tail recursion => while
        retp = makeNode(MULDIV, getLexeme());
        advance();
        retp->right = factor();
        retp->left = left;
        left = retp;
    }
    return retp;
}

BTNode *factor(void)
{
    BTNode *retp = NULL;
    char tmpstr[MAXLEN];

    if (match(INT))
    {
        retp = makeNode(INT, getLexeme());
        retp->val = getval();
        advance();
    }
    else if (match(ID))
    {
        BTNode *left = makeNode(ID, getLexeme());
        left->val = getval();
        strcpy(tmpstr, getLexeme());
        advance();
        if (match(ASSIGN))
        {
            retp = makeNode(ASSIGN, getLexeme());
            advance();
            retp->right = expr();
            retp->left = left;
        }
        else
            retp = left;
    }
    else if (match(ADDSUB))
    {
        strcpy(tmpstr, getLexeme());
        advance();
        if (match(ID) || match(INT))
        {
            retp = makeNode(ADDSUB, tmpstr);
            if (match(ID))
                retp->right = makeNode(ID, getLexeme());
            else
                retp->right = makeNode(INT, getLexeme());
            retp->right->val = getval();
            retp->left = makeNode(INT, "0");
            retp->left->val = 0;
            advance();
        }
        else
            error(NOTNUMID);
    }
    else if (match(LPAREN))
    {
        advance();
        retp = expr();
        if (match(RPAREN))
            advance();
        else
            error(MISPAREN);
    }
    else
        error(NOTNUMID);
    return retp;
}

void error(ErrorType errorNum)
{
    switch (errorNum)
    {
    case MISPAREN:
        fprintf(stderr, "Mismatched parenthesis\n");
        break;
    case NOTNUMID:
        fprintf(stderr, "Number or identifier expected\n");
        break;
    case NOTFOUND:
        fprintf(stderr, "%s not defined\n", getLexeme());
        break;
    case RUNOUT:
        fprintf(stderr, "Out of memory\n");
        break;
    case NAN:
        fprintf(stderr, "Not a number\n");
    }
    exit(0);
}

void statement(void)
{
    BTNode *retp;

    if (match(END))
    {
        printf(">> ");
        advance();
    }
    else
    {
        retp = expr();
        if (match(END))
        {
            printf("%d\n", evaluateTree(retp));
            printPrefix(retp);
            printf("\n");
            freeTree(retp);

            printf(">> ");
            advance();
        }
    }
}

int main()
{
    printf(">> ");
    while (1)
        statement();

    return 0;
}

```



# 第八週 <*2023.10.30*>

## 組合語言

* ***Get assembly code***
> *in terminal*
> => ***gcc -S ex1.c*** // *get assembly code of ex1.c*
> => ***-gcc -S -masm=intel ex1.c*** // *x86 CPU & intel style's assembly*
> => ***-gcc ex1.c***  //*compile assembly code*

* ***Assembly v.s. C code***
```clike=
int b;
int main(){
    b=3;
    int a;
    a=5;
}
```

```asm=
//assignment 
mov DWORD PTR b,3;
mov DWORD PTR [esp+12],5
```

* ***MOV instruction***
語法 => *MOV destination, source *//將右側資料搬動到左側
* ***DWORD data size***


| *Type Specifier* | *Bytes addressed* | 
| -------- | -------- | 
| *BYTE*   | 1     | 
| *WORD*   | 2     | 
| *DWORD*  | 4     | 
| *QWORD*  |8      | 


* ***Indiret memory access***
*Register 'esp' holds an address of memory*
