書籍
- C言語プログラミング ハーベイ M.ダイテル (著), ポール J.ダイテル (著), 小嶋 隆一 (翻訳)
- 開発環境
- Visual Stdio Code
- gcc 8.1.0
- Python 3.7.8
12.6: 2つの連結リスト(データは文字)を結合
C言語
#include <stdio.h>
#include <conio.h>
typedef struct list{
struct list *next;
char cData;
}List;
void printList(List *);
List *concatenate(List *, List *);
int main()
{
List a, b, c, d;
List *con;
printf("リスト1\n");
a.cData = 'X';
a.next = &b;
b.cData = 'Y';
b.next = NULL;
printList(&a);
printf("リスト2\n");
c.cData = 'Z';
c.next = &d;
d.cData = '!';
d.next = NULL;
printList(&c);
printf("連結後\n");
con = concatenate(&a, &c);
printList(con);
getch();
return 0;
}
void printList(List *headPtr)
{
while (headPtr != NULL)
{
printf("%c\n", headPtr -> cData);
headPtr = headPtr -> next;
}
}
List *concatenate(List *a, List *c)
{
List *headPtr;
headPtr = a;
while(a -> next != NULL)
{
a = a -> next;
}
a -> next = c;
return headPtr;
}
Python
12.7: 2つの順序リスト(データは整数)を結合
C言語
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
typedef struct list{
struct list *next;
int iData;
}List;
void printList(List *);
List *merge(List *, List *);
int main()
{
List a, b, c, d;
List *mer;
printf("リスト1\n");
a.iData = 100;
a.next = &b;
b.iData = 200;
b.next = NULL;
printList(&a);
printf("リスト2\n");
c.iData = 50;
c.next = &d;
d.iData = 300;
d.next = NULL;
printList(&c);
getch();
printf("併合後\n");
mer = merge(&a, &c);
printList(mer);
getch();
return 0;
}
void printList(List *headPtr)
{
while (headPtr != NULL)
{
printf("%d\n", headPtr -> iData);
headPtr = headPtr -> next;
}
}
List* merge(List* a, List* c)
{
List tentative;
List* tail = &tentative;
tentative.next = NULL;
while (a != NULL && c != NULL)
{
if (a -> iData <= c -> iData)
{
tail -> next = a;
a = a -> next;
}
else
{
tail -> next = c;
c = c -> next;
}
tail = tail -> next;
}
if (a != NULL)
{
tail -> next = a;
}
else
{
tail -> next = c;
}
return tentative.next;
}
Python
12.8: 25個の乱数を連結リストに昇順に挿入(各ノードの合計と浮動小数点平均も計算)
- 12.7で作った関数mergeを使うのも手
C言語
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// ノードの構造体を定義
struct Node {
int data;
struct Node* next;
};
// 新しいノードを作成する関数
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
fprintf(stderr, "メモリの確保に失敗しました。\n");
return NULL;
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// リストに昇順でノードを挿入する関数
int insertInOrder(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (newNode == NULL) {
return 0; // メモリの確保に失敗した場合
}
if (*head == NULL || (*head)->data >= data) {
newNode->next = *head;
*head = newNode;
} else {
struct Node* current = *head;
while (current->next != NULL && current->next->data < data) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
return 1;
}
// リストを表示する関数
void printList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
// リストのメモリを解放する関数
void freeList(struct Node* head) {
struct Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
}
int main() {
struct Node* head = NULL;
int sum = 0;
srand(time(0));
for (int i = 0; i < 25; i++) {
int randNum = rand() % 101; // 0から100の乱数を生成
if (insertInOrder(&head, randNum)) {
sum += randNum;
} else {
// メモリの確保に失敗した場合、メモリを解放して終了
freeList(head);
return 1;
}
}
float average = sum / 25.0;
printf("連結リスト (昇順):\n");
printList(head);
printf("ノードの値の合計: %d\n", sum);
printf("ノードの値の平均: %.2f\n", average);
// メモリの解放
freeList(head);
return 0;
}
Python
import random
# define node class
class Node:
def __init__(self, data):
self.data = data
self.next = None
# A function to insert nodes into a list in ascending order
def insert_in_order(head, data):
new_node = Node(data)
if head is None or head.data >= data:
new_node.next = head
return new_node
else:
current = head
while current.next is not None and current.next.data < data:
current = current.next
new_node.next = current.next
current.next = new_node
return head
# A function to print list
def print_list(head):
current = head
while current is not None:
print(f'{current.data} -> ', end='')
current = current.next
print('None')
# A function to free the memory of a list
def free_list(head):
while head is not None:
temp = head
head = head.next
del temp
def main():
head = None
total_sum = 0
for _ in range(25):
rand_num = random.randint(0, 100)
head = insert_in_order(head, rand_num)
total_sum += rand_num
average = total_sum / 25.0
print('連結リスト (昇順):')
print_list(head)
print(f'ノードの値の合計: {total_sum}')
print(f'ノードの値の平均: {average:.2f}')
# free memory
free_list(head)
if __name__ == '__main__':
main()
12.9: 10個のノードからなる連結リスト(データは文字)を生成し、最初のリストとは逆の順序で2つ目のリストを生成
C言語
#include <stdio.h>
#include <stdlib.h>
// ノードの構造体を定義
struct Node {
char data;
struct Node* next;
};
// 新しいノードを作成する関数
struct Node* createNode(char data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// リストの末尾にノードを追加する関数
void appendNode(struct Node** head, char data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
}
// リストを表示する関数
void printList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%c -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
// リストを逆順にする関数
struct Node* reverseList(struct Node* head) {
struct Node* prev = NULL;
struct Node* current = head;
struct Node* next = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}
// メモリを解放する関数
void freeList(struct Node* head) {
struct Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
}
int main() {
// 連結リストを生成
struct Node* head = NULL;
char data[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'};
for (int i = 0; i < 10; i++) {
appendNode(&head, data[i]);
}
printf("元のリスト:\n");
printList(head);
// 逆順のリストを生成
struct Node* reversedHead = reverseList(head);
printf("逆順のリスト:\n");
printList(reversedHead);
// メモリの解放
freeList(reversedHead);
return 0;
}
Python
12.10: 入力された1行のテキストをスタックを使って逆向きにプリント
C言語
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
typedef struct stackNode{
char data;
struct stackNode *nextPtr;
}StackNode;
void push(StackNode **, char);
char pop(StackNode **);
int main()
{
StackNode *stackPtr;
char string[100];
int i = 0;
printf("文字列を入力してください\n");
fgets(string, sizeof(string), stdin);
while (string[i] != '\n' && string[i] != '\0')
{
push(&stackPtr, string[i]);
i++;
}
while (i > 0)
{
printf("%c", pop(&stackPtr));
i--;
}
getch();
return 0;
}
void push(StackNode **topPtr, char info)
{
StackNode *newPtr;
newPtr = (StackNode *)malloc(sizeof(StackNode));
if (newPtr != NULL)
{
newPtr -> data = info;
newPtr -> nextPtr = *topPtr;
*topPtr = newPtr;
}
else
{
printf("空きメモリがないので %d は挿入できません\n");
}
}
char pop(StackNode **topPtr)
{
StackNode *tempPtr;
char popValue;
tempPtr = *topPtr;
popValue = (*topPtr) -> data;
*topPtr = (*topPtr) -> nextPtr;
free(tempPtr);
return popValue;
}
Python
12.11: スタックを使い文字列が回文(前から見ても後ろから見ても同じスペルの文字列)か判定
- スペースや句点は無視
C言語
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define SIZE 100
typedef struct stackNode{
char data;
struct stackNode *nextPtr;
} StackNode;
void push(StackNode **, char);
char pop(StackNode **);
void removePunctuation(char *, char *);
int main() {
StackNode *stackPtr = NULL;
char string[SIZE];
char cleanedString[SIZE];
char reverse[SIZE];
int i;
int count = 0;
printf("回文であるかを判定します\n");
printf("文字列を入力してください\n");
gets(string);
printf("入力文字列: %s\n", string);
// 句読点を取り除いた文字列を作成
removePunctuation(string, cleanedString);
printf("句読点を取り除いた文字列: %s\n", cleanedString);
// スタックに文字列をつめていく
for (i = 0; cleanedString[i] != '\0' && cleanedString[i] != '\n'; i++) {
push(&stackPtr, cleanedString[i]);
count++;
}
// スタックから文字列を取り出す
for (i = 0; i < count; i++) {
reverse[i] = pop(&stackPtr);
}
reverse[i] = '\0';
printf("逆転した文字列: %s\n", reverse);
// 結果表示
if (strcmp(cleanedString, reverse) == 0) {
printf("回文です\n");
} else {
printf("回文ではありません\n");
}
getch();
return 0;
}
void push(StackNode **topPtr, char info) {
StackNode *newPtr = (StackNode *)malloc(sizeof(StackNode));
if (newPtr != NULL) {
newPtr->data = info;
newPtr->nextPtr = *topPtr;
*topPtr = newPtr;
} else {
printf("空きメモリがないので %d は挿入できません\n", info);
}
}
char pop(StackNode **topPtr) {
StackNode *tempPtr;
char popValue;
tempPtr = *topPtr;
popValue = (*topPtr)->data;
*topPtr = (*topPtr)->nextPtr;
free(tempPtr);
return popValue;
}
void removePunctuation(char *source, char *destination) {
int j = 0;
for (int i = 0; source[i] != '\0'; i++) {
if (isalnum(source[i])) {
destination[j++] = source[i];
}
}
destination[j] = '\0';
}
Python
12.12: 1桁の整数を使った中置算術式を後置記法に変換
- 中置: (6 + 2) * 5 - 8 / 4
- 後置: 6 2 + 5 * 8 4 / -
C言語
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
// スタックのノードを表す構造体
typedef struct stackNode{
char data;
struct stackNode *nextPtr;
}StackNode;
// d
void push(StackNode **, char);
// e
char pop(StackNode **);
// b
int isOperator(char);
// f
char stackTop(StackNode **);
// h
void printStack(StackNode **);
// c
int precedence(char, char);
// g スタックが空であるかを判定する関数
int isEmpty(StackNode **);
// a
void convertToPostfix(char [], char []);
int main()
{
char infix[100];
char postfix[100];
printf("中間式を入力してください\n");
fgets(infix, sizeof(infix), stdin);
convertToPostfix(infix, postfix);
printf("%s\n", postfix);
getch();
return 0;
}
void push(StackNode **topPtr, char info)
{
StackNode *newPtr;
newPtr = (StackNode *)malloc(sizeof(StackNode));
if (newPtr != NULL)
{
newPtr -> data = info;
newPtr -> nextPtr = *topPtr;
*topPtr = newPtr;
}
else
{
printf("空きメモリがないので %d は挿入できません\n");
}
}
char pop(StackNode **topPtr)
{
StackNode *tempPtr;
char popValue;
tempPtr = *topPtr;
popValue = (*topPtr) -> data;
*topPtr = (*topPtr) -> nextPtr;
free(tempPtr);
return popValue;
}
int isOperator(char c)
{
if (c == '+')
{
return 1;
}
else if (c == '-')
{
return 1;
}
else if (c == '*')
{
return 1;
}
else if (c == '/')
{
return 1;
}
else if (c == '%')
{
return 1;
}
else if (c == '^')
{
return 1;
}
return 0;
}
// スタックが空かは呼び出し側で対応
char stackTop(StackNode **topPtr)
{
return(*topPtr) -> data;
}
// スタックが空であるかを判定する関数
// 引数: topPtr(スタックの先頭位置のアドレスを格納するポインタへのポインタ
// 戻り値: 1 空である 0 空でない
int isEmpty(StackNode **topPtr)
{
if (*topPtr == NULL)
{
return 1;
}
return 0;
}
void printStack(StackNode **topPtr)
{
StackNode *tmpPtr;
if (*topPtr == NULL)
{
printf("スタックは空ですn");
return;
}
// 先頭データを表示
printf("%c\n", (*topPtr) -> data);
tmpPtr = (*topPtr) -> nextPtr;
while (tmpPtr != NULL)
{
printf("%c\n", tmpPtr -> data);
tmpPtr = tmpPtr -> nextPtr;
}
getch();
}
int precedence(char op1, char op2)
{
static int level[58];
static int first = 1;
if (first == 1)
{
level[0] = 13; // %
level[5] = 13; // *
level[6] = 12; // +
level[8] = 12; // -
level[10] = 13; // /
level[57] = 7; // ^
first = 0;
}
if (level[op1 - '%'] < level[op2 - '%'])
{
return -1;
}
else if (level[op1 - '%'] == level[op2 - '%'])
{
return 0;
}
return 1;
}
void convertToPostfix(char infix[], char postfix[])
{
StackNode *stackPtr = NULL;
char c;
int now = 0;
int next = 0;
push(&stackPtr, '(');
infix[strlen(infix) - 1] = ')';
// スタックが空でない間
while (isEmpty(&stackPtr) == 0 && now < 100)
{
// 数字なら
if (isdigit(infix[now]))
{
postfix[next] = infix[now];
next++;
postfix[next] = ' ';
next++;
}
// 左括弧なら
else if (infix[now] == '(')
{
push(&stackPtr, infix[now]);
}
// 演算子なら
else if (isOperator(infix[now]))
{
// スタックに演算子があるなら
if (isOperator(stackTop(&stackPtr)))
{
c = stackTop(&stackPtr);
// 取り出したものが演算子でその演算子の優先度が,現在の演算子より
// 高いか等しい間
while (isOperator(c) && precedence(c, infix[now]) >= 0)
{
c = pop(&stackPtr);
postfix[next] = c;
next++;
postfix[next] = ' ';
next++;
c = stackTop(&stackPtr);
}
}
push(&stackPtr, infix[now]);
}
// 右括弧ならば
else if (infix[now] == ')')
{
// スタックの先頭が左括弧でない間
while (stackTop(&stackPtr) != '(')
{
c = pop(&stackPtr);
postfix[next] = c;
next++;
postfix[next] = ' ';
next++;
}
pop(&stackPtr);
}
// infixの次の要素へ
now++;
}
postfix[next] = '\0';
}
Python
12.13: 1桁の数字と演算子からなる後置算術式を評価
C言語
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define SIZE 100
#define DEBUG(x) x
// スタックのノードを表す構造体
typedef struct stackNode{
int data;
struct stackNode *nextPtr;
}StackNode;
void push(StackNode **, int);
char pop(StackNode **);
int isOperator(char);
int calculate(int, int, char);
int evaluatePostfixExpression(char *, int);
int main()
{
char postfix[100];
int result;
printf("後置式を入力してください\n");
fgets(postfix, sizeof(postfix), stdin);
DEBUG(printf("postfix %s\n", postfix));
// 空なら終了(fgets)
if (postfix[1] == '\0')
{
return 0;
}
result = evaluatePostfixExpression(postfix, 100);
printf("result %d\n", result);
getch();
return 0;
}
void push(StackNode **topPtr, int info)
{
StackNode *newPtr;
newPtr = (StackNode *)malloc(sizeof(StackNode));
if (newPtr != NULL)
{
newPtr -> data = info;
newPtr -> nextPtr = *topPtr;
*topPtr = newPtr;
}
else
{
printf("空きメモリがないので %d は挿入できません\n");
}
}
char pop(StackNode **topPtr)
{
StackNode *tempPtr;
char popValue;
tempPtr = *topPtr;
popValue = (*topPtr) -> data;
*topPtr = (*topPtr) -> nextPtr;
free(tempPtr);
return popValue;
}
int isOperator(char c)
{
if (c == '+')
{
return 1;
}
else if (c == '-')
{
return 1;
}
else if (c == '*')
{
return 1;
}
else if (c == '/')
{
return 1;
}
else if (c == '%')
{
return 1;
}
else if (c == '^')
{
return 1;
}
return 0;
}
int evaluatePostfixExpression(char * postfix, int size)
{
int now;
int x, y;
int num;
StackNode *stackPtr = NULL;
for (now = 0; postfix[now] != '\0' && now < size; now++)
{
// 数字なら
if (isdigit(postfix[now]))
{
push(&stackPtr, postfix[now] - '0');
}
// 演算子なら
else if (isOperator(postfix[now]))
{
x = pop(&stackPtr);
y = pop(&stackPtr);
push(&stackPtr, calculate(y, x, postfix[now]));
}
}
return pop(&stackPtr);
}
int calculate(int y, int x, char c)
{
if (c == '+')
{
return y + x;
}
else if (c == '-')
{
return y - x;
}
else if (c == '*')
{
return y * x;
}
else if (c == '/')
{
return y / x;
}
else if (c == '%')
{
return y % x;
}
else if (c == '^')
{
return y ^ x;
}
}
Python
12.14: 12.13の後置式評価プログラムをオペランドが2桁以上の整数でも処理できるように改造
C言語
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define SIZE 100
#define DEBUG(x) x
// スタックのノードを表す構造体
typedef struct stackNode{
int data;
struct stackNode *nextPtr;
}StackNode;
void push(StackNode **, int);
int pop(StackNode **);
int isOperator(char);
int evaluatePostfixExpression(char *, int);
int calculate(int, int, char);
int main()
{
char postfix[100];
int result;
printf("後置式を入力してください\n");
fgets(postfix, sizeof(postfix), stdin);
// 空なら終了(fgets)
if (postfix[1] == '\0')
{
return 0;
}
result = evaluatePostfixExpression(postfix, 100);
printf("result %d\n", result);
getch();
return 0;
}
void push(StackNode **topPtr, int info)
{
StackNode *newPtr;
newPtr = (StackNode *)malloc(sizeof(StackNode));
if (newPtr != NULL)
{
newPtr -> data = info;
newPtr -> nextPtr = *topPtr;
*topPtr = newPtr;
}
else
{
printf("空きメモリがないので %d は挿入できません\n");
}
}
int pop(StackNode **topPtr)
{
StackNode *tempPtr;
int popValue;
tempPtr = *topPtr;
popValue = (*topPtr) -> data;
*topPtr = (*topPtr) -> nextPtr;
free(tempPtr);
return popValue;
}
int isOperator(char c)
{
if (c == '+')
{
return 1;
}
else if (c == '-')
{
return 1;
}
else if (c == '*')
{
return 1;
}
else if (c == '/')
{
return 1;
}
else if (c == '%')
{
return 1;
}
else if (c == '^')
{
return 1;
}
return 0;
}
int evaluatePostfixExpression(char * postfix, int size)
{
int now;
int x, y;
int num;
StackNode *stackPtr = NULL;
for (now = 0; postfix[now] != '\0' && now < size; now++)
{
// 数字なら
if (isdigit(postfix[now]))
{
// 文字としての数値を整数値に変換する
for (num = 0; postfix[now] != ' '; now++)
{
num = num * 10 + (postfix[now] - '0');
}
push(&stackPtr, num);
}
// 演算子なら
else if (isOperator(postfix[now]))
{
x = pop(&stackPtr);
y = pop(&stackPtr);
push(&stackPtr, calculate(y, x, postfix[now]));
}
}
return pop(&stackPtr);
}
int calculate(int y, int x, char c)
{
if (c == '+')
{
return y + x;
}
else if (c == '-')
{
return y - x;
}
else if (c == '*')
{
return y * x;
}
else if (c == '/')
{
return y / x;
}
else if (c == '%')
{
return y % x;
}
else if (c == '^')
{
return y ^ x;
}
}
Python
12.15: スーパーマーケットのレジの行列をシミュレート
- 応用: 最適レジ数の導出(顧客の到着間隔、顧客のサービス時間、レジ設置予算などのパラメータのもと)
C言語
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <signal.h>
// デバッグ用
#define DEBUG(x) x
// 到着間隔
#define ARRIVE_INTERVAL 4
// キュー構造体
typedef struct queue{
int number; // 何人目の顧客であるか
int arriveTime; // レジに到着した時刻
struct queue *next;
}Queue;
// キューにデータを入れる関数
int enQueue(Queue **, Queue **, int, int);
// キューからデータを取り出す関数
int deQueue(Queue **, Queue **, int *);
// キューが空を調べる関数
int isEmpty(Queue *);
// キューの情報を表示
void printQueue(Queue *);
// キューのデータの個数を求める関数
int checkQueueNum(Queue *);
int main()
{
int nowTime; // スタートしてからの経過分
int number = 1; // 顧客の番号
int serviceTime; // 顧客のサービス時間
int nextArrivetime; // 次の顧客の到着時間
int serviceNum; // 現在サービスを受けている顧客の番号
int arriveTime; // その顧客がレジに到着した時間
int waitTime; // その顧客がサービスを受けるまでに待たされた時間
int maxWaittime = -1; // 最大何分待たされたか
int queueNum; // キューに何人待たされているか
int maxqueueNum = -1; // 最大何人待たされたか
Queue *headPtr = NULL; // キューの先頭を指すポインタ
Queue *tailPtr = NULL; // キューの最後尾を指すポインタ
srand(time(NULL));
// 最初の顧客が到着したことを表示
printf("%dさんが到着しました\n", number);
// 最初の顧客の到着時間を求める
nowTime = rand() % ARRIVE_INTERVAL + 1;
// 最初の顧客のサービス時間を決める
serviceTime = rand() % 4 + 1;
// 最初の顧客に対してサービスを開始する
serviceNum = 1;
printf("%dさんのサービスを開始します\n", serviceNum);
// 次の顧客の到着時間を求める
nextArrivetime = nowTime + (rand() % ARRIVE_INTERVAL + 1);
// 次に到着する顧客
number++;
// 720分間シュミレーションを行う
while (nowTime < 720)
{
// 次の顧客が到着したら
if (nowTime >= nextArrivetime)
{
// 顧客が到着したことを表示する
printf("%dさんが到着しました\n\n", number);
// その顧客をキューにつなぐ
if ((enQueue(&headPtr, &tailPtr, number, nowTime)) == -1)
{
fprintf(stderr, "メモリ領域の確保に失敗しました\n");
// ここに今までに確保したQueueの動的領域を解放する処理を書く
return -1;
}
// 次の顧客の到着時間を求める
nextArrivetime = nowTime + (rand() % ARRIVE_INTERVAL + 1);
// 次に到着する顧客
number++;
}
// 現在の顧客に対するサービスが終了したら
if (serviceTime <= 0)
{
// サービスが完了したことを表示する
printf("%dさんのサービスが完了しました\n\n", serviceNum);
// 顧客がいるならば
if (isEmpty(headPtr) == 0)
{
// 次の顧客をキューから取り出して,その顧客に対してサービスを開始する
serviceNum = deQueue(&headPtr, &tailPtr, &arriveTime);
printf("%dさんのサービスを開始します\n", serviceNum);
// 待たされた時間を計算
waitTime = nowTime - arriveTime;
DEBUG(printf("\n%dさんはサービスを受けるまで%d分待たされました\n\n", serviceNum, waitTime));
// 今までで最も待たされた時間ならば
if (waitTime > maxWaittime)
{
maxWaittime = waitTime;
}
// その顧客のサービス完了時刻を計算する
serviceTime = rand() % 4 + 1;
}
}
// 今現在何人レジに待たされているかを調べる
queueNum = checkQueueNum(headPtr);
// 今までで最もレジに人がいるならば
if (queueNum > maxqueueNum)
{
maxqueueNum = queueNum;
}
DEBUG(printf("時刻%d: \n", nowTime));
DEBUG(printQueue(headPtr));
// 1分経過
nowTime++;
serviceTime--;
}
printf("\n%d人到着しました\n\n", number - 1);
printf("\n最大%d分待たされました\n\n", maxWaittime);
printf("\n最大%d人レジで待たされました\n\n", maxqueueNum);
// ここに今までに確保したQueueの動的領域を解放する処理を書く
getch();
return 0;
}
// キューにデータを入れる関数
// 戻り値 -1以外 正常終了 -1 メモリ領域確保失敗
int enQueue(Queue **headPtr, Queue **tailPtr, int num, int time)
{
Queue *newPtr;
// メモリ領域の確保に失敗したならば
if ((newPtr = (Queue *)malloc(sizeof(Queue))) == NULL)
{
return -1;
}
// データの挿入
newPtr -> number = num;
newPtr -> next = NULL;
newPtr -> arriveTime = time;
// キューが空ならば
if (isEmpty(*headPtr))
{
// 新しく生成したノードを先頭に登録する
*headPtr = newPtr;
}
else
{
// 最後尾の次のノードとして登録する
(*tailPtr) -> next = newPtr;
}
// 最後尾を更新
*tailPtr = newPtr;
return 0;
}
// キューの情報を表示
void printQueue(Queue *currentPtr)
{
if (currentPtr == NULL)
{
printf("レジには誰もいません\n\n");
}
else
{
printf("サービス待ちの人:\n");
while (currentPtr != NULL)
{
printf("%d -> ", currentPtr -> number);
currentPtr = currentPtr -> next;
}
printf("NULL\n\n");
}
}
// キューが空を調べる関数
// 戻り値 0以外 空である 0 空でない
int isEmpty(Queue *headPtr)
{
return headPtr == NULL;
}
// キューからデータを取り出す関数
int deQueue(Queue **headPtr, Queue **tailPtr, int *time)
{
Queue *tempPtr;
int value;
value = (*headPtr) -> number;
*time = (*headPtr) -> arriveTime;
tempPtr = *headPtr;
*headPtr = (*headPtr) -> next;
if (*headPtr == NULL)
{
*tailPtr = NULL;
}
free(tempPtr);
return value;
}
// キューのデータの個数を求める関数
// 戻り値 キューに格納されているデータの個数
int checkQueueNum(Queue * currentPtr)
{
int num = 0;
if (currentPtr == NULL)
{
return 0;
}
else
{
while (currentPtr != NULL)
{
num++;
currentPtr = currentPtr -> next;
}
}
return num;
}
Python
from collections import deque
import random
import time
MAX_ARRIVE_INTERVAL = 4 # maximum arrival interval
customerIdRegister = deque([]) # customers at the register
arriveTimeRegister = deque([]) # customer's arrival time at the register
def main():
# Seed the random number generator with the current time
random.seed(time.time())
# first customer
customerId = 1
# caliculate arrival time of first customer
nowTime = random.randint(1, MAX_ARRIVE_INTERVAL)
firstTime = nowTime
# first customer arrives at the register
print("時刻 %d" % (firstTime))
print("%dさんが到着しました" % (customerId))
# caliculate service time of first customer
serviceTime = random.randint(1, 4)
# start serving first customer
customerIdBeingServed = 1
print("%dさんのサービスを開始します サービス時間は%dです" % (customerIdBeingServed, serviceTime))
# next arrival customer
customerId = customerId + 1
# caliculate arrival time of next customer
nextArrivetime = nowTime + random.randint(1, MAX_ARRIVE_INTERVAL)
# initialize the maximum number of minutes someone have to wait
maxServiceWaitTime = -1
# initialize the maximum number of people in the register
maxPeopleAtRegister = -1
# run a 720 minute simulation(starting point 0)
while nowTime < 30: # <=720:
if nowTime != firstTime:
print("時刻 %d" % (nowTime))
# if the next customer arrives
if nowTime >= nextArrivetime:
# some customer arrives at the register
print("%dさんが到着しました" % (customerId))
# register the customer at the register
customerIdRegister.append(customerId)
arriveTimeRegister.append(nowTime)
# caliculate arrival time of next customer
nextArrivetime = nowTime + random.randint(1, MAX_ARRIVE_INTERVAL)
# Next arrival customer
customerId = customerId + 1
# if the current customer service ends
if serviceTime <= 0:
# display the service is complete
if serviceTime == 0:
print("%dさんのサービスが完了しました" % (customerIdBeingServed))
# if customer is at the register
if len(customerIdRegister) != 0:
# retrive from register and start serving the customer
customerIdBeingServed = customerIdRegister.popleft()
arriveTime = arriveTimeRegister.popleft()
# calculate the time spent waiting for service
serviceWaitTime = nowTime - arriveTime
print("%dさんはサービスを受けるまで%d分待たされました" % (customerIdBeingServed, serviceWaitTime))
# the longest wait ever for service
if serviceWaitTime > maxServiceWaitTime:
maxServiceWaitTime = serviceWaitTime
# caliculate service time of the customer
serviceTime = random.randint(1, 4)
print("%dさんのサービスを開始します サービス時間は%dです" % (customerIdBeingServed, serviceTime))
# find out how many people are currently waiting at the register
peopleAtRegister = len(customerIdRegister)
# if there are more people at the register than ever
if peopleAtRegister > maxPeopleAtRegister:
maxPeopleAtRegister = peopleAtRegister
print(customerIdRegister)
print("")
# one minute passed
nowTime = nowTime + 1
serviceTime = serviceTime - 1
print("")
print("%d人到着しました" % (customerId - 1))
print("最大%d分待たされました" % (maxServiceWaitTime))
print("最大%d人レジで待たされました" % (maxPeopleAtRegister))
if __name__ == '__main__':
main()
Python版: 実行結果
時刻 3
1さんが到着しました
1さんのサービスを開始します サービス時間は2です
deque([])
時刻 4
2さんが到着しました
deque([2])
時刻 5
1さんのサービスが完了しました
2さんはサービスを受けるまで1分待たされました
2さんのサービスを開始します サービス時間は2です
deque([])
時刻 6
3さんが到着しました
deque([3])
時刻 7
2さんのサービスが完了しました
3さんはサービスを受けるまで1分待たされました
3さんのサービスを開始します サービス時間は2です
deque([])
時刻 8
deque([])
時刻 9
4さんが到着しました
3さんのサービスが完了しました
4さんはサービスを受けるまで0分待たされました
4さんのサービスを開始します サービス時間は4です
deque([])
時刻 10
5さんが到着しました
deque([5])
時刻 11
6さんが到着しました
deque([5, 6])
時刻 12
deque([5, 6])
時刻 13
7さんが到着しました
4さんのサービスが完了しました
5さんはサービスを受けるまで3分待たされました
5さんのサービスを開始します サービス時間は1です
deque([6, 7])
時刻 14
8さんが到着しました
5さんのサービスが完了しました
6さんはサービスを受けるまで3分待たされました
6さんのサービスを開始します サービス時間は3です
deque([7, 8])
時刻 15
9さんが到着しました
deque([7, 8, 9])
時刻 16
deque([7, 8, 9])
時刻 17
10さんが到着しました
6さんのサービスが完了しました
7さんはサービスを受けるまで4分待たされました
7さんのサービスを開始します サービス時間は4です
deque([8, 9, 10])
時刻 18
deque([8, 9, 10])
時刻 19
deque([8, 9, 10])
時刻 20
deque([8, 9, 10])
時刻 21
11さんが到着しました
7さんのサービスが完了しました
8さんはサービスを受けるまで7分待たされました
8さんのサービスを開始します サービス時間は1です
deque([9, 10, 11])
時刻 22
12さんが到着しました
8さんのサービスが完了しました
9さんはサービスを受けるまで7分待たされました
9さんのサービスを開始します サービス時間は3です
deque([10, 11, 12])
時刻 23
deque([10, 11, 12])
時刻 24
deque([10, 11, 12])
時刻 25
13さんが到着しました
9さんのサービスが完了しました
10さんはサービスを受けるまで8分待たされました
10さんのサービスを開始します サービス時間は3です
deque([11, 12, 13])
時刻 26
deque([11, 12, 13])
時刻 27
deque([11, 12, 13])
時刻 28
14さんが到着しました
10さんのサービスが完了しました
11さんはサービスを受けるまで7分待たされました
11さんのサービスを開始します サービス時間は1です
deque([12, 13, 14])
時刻 29
11さんのサービスが完了しました
12さんはサービスを受けるまで7分待たされました
12さんのサービスを開始します サービス時間は1です
deque([13, 14])
14人到着しました
最大8分待たされました
最大3人レジで待たされました
12.16: リスト12.7(P465)のプログラムを重複値を含む二分木もなぞれるように変更
C言語
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <ctype.h>
#define SIZE 7
typedef struct treeNode{
struct treeNode *leftPtr;
int data;
struct treeNode *rightPtr;
}TreeNode;
void insertNode(TreeNode **, int);
void inOrder(TreeNode *);
void preOrder(TreeNode *);
void postOrder(TreeNode *);
int main()
{
int i, item;
TreeNode *rootPtr = NULL;
srand(time(NULL));
printf("2分木に挿入する値:\n");
for (i = 1; i <= SIZE; i++)
{
item = rand() % 15;
printf("%3d", item);
insertNode(&rootPtr, item);
}
printf("\n\n先順探索の結果:\n");
preOrder(rootPtr);
printf("\n\n中順探索の結果:\n");
inOrder(rootPtr);
printf("\n\n後順探索の結果:\n");
postOrder(rootPtr);
getch();
return 0;
}
void insertNode(TreeNode **treePtr, int value)
{
if (*treePtr == NULL)
{
*treePtr = (TreeNode *)malloc(sizeof(TreeNode));
if (*treePtr != NULL)
{
(*treePtr) -> data = value;
(*treePtr) -> leftPtr = NULL;
(*treePtr) -> rightPtr = NULL;
}
else
{
printf("空きメモリがないため %d は挿入できません\n", value);
}
}
else if (value < (*treePtr) -> data)
{
insertNode(&((*treePtr) -> leftPtr), value);
}
else if (value > (*treePtr) -> data)
{
insertNode(&((*treePtr) -> rightPtr), value);
}
// 同じ値だったら木の左側にデータを挿入
else
{
insertNode(&((*treePtr) -> leftPtr), value);
}
}
void inOrder(TreeNode *treePtr)
{
if (treePtr != NULL)
{
inOrder(treePtr -> leftPtr);
printf("%3d", treePtr -> data);
inOrder(treePtr -> rightPtr);
}
}
void preOrder(TreeNode *treePtr)
{
if (treePtr != NULL)
{
printf("%3d", treePtr -> data);
preOrder(treePtr -> leftPtr);
preOrder(treePtr -> rightPtr);
}
}
void postOrder(TreeNode *treePtr)
{
if (treePtr != NULL)
{
postOrder(treePtr -> leftPtr);
postOrder(treePtr -> rightPtr);
printf("%3d", treePtr -> data);
}
}
C言語版 実行結果
2分木に挿入する値:
1 9 6 0 4 0 6
先順探索の結果:
1 0 0 9 6 4 6
中順探索の結果:
0 0 1 4 6 6 9
後順探索の結果:
0 0 6 4 6 9 1
- 先順探索
- 中順探索
- 後順探索
Python
12.17: テキストを1行入力して単語に分解、それらの単語を二分探索木に挿入、それを中順走査、先順走査、後順走査でプリント
C言語
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 100
// 二分探索木のノード定義
typedef struct TreeNode {
char *data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// ノードの作成
TreeNode* createNode(char *data) {
TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
newNode->data = strdup(data);
newNode->left = newNode->right = NULL;
return newNode;
}
// 二分探索木に挿入
TreeNode* insert(TreeNode *root, char *data) {
if (root == NULL) {
return createNode(data);
}
if (strcmp(data, root->data) < 0) {
root->left = insert(root->left, data);
} else if (strcmp(data, root->data) > 0) {
root->right = insert(root->right, data);
}
return root;
}
// 中順走査
void inorderTraversal(TreeNode *root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%s ", root->data);
inorderTraversal(root->right);
}
}
// 先順走査
void preorderTraversal(TreeNode *root) {
if (root != NULL) {
printf("%s ", root->data);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
// 後順走査
void postorderTraversal(TreeNode *root) {
if (root != NULL) {
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%s ", root->data);
}
}
// メモリ解放
void freeTree(TreeNode *root) {
if (root != NULL) {
freeTree(root->left);
freeTree(root->right);
free(root->data);
free(root);
}
}
int main() {
char input[SIZE];
char *token;
TreeNode *root = NULL;
printf("文字列を入力してください:\n");
fgets(input, SIZE, stdin);
// 改行を削除
input[strcspn(input, "\n")] = '\0';
// トークンに分解
token = strtok(input, " ");
while (token != NULL) {
root = insert(root, token);
token = strtok(NULL, " ");
}
// 中順走査
printf("中順走査: ");
inorderTraversal(root);
printf("\n");
// 先順走査
printf("先順走査: ");
preorderTraversal(root);
printf("\n");
// 後順走査
printf("後順走査: ");
postorderTraversal(root);
printf("\n");
// メモリ解放
freeTree(root);
return 0;
}
Python
12.18: 1次元配列だけを使い重複値を回避する方法 + 1次元配列・二分探索木による重複値回避の性能比較
- 回避方法
- 1次元配列の先頭から最後尾まで一つずつ値を比較
- 性能比較
- 共通
- 重複値はひとつだけ存在
- データ数$n$($>=2$)
- 2分探索木
- 平衡型(バランスがとれている)
- []: ガウス記号(ある値についてそれを超えない最大の整数値)
- 1次元配列
- 重複値は配列内のどこかに等確率($\frac{1}{n}$)で存在
- 平均比較回数(比較回数の期待値)$ = \frac{1}{n} \times 1 + \frac{1}{n} \times 2 + \frac{1}{n} \times 3 + \frac{1}{n} \times 4 ... = \frac{1 + 2 + 3 + 4 ...}{n} = \frac{n(n+1)/2}{n}$
- 共通
| 1次元配列 | 二分探索木 | |
|---|---|---|
| 最小比較回数 | 1 | 1 |
| 平均比較回数 | $\frac{n+1}{2}$ | $[log_{2}{n}]$ |
| 最大比較回数 | $n$ | $[log_{2}{n}]$+1 |
12.19: 二分木を受け取り、それのレベル数を決定
C言語
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
typedef struct TreeNode {
int value;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
int depth(TreeNode* node) {
if (node == NULL) {
return 0;
} else {
int left_depth = depth(node->left);
int right_depth = depth(node->right);
return (left_depth > right_depth) ? left_depth + 1 : right_depth + 1;
}
}
int main() {
// 例
// 1
// / \
// 2 3
// / \
// 4 5
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->value = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->value = 2;
root->left->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->left->value = 4;
root->left->left->left = NULL; // 葉ノードにNULLを代入
root->left->left->right = NULL; // 葉ノードにNULLを代入
root->left->right = (TreeNode*)malloc(sizeof(TreeNode));
root->left->right->value = 5;
root->left->right->left = NULL; // 葉ノードにNULLを代入
root->left->right->right = NULL; // 葉ノードにNULLを代入
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->value = 3;
root->right->left = NULL; // 葉ノードにNULLを代入
root->right->right = NULL; // 葉ノードにNULLを代入
printf("深さ: %d\n", depth(root)); // 出力: 3
getch();
// メモリ解放
free(root->left->right);
free(root->left->left);
free(root->left);
free(root->right);
free(root);
return 0;
}
Python
12.20: 連結リスト(要素は整数でソートされている)のデータ項目を逆の順序で再帰的に出力
C言語
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
// ノードの定義
typedef struct Node {
int data;
struct Node* next;
} Node;
// ノードを作成するヘルパー関数
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// ソートされた位置にノードを挿入する関数
void insertSorted(Node** head, int data) {
Node* newNode = createNode(data);
// ヘッドがNULLの場合、またはヘッドのデータが新しいノードのデータより大きい場合
if (*head == NULL || (*head)->data >= data) {
newNode->next = *head;
*head = newNode;
} else {
// 適切な位置を見つける
Node* current = *head;
while (current->next != NULL && current->next->data < data) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
}
// 逆順に連結リストを出力する再帰関数
void printListBackwards(Node* node) {
if (node == NULL) return;
printListBackwards(node->next);
printf("%d ", node->data);
}
int main() {
// ソートされた連結リストを生成するためのヘッドノード
Node* head = NULL;
// 挿入するデータの配列
int arr[] = {3, 1, 4, 2, 5};
int n = sizeof(arr) / sizeof(arr[0]);
// データを挿入してソートされた連結リストを生成
for (int i = 0; i < n; i++) {
insertSorted(&head, arr[i]);
}
// 逆順に連結リストを出力
printListBackwards(head);
getch();
return 0;
}
Python
12.21: リストを再帰的に探索
C言語
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
// 連結リストのノードを定義
struct Node {
int data;
struct Node* next;
};
// 新しいノードを作成する関数
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 連結リストにノードを追加する関数
void appendNode(struct Node** headRef, int data) {
struct Node* newNode = createNode(data);
if (*headRef == NULL) {
*headRef = newNode;
return;
}
struct Node* temp = *headRef;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
// 再帰的に指定された値を連結リストから探し出す関数
struct Node* searchList(struct Node* head, int target) {
if (head == NULL) {
return NULL; // 見つからなかった場合
}
if (head->data == target) {
return head; // 見つかった場合
}
return searchList(head->next, target);
}
// メイン関数
int main() {
struct Node* head = NULL;
int n, value, target;
printf("連結リストのノード数を入力してください: ");
scanf("%d", &n);
for (int i = 0; i < n; i++) {
printf("ノード %d の値を入力してください: ", i + 1);
scanf("%d", &value);
appendNode(&head, value);
}
printf("検索したい値を入力してください: ");
scanf("%d", &target);
struct Node* result = searchList(head, target);
if (result != NULL) {
printf("値 %d が見つかりました: アドレス %p\n", result->data, (void*)result);
} else {
printf("値 %d は見つかりませんでした。\n", target);
}
// メモリ解放
struct Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
getch();
return 0;
}
Python
12.22: 二分木からデータを削除
- 書籍で指定されたアルゴリズムに非従順
C言語
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
typedef struct TreeNode {
int data;
struct TreeNode* leftPtr;
struct TreeNode* rightPtr;
} TreeNode;
void insertNode(TreeNode **, int);
void outputTree(TreeNode*, int);
void inorderTraversal(TreeNode *);
void preorderTraversal(TreeNode *);
void postorderTraversal(TreeNode *);
TreeNode* deleteNode(TreeNode*, int, int *);
TreeNode* findMax(TreeNode*);
TreeNode* findMax(TreeNode* root) {
while (root->rightPtr != NULL) {
root = root->rightPtr;
}
return root;
}
TreeNode* deleteNode(TreeNode* root, int data, int* found) {
if (root == NULL) {
return root;
}
if (data < root->data) {
root->leftPtr = deleteNode(root->leftPtr, data, found);
} else if (data > root->data) {
root->rightPtr = deleteNode(root->rightPtr, data, found);
} else {
// ノードが見つかった場合
*found = 1;
if (root->leftPtr == NULL) {
TreeNode* temp = root->rightPtr;
free(root);
return temp;
} else if (root->rightPtr == NULL) {
TreeNode* temp = root->leftPtr;
free(root);
return temp;
}
// 両方の子ノードがある場合
TreeNode* temp = findMax(root->leftPtr);
root->data = temp->data;
root->leftPtr = deleteNode(root->leftPtr, temp->data, found);
}
return root;
}
void insertNode(TreeNode** root, int data) {
if (*root == NULL) {
*root = (TreeNode*)malloc(sizeof(TreeNode));
(*root)->data = data;
(*root)->leftPtr = NULL;
(*root)->rightPtr = NULL;
} else if (data < (*root)->data) {
insertNode(&(*root)->leftPtr, data);
} else {
insertNode(&(*root)->rightPtr, data);
}
}
void printTree(TreeNode* root) {
if (root != NULL) {
printTree(root->leftPtr);
printf("%d ", root->data);
printTree(root->rightPtr);
}
}
// 二分木を目に見える形でプリントする関数
void outputTree(TreeNode* root, int totalSpaces) {
if (root == NULL)
return;
// 右のサブツリーをプリント
outputTree(root->rightPtr, totalSpaces + 5);
// 現在のノードをプリント
printf("\n");
for (int i = 1; i < totalSpaces; i++)
printf(" ");
printf("%d(%p)\n", root->data, (void *)root);
// 左のサブツリーをプリント
outputTree(root->leftPtr, totalSpaces + 5);
}
// 中順走査
void inorderTraversal(TreeNode *root) {
if (root != NULL) {
inorderTraversal(root->leftPtr);
printf("%d ", root->data);
inorderTraversal(root->rightPtr);
}
}
// 先順走査
void preorderTraversal(TreeNode *root) {
if (root != NULL) {
printf("%d ", root->data);
preorderTraversal(root->leftPtr);
preorderTraversal(root->rightPtr);
}
}
// 後順走査
void postorderTraversal(TreeNode *root) {
if (root != NULL) {
postorderTraversal(root->leftPtr);
postorderTraversal(root->rightPtr);
printf("%d ", root->data);
}
}
int main() {
TreeNode* root = NULL;
int eraseData;
int found = 0;
int values[] = {9, 3, 7, 2, 10};
int numValues = sizeof(values) / sizeof(values[0]);
for (int i = 0; i < numValues; i++) {
insertNode(&root, values[i]);
}
printf("ツリーの内容（削除前）: ");
outputTree(root, 0);
printf("\n");
printf("削除するデータを入力して下さい\n");
scanf("%d", &eraseData);
root = deleteNode(root, eraseData, &found);
if (!found) {
printf("\n指定された値はツリー内に存在しませんでした。\n\n");
}
printf("ツリーの内容（削除後）: ");
outputTree(root, 0);
printf("\n");
printf("\n先順走査\n");
preorderTraversal(root);
printf("\n中順走査\n");
inorderTraversal(root);
printf("\n後順走査\n");
postorderTraversal(root);
printf("\n");
getch();
return 0;
}
Python
12.23: 二分木を探索
C言語
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <ctype.h>
#define SIZE 5
typedef struct treeNode{
struct treeNode *leftPtr;
int data;
struct treeNode *rightPtr;
}TreeNode;
void insertNode(TreeNode **, int);
TreeNode *binaryTreeSearch(TreeNode *, int);
void outputTree(TreeNode*, int);
int main()
{
int i, item;
TreeNode *rootPtr = NULL;
TreeNode *tmpPtr;
int key;
srand(time(NULL));
printf("2分木に挿入する値:\n");
for (i = 1; i <= SIZE; i++)
{
item = rand() % 15;
printf("%3d", item);
insertNode(&rootPtr, item);
}
outputTree(rootPtr, 0);
printf("\nbinaryTreeSearch:\n");
printf("探索キーを入力してください: ");
scanf("%d", &key);
if ((tmpPtr = binaryTreeSearch(rootPtr, key)) == NULL)
{
printf("データはありませんでした\n");
}
else
{
printf("データ %d アドレス%p\n", tmpPtr -> data, (void *)tmpPtr);
}
getch();
return 0;
}
// 二分木を目に見える形でプリントする関数
void outputTree(TreeNode* root, int totalSpaces) {
if (root == NULL)
return;
// 増加する距離
int count = 5;
// 右のサブツリーをプリント
totalSpaces += count;
outputTree(root->rightPtr, totalSpaces);
// 現在のノードをプリント
printf("\n");
for (int i = count; i < totalSpaces; i++)
printf(" ");
printf("%d\n", root->data);
// 左のサブツリーをプリント
outputTree(root->leftPtr, totalSpaces);
}
void insertNode(TreeNode **treePtr, int value)
{
if (*treePtr == NULL)
{
*treePtr = (TreeNode *)malloc(sizeof(TreeNode));
if (*treePtr != NULL)
{
(*treePtr) -> data = value;
(*treePtr) -> leftPtr = NULL;
(*treePtr) -> rightPtr = NULL;
}
else
{
printf("空きメモリがないため %d は挿入できません\n", value);
}
}
else if (value < (*treePtr) -> data)
{
insertNode(&((*treePtr) -> leftPtr), value);
}
else if (value > (*treePtr) -> data)
{
insertNode(&((*treePtr) -> rightPtr), value);
}
// 同じ値だったら木の左側にデータを挿入
else
{
insertNode(&((*treePtr) -> leftPtr), value);
}
}
TreeNode *binaryTreeSearch(TreeNode *treePtr, int key)
{
if (treePtr == NULL)
{
return NULL;
}
// データが見つかったならば
if (treePtr -> data == key)
{
return treePtr;
}
// keyの値がデータより大きいならば
else if (treePtr -> data < key)
{
return binaryTreeSearch(treePtr -> rightPtr, key);
}
else
{
return binaryTreeSearch(treePtr -> leftPtr, key);
}
}
Python
12.24: 二分木のレベル順走査
C言語
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <conio.h>
struct treeNode {
int data;
struct treeNode *leftPtr;
struct treeNode *rightPtr;
};
typedef struct treeNode TREENODE;
typedef TREENODE* TREENODEPTR;
struct queueNode {
TREENODEPTR treeNode;
struct queueNode *nextPtr;
};
typedef struct queueNode QUEUENODE;
typedef QUEUENODE *QUEUENODEPTR;
void inOrder(TREENODEPTR);
void printQueue(QUEUENODEPTR);
bool isEmpty(QUEUENODEPTR);
void levelOrder(TREENODEPTR);
void dequeue(QUEUENODEPTR *, QUEUENODEPTR *);
void enqueue(QUEUENODEPTR *, QUEUENODEPTR *, TREENODEPTR);
void outputTree(TREENODEPTR, int);
// 中順走査
void inOrder(TREENODEPTR root) {
if (root != NULL) {
inOrder(root->leftPtr);
printf("%d ", root->data);
inOrder(root->rightPtr);
}
}
// キューにノードを追加する関数
void enqueue(QUEUENODEPTR *headPtr, QUEUENODEPTR *tailPtr, TREENODEPTR treeNode) {
QUEUENODEPTR newPtr;
newPtr = (QUEUENODEPTR)malloc(sizeof(QUEUENODE));
if (newPtr != NULL) {
newPtr->treeNode = treeNode;
newPtr->nextPtr = NULL;
if (isEmpty(*headPtr)) {
*headPtr = newPtr;
} else {
(*tailPtr)->nextPtr = newPtr;
}
*tailPtr = newPtr;
} else {
printf("空きメモリがないため、ノードは挿入できません。\n");
}
}
// キューからノードを取り出す関数
void dequeue(QUEUENODEPTR *headPtr, QUEUENODEPTR *tailPtr) {
QUEUENODEPTR tempPtr;
tempPtr = *headPtr;
*headPtr = (*headPtr)->nextPtr;
if (*headPtr == NULL) {
*tailPtr = NULL;
}
free(tempPtr);
}
// キューが空かどうかを確認する関数
bool isEmpty(QUEUENODEPTR headPtr) {
return headPtr == NULL;
}
// レベル順に二分木を走査する関数
void levelOrder(TREENODEPTR root) {
if (root == NULL) return;
QUEUENODEPTR queueFront = NULL;
QUEUENODEPTR queueRear = NULL;
// 1 ルートノードをキューに入れる
enqueue(&queueFront, &queueRear, root);
// 2 キューにノードが残っているあいだ
while (!isEmpty(queueFront)) {
// キューから次のノードを取り出す
TREENODEPTR currentNode = queueFront->treeNode;
dequeue(&queueFront, &queueRear);
// そのノード値をプリントする
printf("%d ", currentNode->data);
// そのノードの左の子へのポインタがNULLでないなら
if (currentNode->leftPtr != NULL) {
// 左の子ノードをキューに入れる
enqueue(&queueFront, &queueRear, currentNode->leftPtr);
}
// そのノードの右の子へのポインタがNULLでないなら
if (currentNode->rightPtr != NULL) {
// 右の子ノードをキューに入れる
enqueue(&queueFront, &queueRear, currentNode->rightPtr);
}
}
}
// 新しいノードを作成する関数
TREENODEPTR createNode(int data) {
TREENODEPTR newNode = (TREENODEPTR)malloc(sizeof(TREENODE));
if (newNode != NULL) {
newNode->data = data;
newNode->leftPtr = NULL;
newNode->rightPtr = NULL;
}
return newNode;
}
// 二分木を目に見える形でプリントする関数
void outputTree(TREENODEPTR root, int totalSpaces) {
if (root == NULL)
return;
// 右のサブツリーをプリント
outputTree(root->rightPtr, totalSpaces + 5);
// 現在のノードをプリント
printf("\n");
for (int i = 1; i < totalSpaces; i++)
printf(" ");
printf("%d(%p)\n", root->data, (void *)root);
// 左のサブツリーをプリント
outputTree(root->leftPtr, totalSpaces + 5);
}
int main() {
// 二分木を作成
TREENODEPTR root = createNode(1);
root->leftPtr = createNode(2);
root->rightPtr = createNode(3);
root->leftPtr->leftPtr = createNode(4);
root->leftPtr->rightPtr = createNode(5);
outputTree(root, 0);
printf("レベル順走査\n");
levelOrder(root);
printf("\n中順走査\n");
inOrder(root);
getch();
return 0;
}
Python
12.25: 二分木のプリント
C言語
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <ctype.h>
#define SIZE 5
typedef struct treeNode{
struct treeNode *leftPtr;
int data;
struct treeNode *rightPtr;
}TreeNode;
void insertNode(TreeNode **, int);
void outputTree(TreeNode*, int);
int main()
{
int i, item;
TreeNode *rootPtr = NULL;
TreeNode *tmpPtr;
int key;
srand(time(NULL));
printf("2分木に挿入する値:\n");
for (i = 1; i <= SIZE; i++)
{
item = rand() % 15;
printf("%3d", item);
insertNode(&rootPtr, item);
}
printf("\n");
outputTree(rootPtr, 0);
getch();
return 0;
}
// 二分木を目に見える形でプリントする関数
void outputTree(TreeNode* root, int totalSpaces) {
if (root == NULL)
return;
// 右のサブツリーをプリント
outputTree(root->rightPtr, totalSpaces + 5);
// 現在のノードをプリント
printf("\n");
for (int i = 1; i < totalSpaces; i++)
printf(" ");
printf("%d\n", root->data);
// 左のサブツリーをプリント
outputTree(root->leftPtr, totalSpaces + 5);
}
void insertNode(TreeNode **treePtr, int value)
{
if (*treePtr == NULL)
{
*treePtr = (TreeNode *)malloc(sizeof(TreeNode));
if (*treePtr != NULL)
{
(*treePtr) -> data = value;
(*treePtr) -> leftPtr = NULL;
(*treePtr) -> rightPtr = NULL;
}
else
{
printf("空きメモリがないため %d は挿入できません\n", value);
}
}
else if (value < (*treePtr) -> data)
{
insertNode(&((*treePtr) -> leftPtr), value);
}
else if (value > (*treePtr) -> data)
{
insertNode(&((*treePtr) -> rightPtr), value);
}
// 同じ値だったら木の左側にデータを挿入
else
{
insertNode(&((*treePtr) -> leftPtr), value);
}
}
Python
12.26: 簡易言語
- a
10 rem 整数を三個入力して,それらの平均を求める
15 input i
20 input j
25 input k
30 let l = (i + j + k) / 3
40 print l
50 end
- b
5 rem 番兵値は-9999
10 input j
15 if j == -9999 goto 90
20 let s = s + j
25 goto 10
90 print s
99 end
- c
10 rem 平均値を求める
40 input d
50 let c = d + c
60 let a = a + 1
80 if a < 7 goto 40
90 let c = c / 7
100 print c
110 end
- d
10 input x
20 input d
22 rem 今入力したデータが前のデータより小さいなら
30 if d <= e goto 50
40 rem 最大値を更新する
44 let e = d
50 let c = c + 1
60 if c < x goto 20
80 print e
90 end
- e
10 input d
20 if e < d goto 50
30 let e = d
50 let c = c + 1
60 if c < 10 goto 10
90 print e
99 end
- f
10 let e = 2
20 let d = d + e
30 let e = e + 2
40 if e < 32 goto 20
50 print d
60 end
- g
2 rem 10 15 は初期化
10 let e = 1
15 let d = 1
20 let d = e * d
30 let e = e + 2
40 if e < 11 goto 20
50 print d
60 end
12.27: コンパイラの制作
- a: 練習問題7.19で書いたSimpletronシミュレーターをユーザが指定したファイルからSMLコードを入力するように改造
C言語
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define DEBUG(name) { printf("\nDEBUG (" #name ") %d\n\n", name); }
// 入出力命令
#define READ 10
#define WRITE 11
// ロード/ストア命令
#define LOAD 20
#define STORE 21
// 算術演算命令
#define ADD 30
#define SUBTRACT 31
#define DIVIDE 32
#define MULTIPLY 33
// 分岐命令
#define BRANCH 40
#define BRANCHENG 41
#define BRANCHZERO 42
#define HALT 43
#define MEMORY_SIZE 100
// レジスタの内容とメモリの内容をダンプする関数
void printDumpToBoth(FILE *, int, int, int, int, int, int []);
int main() {
static int memory[MEMORY_SIZE]; // メモリモデル
int accumulator = 0; // レジスタ
int instructionCounter = 0; // 次に実行する命令が格納されたメモリ番地を格納
int instructionRegister; // 次に実行する命令
int operationCode; // 現在実行中の命令コードを格納
int operand = 0; // 現在の命令が作用するメモリ番地
int endFlag = 0;
char line[256];
FILE *inputFile = fopen("7.18a.c", "r");
FILE *outputFile = fopen("12.27aOutput.txt", "w");
if (inputFile == NULL || outputFile == NULL) {
fprintf(stderr, "ファイルを開くことができません。\n");
return 1;
}
while (fgets(line, sizeof(line), inputFile)) {
sscanf(line, "%*d %d", &memory[operand]);
if (memory[operand] == -9999) {
endFlag = 1;
memory[operand] = 0;
} else if (-9999 <= memory[operand] && memory[operand] <= 9999) {
operand++;
} else {
printf("\n不正な値です -9999 - 9999 までの値を入力してください\n\n");
}
}
fclose(inputFile);
if (operand <= 0) {
fprintf(outputFile, "命令はロードされていません\n");
printf("命令はロードされていません\n");
endFlag = 1;
} else {
fprintf(outputFile, "*** プログラムのロードが完了しました ***\n");
printf("*** プログラムのロードが完了しました ***\n");
fprintf(outputFile, "*** プログラムの実行を開始します ***\n");
printf("*** プログラムの実行を開始します ***\n");
endFlag = 0;
}
while (endFlag == 0) {
// 命令を取り出す
instructionRegister = memory[instructionCounter];
DEBUG(instructionRegister)
// 次の命令にカウンタを更新
instructionCounter++;
// 命令レジスタから命令コードを取り出す
operationCode = instructionRegister / 100;
// 命令レジスタからオペランドを取り出す
operand = instructionRegister % 100;
// 命令判別
switch (operationCode) {
// 入力命令
case READ:
fprintf(outputFile, "データを入力してください\n");
printf("データを入力してください\n");
scanf("%d", &memory[operand]);
fprintf(outputFile, "%d\n\n", memory[operand]);
break;
// 出力命令
case WRITE:
fprintf(outputFile, "%+5d\n", memory[operand]);
printf("%+5d\n", memory[operand]);
break;
// ロード命令
case LOAD:
accumulator = memory[operand];
break;
// ストア命令
case STORE:
memory[operand] = accumulator;
break;
// 加算命令
case ADD:
accumulator += memory[operand];
if (accumulator < -9999 || accumulator > 9999) {
fprintf(stderr, "*** 演算結果のオーバーフロー ***\n");
printf("*** 演算結果のオーバーフロー ***\n");
fprintf(stderr, "*** Simpletronは異常終了しました ***\n\n");
printf("*** Simpletronは異常終了しました ***\n\n");
printDumpToBoth(outputFile, accumulator, instructionCounter, instructionRegister, operationCode, operand, memory);
return -1;
}
break;
// 引き算命令
case SUBTRACT:
accumulator -= memory[operand];
if (accumulator < -9999 || accumulator > 9999) {
fprintf(stderr, "*** 演算結果のオーバーフロー ***\n");
printf("*** 演算結果のオーバーフロー ***\n");
fprintf(stderr, "*** Simpletronは異常終了しました ***\n\n");
printf("*** Simpletronは異常終了しました ***\n\n");
printDumpToBoth(outputFile, accumulator, instructionCounter, instructionRegister, operationCode, operand, memory);
return -1;
}
break;
// 割り算命令
case DIVIDE:
if (memory[operand] == 0) {
fprintf(stderr, "*** ゼロで割ろうとした ***\n");
printf("*** ゼロで割ろうとした ***\n");
fprintf(stderr, "*** Simpletronは異常終了しました ***\n\n");
printf("*** Simpletronは異常終了しました ***\n\n");
printDumpToBoth(outputFile, accumulator, instructionCounter, instructionRegister, operationCode, operand, memory);
return -1;
}
accumulator /= memory[operand];
break;
// 掛け算命令
case MULTIPLY:
accumulator *= memory[operand];
if (accumulator < -9999 || accumulator > 9999) {
fprintf(stderr, "*** 演算結果のオーバーフロー ***\n");
printf("*** 演算結果のオーバーフロー ***\n");
fprintf(stderr, "*** Simpletronは異常終了しました ***\n\n");
printf("*** Simpletronは異常終了しました ***\n\n");
printDumpToBoth(outputFile, accumulator, instructionCounter, instructionRegister, operationCode, operand, memory);
return -1;
}
break;
// 無条件分岐命令
case BRANCH:
instructionCounter = operand;
break;
// アキュムレータが負のとき分岐する命令
case BRANCHENG:
if (accumulator < 0) {
instructionCounter = operand;
}
break;
// アキュムレータが0のとき分岐する命令
case BRANCHZERO:
if (accumulator == 0) {
instructionCounter = operand;
}
break;
// 停止命令
case HALT:
endFlag = 1;
fprintf(outputFile, "*** Simpletronは終了しました ***\n\n");
printf("*** Simpletronは終了しました ***\n\n");
printDumpToBoth(outputFile, accumulator, instructionCounter, instructionRegister, operationCode, operand, memory);
break;
// 不正な命令
default:
fprintf(stderr, "*** 不正な命令コード ***\n");
printf("*** 不正な命令コード ***\n");
fprintf(stderr, "*** Simpletronは異常終了しました ***\n\n");
printf("*** Simpletronは異常終了しました ***\n\n");
printDumpToBoth(outputFile, accumulator, instructionCounter, instructionRegister, operationCode, operand, memory);
return -1;
}
}
fclose(outputFile);
return 0;
}
// レジスタの内容とメモリの内容をダンプする関数
void printDumpToBoth(FILE *outputFile, int accu, int instructionC, int instructionR, int operation, int operand, int m[]) {
int i, j;
fprintf(outputFile, "レジスタ:\n");
printf("レジスタ:\n");
fprintf(outputFile, "アキュムレータ %+05d\n", accu);
printf("アキュムレータ %+05d\n", accu);
fprintf(outputFile, "命令カウンタ %02d\n", instructionC);
printf("命令カウンタ %02d\n", instructionC);
fprintf(outputFile, "命令レジスタ %+05d\n", instructionR);
printf("命令レジスタ %+05d\n", instructionR);
fprintf(outputFile, "命令コード %02d\n", operation);
printf("命令コード %02d\n", operation);
fprintf(outputFile, "オペランド %02d\n\n", operand);
printf("オペランド %02d\n\n", operand);
fprintf(outputFile, "メモリ:\n");
printf("メモリ:\n");
fprintf(outputFile, " ");
printf(" ");
for (i = 0; i < 10; i++) {
fprintf(outputFile, "%5d ", i);
printf("%5d ", i);
}
fprintf(outputFile, "\n");
printf("\n");
for (i = 0; i < 100; i += 10) {
fprintf(outputFile, "%2d ", i);
printf("%2d ", i);
for (j = i; j < i + 10; j++) {
fprintf(outputFile, "%+05d ", m[j]);
printf("%+05d ", m[j]);
}
fprintf(outputFile, "\n");
printf("\n");
}
}
Python
- b: 練習問題12.12の中置式-後置式変換アルゴリズムを複数桁の整数オペランドと1文字の変数名オペランドを処理できるように改良
C言語
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
// スタックのノードを表す構造体
typedef struct stackNode {
char data[10]; // 文字列データを格納
struct stackNode *nextPtr;
} StackNode;
// プロトタイプ宣言
void push(StackNode **, char *);
char *pop(StackNode **);
int isOperator(char);
char *stackTop(StackNode **);
int isEmpty(StackNode **);
void convertToPostfix(char [], char []);
int precedence(char, char);
// main関数
int main() {
char infix[100];
char postfix[100] = ""; // 初期化する
printf("中間式を入力してください\n");
fgets(infix, sizeof(infix), stdin);
convertToPostfix(infix, postfix);
printf("後置式: %s\n", postfix);
return 0;
}
// スタックにプッシュする関数
void push(StackNode **topPtr, char *info) {
StackNode *newPtr = (StackNode *)malloc(sizeof(StackNode));
if (newPtr != NULL) {
strcpy(newPtr->data, info);
newPtr->nextPtr = *topPtr;
*topPtr = newPtr;
} else {
printf("空きメモリがないので %s は挿入できません\n", info);
}
}
// スタックからポップする関数
char *pop(StackNode **topPtr) {
StackNode *tempPtr;
char *popValue = (char *)malloc(10 * sizeof(char));
tempPtr = *topPtr;
strcpy(popValue, (*topPtr)->data);
*topPtr = (*topPtr)->nextPtr;
free(tempPtr);
return popValue;
}
// 演算子かどうかを判定する関数
int isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/' || c == '%' || c == '^';
}
// スタックのトップを取得する関数
char *stackTop(StackNode **topPtr) {
return (*topPtr)->data;
}
// スタックが空であるかを判定する関数
int isEmpty(StackNode **topPtr) {
return *topPtr == NULL;
}
// 演算子の優先順位を判定する関数
int precedence(char op1, char op2) {
if (op1 == '*' || op1 == '/' || op1 == '%') {
return (op2 == '+' || op2 == '-') ? 1 : 0;
} else {
return (op2 == '+' || op2 == '-') ? 0 : -1;
}
}
// 中置式を後置式に変換する関数
void convertToPostfix(char infix[], char postfix[]) {
StackNode *stackPtr = NULL;
char token[10];
int i = 0, j = 0;
int wasOperator = 1; // 1: 次は減算演算子がこない(負の符号) 0: 次は減算演算子がくる
push(&stackPtr, "(");
strcat(infix, " )");
while (infix[i] != '\0') {
if (isdigit(infix[i]) || (infix[i] == '-' && wasOperator)) {
// 数値を扱う
if (infix[i] == '-') {
token[j++] = infix[i++];
}
while (isdigit(infix[i])) {
token[j++] = infix[i++];
}
token[j] = '\0';
strcat(postfix, token);
strcat(postfix, " ");
j = 0;
wasOperator = 0; // 次は減算演算子
} else if (isalpha(infix[i])) {
// 変数を扱う
token[j++] = infix[i++];
token[j] = '\0';
strcat(postfix, token);
strcat(postfix, " ");
j = 0;
wasOperator = 0; // 次は減算演算子
} else if (infix[i] == '(') {
// 左括弧を扱う
token[0] = infix[i++];
token[1] = '\0';
push(&stackPtr, token);
wasOperator = 1; // 次に減算演算子はこない
} else if (isOperator(infix[i])) {
// 演算子を扱う
token[0] = infix[i++];
token[1] = '\0';
while (isOperator(stackTop(&stackPtr)[0]) && precedence(stackTop(&stackPtr)[0], token[0]) >= 0) {
strcat(postfix, pop(&stackPtr));
strcat(postfix, " ");
}
push(&stackPtr, token);
wasOperator = 1; // 次に減算演算子はこない
} else if (infix[i] == ')') {
// 右括弧を扱う
while (stackTop(&stackPtr)[0] != '(') {
strcat(postfix, pop(&stackPtr));
strcat(postfix, " ");
}
pop(&stackPtr); // Pop left parenthesis
i++;
wasOperator = 0; // 次は減算演算子
} else {
// 空白やその他の文字は無視
i++;
}
}
postfix[strlen(postfix) - 1] = '\0';
}
Python
- c: 練習問題12.13の後置式評価アルゴリズムを複数桁の整数オペランドと1文字の変数名オペランドを処理できるように改良
- このアルゴリズムには、式を直接評価しないでそれに相当するSML命令を生成する機能を組み込む
C言語
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define SIZE 100
#define MEMORY_SIZE 100
#define DEBUG(x) x
// スタックのノードを表す構造体
typedef struct stackNode {
int data;
struct stackNode *nextPtr;
} StackNode;
void push(StackNode **, int);
int pop(StackNode **);
int isOperator(char);
int calculate(int, int, char);
int generateSML(char *, int *);
int main() {
int end;
char postfix[100];
printf("後置式を入力してください\n");
// 注: 命令コードを生成するだけで実行はしないのでメモリに演算結果は格納されない
// 後置式の例 6 2 + 5 * 8 4 / -
// 生成されるSML命令
// 00: 2099 99番地のデータ(6)をアキュムレーターにロード
// 01: 3098 98番地のデータ(2)をアキュムレーターの値に足す
// 02: 2197 アキュムレーターから97番地に結果(6 + 2 = 8)をストア
// 03: 2097 97番地のデータ(8)をアキュムレーターにロード
// 04: 3396 96番地のデータ(5)をアキュムレーターの値(8)に掛ける
// 05: 2195 アキュムレーターから95番地に結果(8 * 5 = 40)をストア
// 06: 2094 94番地のデータ(8)をアキュムレーターにロード
// 07: 3293 93番地のデータ(4)でアキュムレーターの値(8)を割る
// 08: 2192 アキュムレーターから92番地に結果(8 / 4 = 2)をストア
// 09: 2095 95番地のデータ(40)をアキュムレーターにロード
// 10: 3192 92番地のデータ(2)をアキュムレーターの値(40)から引く
// 11: 2191 アキュムレーターから91番地に結果(40 - 2 = 38)をストア
// 後置式の例 -150 w +
// 生成されるSML命令
// 00: 2099 99番地のデータ(-150)をアキュムレーターにロード
// 01: 3098 98番地のデータ(wの中身)をアキュムレーターの値に足す
// 02: 2197 アキュムレーターから97番地に結果(-150 + wの中身)をストア
fgets(postfix, sizeof(postfix), stdin);
DEBUG(printf("postfix %s\n", postfix));
// 空なら終了(fgets)
if (postfix[1] == '\0') {
return 0;
}
int memory[MEMORY_SIZE] = {0};
end = generateSML(postfix, memory);
// 結果の表示
printf("メモリ内容:\n");
for (int i = 0; i < MEMORY_SIZE; i++) {
printf("%02d: %04d", i, memory[i]);
if((i + 1) % 5 == 0){
printf("\n");
}else{
printf(" ");
}
}
return 0;
}
void push(StackNode **topPtr, int info) {
StackNode *newPtr = (StackNode *)malloc(sizeof(StackNode));
if (newPtr != NULL) {
newPtr->data = info;
newPtr->nextPtr = *topPtr;
*topPtr = newPtr;
} else {
printf("空きメモリがないので %d は挿入できません\n", info);
}
}
int pop(StackNode **topPtr) {
StackNode *tempPtr;
int popValue;
tempPtr = *topPtr;
popValue = (*topPtr)->data;
*topPtr = (*topPtr)->nextPtr;
free(tempPtr);
return popValue;
}
int isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/' || c == '%' || c == '^';
}
int calculate(int y, int x, char c) {
if (c == '+') {
return y + x;
} else if (c == '-') {
return y - x;
} else if (c == '*') {
return y * x;
} else if (c == '/') {
return y / x;
} else if (c == '%') {
return y % x;
} else if (c == '^') {
return y ^ x;
}
return 0;
}
// SML命令を生成する関数
int generateSML(char *postfix, int *memory) {
StackNode *stackPtr = NULL;
int now;
int x, y;
char token[10];
int j = 0;
int dataCounter = MEMORY_SIZE - 1;
int operationCounter = 0;
for (now = 0; postfix[now] != '\0' && now < SIZE; now++) {
// 負の数に対応するロジックを追加
if (isdigit(postfix[now]) || (postfix[now] == '-' && isdigit(postfix[now + 1]))) {
token[j++] = postfix[now];
while (isdigit(postfix[now + 1])) {
token[j++] = postfix[++now];
}
token[j] = '\0';
memory[dataCounter] = atoi(token);
push(&stackPtr, dataCounter--); // メモリアドレスをスタックにプッシュ
j = 0;
} else if (isalpha(postfix[now])) {
memory[dataCounter] = postfix[now]; // 変数名のASCII値をメモリに保存
push(&stackPtr, dataCounter--); // メモリアドレスをスタックにプッシュ
} else if (isOperator(postfix[now])) {
x = pop(&stackPtr);
y = pop(&stackPtr);
memory[operationCounter++] = 2000 + y; // LOAD y
if (postfix[now] == '+') {
memory[operationCounter++] = 3000 + x; // ADD x
} else if (postfix[now] == '-') {
memory[operationCounter++] = 3100 + x; // SUBTRACT x
} else if (postfix[now] == '*') {
memory[operationCounter++] = 3300 + x; // MULTIPLY x
} else if (postfix[now] == '/') {
memory[operationCounter++] = 3200 + x; // DIVIDE x
}
memory[operationCounter++] = 2100 + dataCounter; // STORE (dataCounter + 1)
push(&stackPtr, dataCounter--);
}
if (operationCounter > dataCounter) {
printf("メモリを使い果たしました\n");
exit(EXIT_FAILURE);
}
}
return operationCounter;
}
Python
- d: Simpleコンパイラを作成
- 3つのSMLプログラムファイルで動作検証
12.27d_simpleProgram1.txt
5 rem 1からxまで合計する
10 input x
15 rem 条件「y==x」の判定
20 if y == x goto 60
25 rem yをインクリメントする
30 let y = y + 1
35 rem yを合計に足し込む
40 let t = t + y
45 rem 行番号20以下をループ
50 goto 20
55 rem 結果をプリントする
60 print t
99 end
12.27d_simpleProgram2.txt
10 rem いくつかの変数の2乗を計算する
20 input j
23 rem
25 rem 番兵値かどうか調べる
30 if j == -9999 goto 99
33 rem
35 rem 変数の2乗を計算して、変数kに代入する
40 let k = j * j
50 print k
53 rem
55 rem 次の整数の入力へ飛ぶ
60 goto 20
99 end
12.27d_simpleProgram3.txt
10 input x
20 input d
22 rem 今入力したデータが前のデータより小さいなら
30 if d <= e goto 50
40 rem 最大値を更新する
44 let e = d
50 let c = c + 1
60 if c < x goto 20
80 print e
90 end
C言語(※: 変数のAscii値をメモリに格納する必要があるか要確認
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<conio.h>
#include<ctype.h>
#define SYMBOLTABLE_SIZE 100
#define MEMORY_SIZE 100
#define POSTFIX_SIZE 100
typedef struct tableEntry
{
int symbol;
char type; /* 'C', 'L', または 'V' */
int location; /* 00から99 */
}TableEntry;
// スタックのノードを表す構造体
typedef struct stackNodeChars {
char data[10]; // 文字列データを格納
struct stackNodeChars *nextPtr;
} StackNodeChars;
// スタックのノードを表す構造体
typedef struct stackNodeInt{
int data;
struct stackNodeInt *nextPtr;
} StackNodeInt;
void convertToPostfix(char [], char []);
void pushChar(StackNodeChars **, char *);
char *popChar(StackNodeChars **);
void pushInt(StackNodeInt **, int);
int popInt(StackNodeInt **);
int isOperator(char);
char *stackTop(StackNodeChars **);
int isEmpty(StackNodeChars **);
int calculate(int, int, char);
void generateSML(char *, int *, TableEntry *, int *, int *, char);
void pass1(int *, int *, int *, TableEntry [], int [], int [], FILE *);
int pass2(int, int, int [], TableEntry [], int []);
void printSymbolTable(int, TableEntry *);
void printSMLInstruction(int, int []);
void printMemory(int, int []);
char inputOutputfileNumber[] = "2";
int main()
{
FILE *file;
TableEntry symbolTable[SYMBOLTABLE_SIZE];
int memory[MEMORY_SIZE] = {0};
int operationCounter = 0;
int dataCounter = MEMORY_SIZE - 1;
int symbolTableCounter = 0;
int flags[MEMORY_SIZE];
char filePath[50] = "./12.27d_simpleProgram"; // Destination buffer
strcat(filePath, inputOutputfileNumber);
strcat(filePath, ".txt"); // Append ".txt"
// ファイルを開く
// daitel P486
// yやtのメモリ番地は0で初期化されている daitel P285
file = fopen(filePath, "r");
//file = fopen("./12.27d_simpleProgram1.txt", "r");
if (file == NULL)
{
fprintf(stderr, "ファイルを開くことができません。\n");
return -1;
}
for (int i = 0; i < MEMORY_SIZE; i++) {
flags[i] = -1;
}
// pass1
pass1(&operationCounter, &dataCounter, &symbolTableCounter, symbolTable, flags, memory, file);
// ファイルを閉じる
fclose(file);
// pass2
if (pass2(operationCounter, symbolTableCounter, flags, symbolTable, memory) == -1)
{
return -1;
}
printf("\n「最終結果」\n");
printSMLInstruction(operationCounter, memory);
printMemory(MEMORY_SIZE, memory);
getch();
return 0;
}
// スタックにプッシュする関数
void pushChar(StackNodeChars **topPtr, char *info) {
StackNodeChars *newPtr = (StackNodeChars *)malloc(sizeof(StackNodeChars));
if (newPtr != NULL) {
strcpy(newPtr->data, info);
newPtr->nextPtr = *topPtr;
*topPtr = newPtr;
} else {
printf("空きメモリがないので %s は挿入できません\n", info);
}
}
// スタックからポップする関数
char *popChar(StackNodeChars **topPtr) {
StackNodeChars *tempPtr;
char *popValue = (char *)malloc(10 * sizeof(char));
tempPtr = *topPtr;
strcpy(popValue, (*topPtr)->data);
*topPtr = (*topPtr)->nextPtr;
free(tempPtr);
return popValue;
}
// 演算子かどうかを判定する関数
int isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/' || c == '%' || c == '^';
}
// スタックのトップを取得する関数
char *stackTop(StackNodeChars **topPtr) {
return (*topPtr)->data;
}
// スタックが空であるかを判定する関数
int isEmpty(StackNodeChars **topPtr) {
return *topPtr == NULL;
}
// 演算子の優先順位を判定する関数
int precedence(char op1, char op2) {
if (op1 == '*' || op1 == '/' || op1 == '%') {
return (op2 == '+' || op2 == '-') ? 1 : 0;
} else {
return (op2 == '+' || op2 == '-') ? 0 : -1;
}
}
// 中置式を後置式に変換する関数
void convertToPostfix(char infix[], char postfix[]) {
StackNodeChars *stackPtr = NULL;
char token[10];
int i = 0, j = 0;
int wasOperator = 1; // 1: 次は減算演算子がこない(負の符号) 0: 次は減算演算子がくる
pushChar(&stackPtr, "(");
strcat(infix, " )");
while (infix[i] != '\0') {
if (isdigit(infix[i]) || (infix[i] == '-' && wasOperator)) {
// 数値を扱う
if (infix[i] == '-') {
token[j++] = infix[i++];
}
// 数字の処理
while (isdigit(infix[i])) {
token[j++] = infix[i++];
}
token[j] = '\0';
strcat(postfix, token);
strcat(postfix, " ");
j = 0;
wasOperator = 0; // 次は減算演算子
} else if (isalpha(infix[i])) {
// 変数を扱う
token[j++] = infix[i++];
token[j] = '\0';
strcat(postfix, token);
strcat(postfix, " ");
j = 0;
wasOperator = 0; // 次は減算演算子
} else if (infix[i] == '(') {
// 左括弧を扱う
token[0] = infix[i++];
token[1] = '\0';
pushChar(&stackPtr, token);
wasOperator = 1; // 次に減算演算子はこない
} else if (isOperator(infix[i])) {
// 演算子を扱う
token[0] = infix[i++];
token[1] = '\0';
while (isOperator(stackTop(&stackPtr)[0]) && precedence(stackTop(&stackPtr)[0], token[0]) >= 0) {
strcat(postfix, popChar(&stackPtr));
strcat(postfix, " ");
}
pushChar(&stackPtr, token);
wasOperator = 1; // 次に減算演算子はこない
} else if (infix[i] == ')') {
// 右括弧を扱う
while (stackTop(&stackPtr)[0] != '(') {
strcat(postfix, popChar(&stackPtr));
strcat(postfix, " ");
}
popChar(&stackPtr); // Pop left parenthesis
i++;
wasOperator = 0; // 次は減算演算子
} else {
// 空白やその他の文字は無視
i++;
}
}
postfix[strlen(postfix) - 1] = '\0'; // 最後の余分なスペースを削除
}
void pushInt(StackNodeInt **topPtr, int info) {
StackNodeInt *newPtr = (StackNodeInt *)malloc(sizeof(StackNodeInt));
if (newPtr != NULL) {
newPtr->data = info;
newPtr->nextPtr = *topPtr;
*topPtr = newPtr;
} else {
printf("空きメモリがないので %d は挿入できません\n", info);
}
}
int popInt(StackNodeInt **topPtr) {
StackNodeInt *tempPtr;
int popValue;
tempPtr = *topPtr;
popValue = (*topPtr)->data;
*topPtr = (*topPtr)->nextPtr;
free(tempPtr);
return popValue;
}
int calculate(int y, int x, char c) {
if (c == '+') {
return y + x;
} else if (c == '-') {
return y - x;
} else if (c == '*') {
return y * x;
} else if (c == '/') {
return y / x;
} else if (c == '%') {
return y % x;
} else if (c == '^') {
return y ^ x;
}
return 0;
}
// SML命令を生成する関数
void generateSML(char *postfix, int *memory, TableEntry *symbolTable, int *operationCounter, int *dataCounter, char left) {
StackNodeInt *stackPtr = NULL;
int now;
int x, y;
char token[10];
int i;
int j = 0;
int memoryLocation;
for (now = 0; postfix[now] != '\0' && now < POSTFIX_SIZE; now++) {
// 負の数に対応するロジックを追加
if (isdigit(postfix[now]) || (postfix[now] == '-' && isdigit(postfix[now + 1]))) {
token[j++] = postfix[now];
while (isdigit(postfix[now + 1])) {
token[j++] = postfix[++now];
}
token[j] = '\0';
for(i = 0; i < SYMBOLTABLE_SIZE; i++){
// 登録されてるので必ず通る
if(symbolTable[i].symbol == atoi(token) && symbolTable[i].type == 'C'){
memoryLocation = symbolTable[i].location;
}
}
memory[memoryLocation] = atoi(token);
pushInt(&stackPtr, memoryLocation); // メモリアドレスをスタックにプッシュ
j = 0;
} else if (isalpha(postfix[now])) {
for(i = 0; i < SYMBOLTABLE_SIZE; i++){
// 登録されてるので必ず通る
if(symbolTable[i].symbol == postfix[now] && symbolTable[i].type == 'V'){
memoryLocation = symbolTable[i].location;
}
}
memory[memoryLocation] = postfix[now]; // 変数名のASCII値をメモリに保存
pushInt(&stackPtr, memoryLocation); // メモリアドレスをスタックにプッシュ
} else if (isOperator(postfix[now])) {
x = popInt(&stackPtr);
y = popInt(&stackPtr);
memory[(*operationCounter)++] = 2000 + y; // LOAD y
if (postfix[now] == '+') {
memory[*operationCounter] = 3000 + x; // ADD x
*operationCounter = *operationCounter + 1;
} else if (postfix[now] == '-') {
memory[*operationCounter] = 3100 + x; // SUBTRACT x
*operationCounter = *operationCounter + 1;
} else if (postfix[now] == '*') {
memory[*operationCounter] = 3300 + x; // MULTIPLY x
*operationCounter = *operationCounter + 1;
} else if (postfix[now] == '/') {
memory[*operationCounter] = 3200 + x; // DIVIDE x
*operationCounter = *operationCounter + 1;
}
memory[(*operationCounter)++] = 2100 + *dataCounter;
pushInt(&stackPtr, *dataCounter);
}
//printf("\n%5d\n", *operationCounter);
if (*operationCounter > *dataCounter){
printf("メモリを使い果たしました\n");
exit(EXIT_FAILURE);
}
}
memory[(*operationCounter)++] = 2000 + *dataCounter;
(*dataCounter)--;
for(i = 0; i < SYMBOLTABLE_SIZE; i++){
// 登録されてるので必ず通る
if(symbolTable[i].symbol == left && symbolTable[i].type == 'V'){
memoryLocation = symbolTable[i].location;
}
}
memory[(*operationCounter)++] = 2100 + memoryLocation;
return;
}
void pass1(int *operationCounter, int *dataCounter, int *symbolTableCounter, TableEntry symbolTable[], int flags[], int memory[], FILE *file)
{
char line[256]; // 読み込む行の最大長を256文字
char *lineNum;
char *order;
char *variable;
char *variableOrConstant;
char *operator;
char *state;
char *stateOriginal;
char postfix[POSTFIX_SIZE] = "";
char *jumpNum;
char *c;
int i;
int j;
int k;
int symbol;
// rem 〇
// input 〇
// if 〇
// goto 〇
// let 〇
// print 〇
// end 〇
// ファイルから1行ずつ読み込む
while (fgets(line, sizeof(line), file) != NULL)
{
// 改行文字を削除
line[strcspn(line, "\n")] = '\0';
// printf("line %s\n", line);
lineNum = strtok(line, " ");
//printf("lineNum %s ", lineNum);
symbolTable[*symbolTableCounter].symbol = atoi(lineNum);
symbolTable[*symbolTableCounter].type = 'L';
symbolTable[*symbolTableCounter].location = *operationCounter;
(*symbolTableCounter)++;
// lineNum = strtok(line, " "); でlineを読み込んでるのでNULLを引数に
order = strtok(NULL, " ");
//printf("order %s ", order);
if (strcmp(order,"let") == 0){
variable = strtok(NULL, " ");
//printf("variable %s\n", variable);
for(j = 0; j < *symbolTableCounter; j++){
if(symbolTable[j].symbol == variable[0] && symbolTable[j].type == 'V'){
break;
}
}
// シンボル表に初めて登録される変数
if(j == *symbolTableCounter){
symbolTable[*symbolTableCounter].symbol = variable[0];
symbolTable[*symbolTableCounter].type = 'V';
symbolTable[*symbolTableCounter].location = *dataCounter;
(*symbolTableCounter)++;
memory[*dataCounter] = variable[0];
(*dataCounter)--;
}
// =
operator = strtok(NULL, " ");
// printf("operator %s\n", operator);
// 式
state = strtok(NULL, "");
printf("state %s\n", state);
printf("state len %d\n", strlen(state));
// もしstateがd + 3などではなくdの場合、d + 0とする
if(strlen(state) == 1)
{
state = strcat(state, " + 0");
}
stateOriginal = strdup(state);
c = strtok(state, " ");
do{
//printf("c %s\n", c);
if (!isOperator(c[0])){
for(j = 0; j < *symbolTableCounter; j++){
if(symbolTable[j].symbol == c[0] && symbolTable[j].type == 'V'){
break;
}
else if(symbolTable[j].symbol == atoi(c) && symbolTable[j].type == 'C'){
break;
}
}
// シンボル表に初めて登録される変数
if(j == *symbolTableCounter){
symbolTable[*symbolTableCounter].symbol = symbol;
// 変数
if (isalpha(c[0])){
symbolTable[j].symbol = c[0];
symbolTable[*symbolTableCounter].type = 'V';
memory[*dataCounter] = c[0];
// 定数
}else{
symbolTable[j].symbol = atoi(c);
symbolTable[*symbolTableCounter].type = 'C';
memory[*dataCounter] = atoi(c);
}
symbolTable[*symbolTableCounter].location = *dataCounter;
(*dataCounter)--;
(*symbolTableCounter)++;
}
}
}while ((c = strtok(NULL, " ")) != NULL);
///printf("state %s\n", state);
// printf("stateOriginal %s\n", stateOriginal);
memset(postfix, '\0', POSTFIX_SIZE);
convertToPostfix(stateOriginal, postfix);
//printf("後置式: %s\n", postfix);
generateSML(postfix, memory, symbolTable, operationCounter, dataCounter, variable[0]);
}else if (strcmp(order,"input") == 0){
variable = strtok(NULL, " ");
// printf("variable %s\n", variable);
for(j = 0; j < *symbolTableCounter; j++){
if(symbolTable[j].symbol == variable[0] && symbolTable[j].type == 'V'){
break;
}
}
// シンボル表に初めて登録される変数
if(j == *symbolTableCounter){
symbolTable[*symbolTableCounter].symbol = variable[0];
symbolTable[*symbolTableCounter].type = 'V';
symbolTable[*symbolTableCounter].location = *dataCounter;
(*symbolTableCounter)++;
//printf("operationCounter %d\n", *operationCounter);
//printf("dataCounter %d\n", *dataCounter);
memory[*operationCounter] = 1000 + *dataCounter;
//printf("memory[operationCounter] %d\n", memory[*operationCounter]);
(*operationCounter)++;
memory[*dataCounter] = variable[0];
(*dataCounter)--;
}
else if(j < *symbolTableCounter){
memory[*operationCounter] = 1000 + symbolTable[j].location;
(*operationCounter)++;
}
// x == y + 1の条件判定には未対応
}else if (strcmp(order,"if") == 0){
variable = strtok(NULL, " ");
//printf("variable %s ", variable);
for(j = 0; j < *symbolTableCounter; j++){
if(symbolTable[j].symbol == variable[0] && symbolTable[j].type == 'V'){
break;
}
}
// シンボル表に初めて登録される変数
if(j == *symbolTableCounter){
symbolTable[*symbolTableCounter].symbol = variable[0];
symbolTable[*symbolTableCounter].type = 'V';
symbolTable[*symbolTableCounter].location = *dataCounter;
(*symbolTableCounter)++;
// 20 アキュムレーターにロード
// printf("operationCounter %d\n", *operationCounter);
memory[*operationCounter] = 2000 + *dataCounter;
memory[*dataCounter] = variable[0];
(*operationCounter)++;
(*dataCounter)--;
}
else if(j < *symbolTableCounter){
memory[*operationCounter] = 2000 + symbolTable[j].location;
(*operationCounter)++;
}
// == <= <にのみ対応
operator = strtok(NULL, " ");
if(strcmp(operator, "==") == 0)
{
variableOrConstant = strtok(NULL, " ");
//printf("variableOrConstant %s ", variableOrConstant);
// 変数・もしくは定数として既にシンボル表に格納されているか
for(j = 0; j < *symbolTableCounter; j++){
if(symbolTable[j].symbol == variableOrConstant[0] && symbolTable[j].type == 'V'){
break;
}
else if(symbolTable[j].symbol == atoi(variableOrConstant) && symbolTable[j].type == 'C'){
break;
}
}
// シンボル表に初めて登録される変数
if(j == *symbolTableCounter)
{
// 変数
if (isalpha(variableOrConstant[0])){
symbolTable[*symbolTableCounter].symbol = variableOrConstant[0];
symbolTable[*symbolTableCounter].type = 'V';
memory[*dataCounter] = variableOrConstant[0];
}
// 定数
else
{
symbolTable[*symbolTableCounter].symbol = atoi(variableOrConstant);
symbolTable[*symbolTableCounter].type = 'C';
memory[*dataCounter] = atoi(variableOrConstant);
}
symbolTable[*symbolTableCounter].location = *dataCounter;
(*symbolTableCounter)++;
(*dataCounter)--;
memory[*operationCounter] = 3100 + symbolTable[*symbolTableCounter - 1].location;
(*operationCounter)++;
}
else if(j < *symbolTableCounter){
memory[*operationCounter] = 3100 + symbolTable[j].location;
(*operationCounter)++;
}
// gotoを飛ばすため戻り値は利用しない
strtok(NULL, " ");
jumpNum = strtok(NULL, " ");
// printf("\njumpNum %s\n", jumpNum);
for(j = 0; j < *symbolTableCounter; j++){
if(symbolTable[j].symbol == atoi(jumpNum) && symbolTable[j].type == 'L'){
break;
}
}
// 飛び先の行番号はシンボル表にない
if(j == *symbolTableCounter){
flags[*operationCounter] = atoi(jumpNum);
// BRANCHZERO
memory[*operationCounter] = 4200;
(*operationCounter)++;
}
else if(j < *symbolTableCounter){
memory[*operationCounter] = 4200 + symbolTable[j].location;
(*operationCounter)++;
}
}
else if(strcmp(operator, "<=") == 0)
{
variableOrConstant = strtok(NULL, " ");
// printf("variableOrConstant %s ", variableOrConstant);
for(j = 0; j < *symbolTableCounter; j++){
if(symbolTable[j].symbol == variableOrConstant[0] && symbolTable[j].type == 'V'){
break;
}
}
// シンボル表に初めて登録される変数
if(j == *symbolTableCounter){
symbolTable[*symbolTableCounter].symbol = variableOrConstant[0];
symbolTable[*symbolTableCounter].type = 'V';
symbolTable[*symbolTableCounter].location = *dataCounter;
memory[*dataCounter] = variableOrConstant[0];
(*symbolTableCounter)++;
(*dataCounter)--;
memory[*operationCounter] = 3100 + symbolTable[*symbolTableCounter - 1].location;
(*operationCounter)++;
}
else if(j < *symbolTableCounter){
memory[*operationCounter] = 3100 + symbolTable[j].location;
(*operationCounter)++;
}
// gotoを飛ばすため戻り値は利用しない
strtok(NULL, " ");
jumpNum = strtok(NULL, " ");
// printf("\njumpNum %s\n", jumpNum);
for(j = 0; j < *symbolTableCounter; j++){
if(symbolTable[j].symbol == atoi(jumpNum) && symbolTable[j].type == 'L'){
break;
}
}
// 飛び先の行番号はシンボル表にない
if(j == *symbolTableCounter){
flags[*operationCounter] = atoi(jumpNum);
// BRANCHZERO
memory[*operationCounter] = 4200;
(*operationCounter)++;
flags[*operationCounter] = atoi(jumpNum);
// BRANCHNEG
memory[*operationCounter] = 4100;
(*operationCounter)++;
}
else if(j < *symbolTableCounter){
memory[*operationCounter] = 4200 + symbolTable[j].location;
(*operationCounter)++;
memory[*operationCounter] = 4100 + symbolTable[j].location;
(*operationCounter)++;
}
}
else if(strcmp(operator, "<") == 0)
{
variableOrConstant = strtok(NULL, " ");
// printf("variableOrConstant %s ", variableOrConstant);
for(j = 0; j < *symbolTableCounter; j++){
if(symbolTable[j].symbol == variableOrConstant[0] && symbolTable[j].type == 'V'){
break;
}
}
// シンボル表に初めて登録される変数
if(j == *symbolTableCounter){
symbolTable[*symbolTableCounter].symbol = variableOrConstant[0];
symbolTable[*symbolTableCounter].type = 'V';
symbolTable[*symbolTableCounter].location = *dataCounter;
memory[*dataCounter] = variableOrConstant[0];
(*symbolTableCounter)++;
(*dataCounter)--;
memory[*operationCounter] = 3100 + symbolTable[*symbolTableCounter - 1].location;
(*operationCounter)++;
}
else if(j < *symbolTableCounter){
memory[*operationCounter] = 3100 + symbolTable[j].location;
(*operationCounter)++;
}
// gotoを飛ばすため戻り値は利用しない
strtok(NULL, " ");
jumpNum = strtok(NULL, " ");
// printf("\njumpNum %s\n", jumpNum);
for(j = 0; j < *symbolTableCounter; j++){
if(symbolTable[j].symbol == atoi(jumpNum) && symbolTable[j].type == 'L'){
break;
}
}
// 飛び先の行番号はシンボル表にない
if(j == *symbolTableCounter){
flags[*operationCounter] = atoi(jumpNum);
// BRANCHNEG
memory[*operationCounter] = 4100;
(*operationCounter)++;
}
else if(j < *symbolTableCounter){
memory[*operationCounter] = 4100 + symbolTable[j].location;
(*operationCounter)++;
}
}
}else if (strcmp(order,"goto") == 0){
jumpNum = strtok(NULL, " ");
// printf("\njumpNum %s\n",jumpNum );
for(j = 0; j < *symbolTableCounter; j++){
if(symbolTable[j].symbol == atoi(jumpNum) && symbolTable[j].type == 'L'){
printf("%d\n", atoi(jumpNum));
break;
}
}
// 飛び先の行番号はシンボル表にない
if(j == *symbolTableCounter){
flags[*operationCounter] = atoi(jumpNum);
// BRANCHZERO
memory[*operationCounter] = 4000;
(*operationCounter)++;
}
else if(j < *symbolTableCounter){
memory[*operationCounter] = 4000 + symbolTable[j].location;
(*operationCounter)++;
}
}else if (strcmp(order,"print") == 0){
variable = strtok(NULL, " ");
// printf("variable %s ", variable);
for(j = 0; j < *symbolTableCounter; j++){
if(symbolTable[j].symbol == variable[0] && symbolTable[j].type == 'V'){
break;
}
}
// 飛び先の行番号はシンボル表にない
if(j == *symbolTableCounter){
printf("指定した変数は存在しません\n");
exit(EXIT_FAILURE);
}
else if(j < *symbolTableCounter){
memory[*operationCounter] = 1100 + symbolTable[j].location;
(*operationCounter)++;
}
}else if (strcmp(order,"end") == 0){
memory[*operationCounter] = 4300;
(*operationCounter)++;
}
if (*operationCounter > *dataCounter){
printf("メモリを使い果たしました\n");
exit(EXIT_FAILURE);
}
printSymbolTable(*symbolTableCounter, symbolTable);
printSMLInstruction(*operationCounter, memory);
}//while
}
int pass2(int operationCounter, int symbolTableCounter, int flags[], TableEntry symbolTable[], int memory[])
{
int i;
int j;
FILE* fileWrite;
char filePath[50] = "./12.27d_simpleProgramOutput"; // Destination buffer
strcat(filePath, inputOutputfileNumber);
strcat(filePath, ".txt"); // Append ".txt"
for(i = 0; i < operationCounter; i++){
printf("flags[%d] %d\n", i, flags[i]);
if(flags[i] != -1){
for(j = 0; j < symbolTableCounter; j++){
if (symbolTable[j].symbol == flags[i]){
memory[i] = memory[i] + symbolTable[j].location;
}
}
}
}
// P486 yやtのメモリ番地は0で初期化されている P285
// 12.27d_simpleProgram1.txt
// 00: 1099 x(99番地)に値を入力する
// 01: 2098 アキュムレーターにy(98番地)をロードする
// 02: 3199 アキュムレーターからx(99番地)を引く
// 03: 4215 アキュムレーターがゼロなら15番地へ飛ぶ
// 04: 2098 アキュムレーターにy(98番地)をロードする
// 05: 3097 アキュムレーターに1(97番地)を足す
// 06: 2196 アキュムレーターの値を一時的に96番地にストアする
// 07: 2096 アキュムレーターに96番地をロードする
// 08: 2198 アキュムレーターの値をy(98番地)にストアする
// 09: 2095 アキュムレーターにt(95番地)をロードする
// 10: 3098 アキュムレーターにy(98)番地を足す
// 11: 2194 アキュムレーターの値を一時的に94番地にストアする
// 12: 2094 アキュムレーターに94番地をロードする
// 13: 2195 アキュムレーターの値をt(95番地)にストアする
// 14: 4001 01番地へ飛ぶ
// 15: 1195 t(95番地)を画面に表示する
// 16: 4300 実行を終了する
// 12.27d_simpleProgram2.txt"
// 00: 1099 j(99番地)に値を入力する
// 01: 2099 アキュムレーターにj(99番地)をロードする
// 02: 3198 アキュムレーターから-9999(98番地)を引く
// 03: 4211 アキュムレーターがゼロなら11番地へ飛ぶ
// 04: 2099 アキュムレーターにj(99番地)をロードする
// 05: 3399 アキュムレーターにj(99番地)を掛ける
// 06: 2196 アキュムレーターの値を一時的に96番地にストアする
// 07: 2096 アキュムレーターに96番地をロードする
// 08: 2197 アキュムレーターの値をk(97番地)にストアする
// 09: 1197 k(97番地)を画面に表示する
// 10: 4000 00番地へ飛ぶ
// 11: 4300 実行を終了する
// 12.27d_simpleProgram3.txt"
// 00: 1099 x(99番地)に値を入力する
// 01: 1098 d(98番地)に値を入力する
// 02: 2098 アキュムレーターにd(98番地)をロードする
// 03: 3197 アキュムレーターからe(97番地)を引く
// 04: 4211 アキュムレーターがゼロなら11番地へ飛ぶ
// 05: 4111 アキュムレーターが負なら11番地へ飛ぶ
// 06: 2098 アキュムレーターにd(98番地)をロードする
// 07: 3096 アキュムレーターに0(96番地)を足す
// 08: 2195 アキュムレーターの値を一時的に95番地にストアする
// 09: 2095 アキュムレーターに95番地をロードする
// 10: 2197 アキュムレーターの値をe(97番地)にストアする
// 11: 2094 アキュムレーターにc(94番地)をロードする
// 12: 3093 アキュムレーターに1(93番地)を足す
// 13: 2192 アキュムレーターの値を一時的に92番地にストアする
// 14: 2092 アキュムレーターに92番地をロードする
// 15: 2194 アキュムレーターの値をc(94番地)にストアする
// 16: 2094 アキュムレーターにc(94番地)をロードする
// 17: 3199 アキュムレーターからx(99番地)を引く
// 18: 4101 アキュムレーターが負なら01番地へ飛ぶ
// 19: 1197 e(97番地)を画面に表示する
// 20: 4300 実行を終了する
// ファイルを開く
fileWrite = fopen(filePath, "w");
if (fileWrite == NULL)
{
fprintf(stderr, "書き込みファイルを開くことができません。\n");
return -1;
}
for (int i = 0; i < operationCounter; i++) {
fprintf(fileWrite, "%2d %04d\n", i, memory[i]);
}
}
void printSymbolTable(int symbolTableCounter, TableEntry *symbolTable)
{
int i;
printf("\n\nシンボル表\n");
for (i = 0; i < symbolTableCounter; i++){
if(symbolTable[i].type == 'C'){
printf("%3d シンボル: %6d タイプ: %3c メモリ番地 %4d\n", i, symbolTable[i].symbol, symbolTable[i].type, symbolTable[i].location);
}else if(symbolTable[i].type == 'V'){
printf("%3d シンボル: %6c タイプ: %3c メモリ番地 %4d\n", i, symbolTable[i].symbol, symbolTable[i].type, symbolTable[i].location);
}else{
printf("%3d シンボル: %6d タイプ: %3c メモリ番地 %4d\n", i, symbolTable[i].symbol, symbolTable[i].type, symbolTable[i].location);
}
}
}
void printSMLInstruction(int operationCounter, int memory[])
{
printf("\nSML命令:\n");
for (int i = 0; i < operationCounter; i++) {
printf("%02d: %04d", i, memory[i]);
if((i + 1) % 10 == 0){
printf("\n");
}else{
printf(" ");
}
}
printf("\n\n");
}
void printMemory(int memorySize, int memory[])
{
printf("\nメモリの内容:\n");
for (int i = 0; i < memorySize; i++) {
printf("%02d: %05d", i, memory[i]);
if((i + 1) % 10 == 0){
printf("\n");
}else{
printf(" ");
}
}
printf("\n\n");
}
Python
参考
- 12.15 Pythonのスタックとキューには何を使えばいいのか（各データ構造の速度比較）
- 12.15 いろんな言語で乱数取得
- 12.18【アルゴリズム】二分探索法の平均探索回数と近似値
- 12.22 二分探索木におけるノードの削除
- 【ソースコード・ターミナル】VSCodeの文字化け解消方法まとめ
12.:
C言語
Python