筑波大学 理工情報生命学術院 システム情報工学研究群 情報理工学位プログラム 2017年8月実施 基礎科目 問題IV

Author

祭音Myyura

Description

整数と表 1 に示した演算子で構成された数式を木構造で表現する. 図 1 に，そのような数式を表す木構造の例を示す. 木構造を深さ優先で走査する方法として，先順 (pre-order, 前順)，中順 (in-order, 間順)，後順 (post-order) がある. 図 1(A) に示した木構造を中順で走査すると，次のような中置記法による数式が得られる. ただし，この数式は計算の順序を示すために括弧を含んでいる.

((10 + 20) - 30)

数式を表す木構造を後順で走査すると，後置記法 (逆ポーランド記法) による数式が得られる. 図1(A) に示した木構造を後順で走査すると，次のような数式が得られる. ただし，この数式で要素の区切りは空白である.

10 20 + 30 -

表 1: 整数を扱う演算子

演算子	説明
+	2つの引数を取り，それらの値を加え，その結果を返す.
-	2つの引数を取り，最初の値から 2 番目の値を引き，その結果を返す.
==	2つの引数を取り，それらの値を比較する.それらが等しい場合，真 (0 ではない値) を返す.そうではない場合，偽 (0) を返す.
!	1つの引数を取り，それが真の場合，偽を返す.そうではない場合，真を返す.
?	3つの引数を取り，最初の値をチェックする.最初の値が真の場合，2 番目の値を返す.そうではない場合，3 番目の値を返す.

            (A)                    (B)                                    (C) 

            (-)                    (+)                                    (?)
         /       \              /       \                             /    |    \
       (+)       (30)         (10)      (+)                         (==)  (30)  (40)
     /     \                          /     \                     /      \
   (10)    (20)                    (20)      (+)                (10)     (20)
                                           /     \
                                        (30)     (40)

図 1: 数式を表す木構造の例

次の小問に答えなさい.ただし，以下の図に示されたプログラムは，C 言語で記述されている.

(1) 図1 (B)，および，図1 (C) に示した木構造を，後置記法で表記しなさい.

(2) 次の 2つの数式は，後置記法で表記された木構造を表している.これらの木構造を，図 1 と同じ形式で図示しなさい.

• (D) 1 2 + 3 4 - +
• (E) 1 2 == ! 0 1 ?

(3) 図 2 に示した関数 calc() は，後置記法で表記された数式をスタックを用いて計算する. この関数は，文字列の配列で表現された数式を引数として取る.配列の各要素は，整数を表す文字列，または，演算子を表す文字列である. 配列は，NULL ポインタで終端されている. この関数は，計算の途中結果をスタックに保存する. 関数 calc() が利用しているスタックは， 表 2 に示した関数で操作される. また，関数 calc() は，表 3 に示した関数を利用している. ただし，関数 calc() はエラー処理に問題がある. 図 3 に示した関数 main() が実行された時，画面にどのような出力がなされるかを示しなさい.

表 2: スタックを操作する関数

関数	説明
void init_stack()	スタックを空にし，大域変数 error を 0 に初期化する.
void push(int x)	スタックに整数 x を積む.
int pop()	スタックが空の場合には，大域変数 error に 1 をセットし，0 を返す.このエラーは，スタック・アンダーフローとして知られている.そうではない場合，スタックから整数を取り出し，それを返す.
int free_stack()	スタックが空の場合，真を返す.そうではない場合，スタックの全ての要素を解放し，偽を返す.

表 3: 関数 calc() が文字，文字列，および，整数を操作するために利用する関数

関数	説明
strcmp()	2 つの文字列を引数に取り，それらが等しい場合，0 を返す.そうではない場合，0 以外の値を返す.
isdigit()	文字を引数に取り，それが数字 (’0’ から’9’ の間) である場合に真，そうではない場合に偽を返す.
atoi()	数字から構成される文字列を引数に取り，その文字列を 10 進数とみなし整数に変換し，その整数を返す.

#define NULL    ((void *)0)
#define OK      1
#define ERROR   0

extern int error;

int calc(char *exp[], int *xp) {
    init_stack();
    for (int i = 0; exp[i] != NULL; i++) {
        if (isdigit(exp[i][0]))
            do_num(exp[i]);
        else if (strcmp(exp[i], "+") == 0)
            do_add();
        else if (strcmp(exp[i], "-") == 0)
            do_sub();
        else if (strcmp(exp[i], "==") == 0)
            do_eq();
        else if (strcmp(exp[i], "!") == 0)
            do_not();
        else if (strcmp(exp[i], "?") == 0)
            do_cond();
        else {
            free_stack();
            return (ERROR);
        }
    }
    *xp = pop();
    free_stack();
    if (error)  /*(X)*/
        return (ERROR);
    else
        return (OK);
}

