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

标签：

• Tsukuba-University
• Stack

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;
}

题目描述

用树结构表示由整数和表 1 所列运算符组成的表达式。图 1 给出了这类表达式树的示例。树的深度优先遍历方式包括前序（pre-order）、中序（in-order）和后序（post-order）遍历。

对图 1(A) 的树作中序遍历，可得到下面的中缀表达式；括号用于明确运算顺序。

((10 + 20) - 30)

对表达式树作后序遍历，则可得到后缀表达式（逆波兰式）。图 1(A) 对应的后缀表达式如下，其中各元素以空格分隔。

10 20 + 30 -

表 1：整数运算符

运算符	说明
+	接收两个参数，把二者相加并返回结果。
-	接收两个参数，用第一个值减去第二个值并返回结果。
==	接收两个参数并比较二者；相等时返回真（非 0 值），否则返回假（0）。
!	接收一个参数；参数为真时返回假，否则返回真。
?	接收三个参数并检查第一个值；第一个值为真时返回第二个值，否则返回第三个值。

            (A)                    (B)                                    (C)

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

图 1：表示表达式的树结构示例

回答下列小问。以下各图中的程序均用 C 语言编写。

1. 分别用后缀记法写出图 1(B) 和图 1(C) 所示的表达式树。

2. 下面两个后缀表达式分别表示一棵树。按照图 1 的形式画出这两棵树。

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

3. 图 2 中的函数 calc() 使用栈计算后缀表达式。该函数接收一个表示表达式的字符串数组作为参数；数组的每个元素要么是表示整数的字符串，要么是表示运算符的字符串，并以 NULL 指针结束。函数把计算过程中的中间结果保存在栈中，使用表 2 所列函数操作栈，并使用表 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()	接收两个字符串；相等时返回 0，否则返回非 0 值。
isdigit()	接收一个字符；若其为数字字符（'0'～'9'）则返回真，否则返回假。
atoi()	接收一个由数字组成的字符串，把它按十进制转换为整数并返回。

#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。给出一个会造成这种情况的输入示例。

6. 图 2 的 calc() 在标有 /*(X)*/ 的位置检查全局变量 error；若为真则返回 ERROR，否则返回 OK。然而，某些错误表达式不会被发现，函数仍会返回 OK。给出一个这样的输入示例。

7. 为解决第 6 问的问题，需要修改 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($c$)

(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