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

Author

祭音Myyura

Description

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

1	`((10 + 20) - 30)`

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

1	`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)

1	`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(\(c\))

(5)

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

(6)

1	`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

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