void do_num(char *s) {
    int a;
    a = atoi(s);
    push(a);
}

void do_add() {
    int a, b;
    b = pop();
    a = pop();
    push(a + b);
}

void do_eq() {
    int a, b;
    b = pop();
    a = pop();
    push(a == b);
}

void do_not() {
    int a;
    a = pop();
    push(!a);
}

図 2: 後置記法の数式を計算する関数 calc()

int main() {
    int x = 0;
    char *exp[] = {"30", "50", "+", NULL};
    if (calc(exp, &x) == OK)
        printf("OK. The result is %d.\n", x);
    else
        printf("Error.\n");
    return (0);
}

図 3: 関数 calc() の利用例

(4) 図 4 の空欄を埋めて，関数 do_sub()，および，do_cond() を完成させなさい.

void do_sub() {
    int a, b;
    [ 空欄 (F) ];
    [ 空欄 (G) ];
    push( [ 空欄 (H) ] );
}

void do_cond() {
    int a, b, c;
    [ 空欄 (I) ];
    b = pop();
    [ 空欄 (J) ];
    if (a)
        [ 空欄 (K) ];
    else
        [ 空欄 (L) ];
}

図 4: 関数 do sub() と do cond()

(5) 図 2 の関数 calc() は，実行中にスタック・アンダーフローのエラーが生じ，ERROR を返す時がある. そのような入力の例を1つ示しなさい.

(6) 図 2 の関数 calc() は，「/*(X)*/」と印を付けた所で大域変数 error が真の場合，ERROR を返す. そうではない場合，この関数は，OK を返す. しかし，入力の数式がある種のエラーを含んでいる時，そのエラーを検出できず，OK を返すことがある. そのような入力の例を1つ示しなさい.

(7) 小問 (6) の問題を解決するために，関数 calc() を修正する.関数 calc() への修正方法の概略を示しなさい.

(8) 表 2 に示した関数を，リストを用いて実装する. 図 5 の空欄を埋めて，関数 push()，および，pop() を完成させなさい.ただし，関数 malloc() は常に成功するものとする.

#define NULL ((void *)0)
struct element {
    struct element *next;
    int data;
};

struct element *sp = NULL;
int error = 0;

void push(int x) {
    struct element *n;
    n = malloc(sizeof(struct element));
    [ 空欄 (M) ];
    [ 空欄 (N) ] = x;
    [ 空欄 (O) ];
}

int free_stack() {
    // コード省略
}

int pop() {
    int x;
    struct element *f;
    if ([ 空欄 (P) ]) {
        error = 1;
        return (0);
    }
    [ 空欄 (Q) ];
    f = sp;
    [ 空欄 (R) ];
    free(f);
    return (x);
}

void init_stack() {
    free_stack();
    sp = NULL;
    error = 0;
}

Kai

(1)

• 図 1(B): 10 20 30 40 + + +
• 図 1(C): 10 20 == 30 40 ?

(2)

                (D)                                     (E)
            
                (+)                                     (?)
            /         \                             /    |    \
         (+)          (-)                         (!)   (0)    (1)
       /     \      /     \                      /
     (1)     (2)  (3)     (4)                  (==)
                                              /    \
                                            (1)    (2)

(3)

OK. The result is 80.

(4)

• [ 空欄 (F) ]: a = pop()
• [ 空欄 (G) ]: b = pop()
• [ 空欄 (H) ]: b - a
• [ 空欄 (I) ]: c = pop()
• [ 空欄 (J) ]: a = pop()
• [ 空欄 (K) ]: push(b)
• [ 空欄 (L) ]: push()

(5)

char *exp[] = {"30", "+", NULL};

(6)

char *exp[] = {"30", "50", "40", "+", NULL};

(7)

int calc(char *exp[], int *xp) {
    // コード省略

    *xp = pop();
    int flag = free_stack();
    if (error || (!flag))  /*(X)*/
        return (ERROR);
    else
        return (OK);
}

(8)

• [ 空欄 (M) ]: n->next = sp
• [ 空欄 (N) ]: n->data
• [ 空欄 (O) ]: sp = n
• [ 空欄 (P) ]: sp == NULL
• [ 空欄 (Q) ]: x = sp->data
• [ 空欄 (R) ]: sp = sp->next