木構造における逆ポーランド記法について
Posted: 2009年8月08日(土) 00:09
下のプログラムは入力された計算式を逆ポーランド記法で表示し、その後木構造で表示するプログラムです。
---------------------------------------------------------------------
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 256
struct Node {
char str[N];
struct Node* left;
struct Node* right;
};
void delete_space(char *str);/* スペースを削除する */
int delete_bracket(char *str);/* 式の外側部分の括弧を削除する.異常があれば-
1を返す.*/
int getRootOperator(char *str);/* 一番低い優先順位の演算子の配列番号を返す.
*/
int insert(struct Node* node);/* 式を二分木に挿入する.異常があれば-1を返す
*/
void reverse_polish_notation(struct Node* node);/* 二分木を逆ポーランド記法
で出力する */
void Tree(struct Node* node, int h); /* 木の表示 */
int main (int argc, const char * argv[/url]){
struct Node *root ;
root = (struct Node *)malloc(sizeof(struct Node));
printf("式を入力してください: ");
scanf("%[^\n]", root->str);
delete_space(root->str);/* スペースを削除 */
if (insert(root) < 0) {/* 木にデータを挿入 */
fprintf(stderr, "syntax error\n");
return -1;
}
printf("逆ポーランド記法: ");
reverse_polish_notation(root);
printf("\n");
printf("木構造の表示\n");
Tree(root,0);
return(0);
}
void delete_space(char *str){
int i=0,j=0 ;
char *cmpstr ;
cmpstr = str ;
while (cmpstr != '\0') {
if (cmpstr == ' ')
i++;
else{
str[j] = cmpstr;
i++;
j++;
}
}
str[j] = '\0';
}
int delete_bracket(char *str){
int i;
int length = strlen(str);
int set = 1;
if (str[0] != '(' || str[length - 1] != ')')
return 0;
for (i = 1; i < length - 1; i++) {/* 括弧の数が正しいか調べる */
if (str == '(')
set++;
else if (str == ')')
set--;
if (set == 0)
return 0;
}
if (set != 1) {/* 正しく無い場合は-1を返す */
return -1;
}
for (i = 0; i < length - 2; i++) {/* 括弧を外側から消してゆく */
str = str[i + 1];
}
str = '\0';
if (str[0] == '(')
delete_bracket(str);
return 0; /* OSに対する戻り値 */
}
int getRootOperator(char *str){
int i;
int rootOperator = -1;
int set = 0;
int pri;/* 優先順位 */
int lowpri = 4;
if (!str)
return -1;
for (i = 0; str; i++) {
switch (str) {
case '=': pri = 1; break;
case '+': pri = 2; break;
case '-': pri = 2; break;
case '*': pri = 3; break;
case '/': pri = 3; break;
case '(': set++; continue;
case ')': set--; continue;
default: continue;
}
if (set == 0 && pri <= lowpri) {/* 優先順位が低い配列番号を保存 */
lowpri = pri;
rootOperator = i;
}
}
return rootOperator;
}
int insert(struct Node* node){/* 再帰される関数 */
int rootOperator;
int len_str;
if (!node)
return -1;
rootOperator = getRootOperator(node->str);
if (rootOperator == (int)-1) {
node->left = NULL;
node->right = NULL;
return 0;
}
len_str = strlen(node->str);
/* 左側の処理 */
/* 問題箇所->始まり */
node->left = (struct Node *)malloc(sizeof(struct Node));/* メモリ確保 */
if (node->left==NULL) {/* 一応無くても動く */
return -1;
}
strncpy(node->left->str, node->str, rootOperator);/* 最低優先順位演算子の
左側部分を左の子にコピー */
/* 問題箇所->終わり */
node->left->str[rootOperato[/url]='\0'; /* 文字列の最後にNULLをつける */
if (delete_bracket(node->left->str) < 0)/* 外側の括弧を削除する */
return -1;
if (insert(node->left) < 0)/* 再帰 */
return -1;
/* 右側の処理 */
/* 問題箇所->始まり */
node->right = (struct Node *)malloc(sizeof(struct Node));/* メモリ確保 */
if (node->right==NULL) {/* 一応無くても動く */
return -1;
}
strncpy(node->right->str, node->str + rootOperator + 1, len_str - rootOpe
rator);/* 最低優先順位演算子の右側部分を右の子にコピー */
/* 問題箇所->終わり */
if (delete_bracket(node->right->str) < 0)/* 外側の括弧を削除する */
return -1;
if (insert(node->right) < 0)/* 再帰 */
return -1;
/* 親ノードの処理 */
node->str[0] = node->str[rootOperato[/url];
node->str[1] = '\0';
return 0;
}
void reverse_polish_notation(struct Node* node)
{
if (!node)
return;
if (node->left)
reverse_polish_notation(node->left);
if (node->right)
reverse_polish_notation(node->right);
printf("%s ",node->str);
}
/* 木を表示する */
/* hは木の深さを表す */
void Tree(struct Node* node, int h){
int i;
if(node != NULL){
Tree( node->right, h+1 );/* node->rightを表示する */
for( i=0; i<h; i++ )
printf(" ");/* 木を表現するために3空白字下げをする */
printf("%s\n", node->str );/* node->strを出力 */
Tree( node->left, h+1 );/* node->leftを表示する */
}
}
--------------------------------------------------------------------------
---------------------------------------------------------------------
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 256
struct Node {
char str[N];
struct Node* left;
struct Node* right;
};
void delete_space(char *str);/* スペースを削除する */
int delete_bracket(char *str);/* 式の外側部分の括弧を削除する.異常があれば-
1を返す.*/
int getRootOperator(char *str);/* 一番低い優先順位の演算子の配列番号を返す.
*/
int insert(struct Node* node);/* 式を二分木に挿入する.異常があれば-1を返す
*/
void reverse_polish_notation(struct Node* node);/* 二分木を逆ポーランド記法
で出力する */
void Tree(struct Node* node, int h); /* 木の表示 */
int main (int argc, const char * argv[/url]){
struct Node *root ;
root = (struct Node *)malloc(sizeof(struct Node));
printf("式を入力してください: ");
scanf("%[^\n]", root->str);
delete_space(root->str);/* スペースを削除 */
if (insert(root) < 0) {/* 木にデータを挿入 */
fprintf(stderr, "syntax error\n");
return -1;
}
printf("逆ポーランド記法: ");
reverse_polish_notation(root);
printf("\n");
printf("木構造の表示\n");
Tree(root,0);
return(0);
}
void delete_space(char *str){
int i=0,j=0 ;
char *cmpstr ;
cmpstr = str ;
while (cmpstr != '\0') {
if (cmpstr == ' ')
i++;
else{
str[j] = cmpstr;
i++;
j++;
}
}
str[j] = '\0';
}
int delete_bracket(char *str){
int i;
int length = strlen(str);
int set = 1;
if (str[0] != '(' || str[length - 1] != ')')
return 0;
for (i = 1; i < length - 1; i++) {/* 括弧の数が正しいか調べる */
if (str == '(')
set++;
else if (str == ')')
set--;
if (set == 0)
return 0;
}
if (set != 1) {/* 正しく無い場合は-1を返す */
return -1;
}
for (i = 0; i < length - 2; i++) {/* 括弧を外側から消してゆく */
str = str[i + 1];
}
str = '\0';
if (str[0] == '(')
delete_bracket(str);
return 0; /* OSに対する戻り値 */
}
int getRootOperator(char *str){
int i;
int rootOperator = -1;
int set = 0;
int pri;/* 優先順位 */
int lowpri = 4;
if (!str)
return -1;
for (i = 0; str; i++) {
switch (str) {
case '=': pri = 1; break;
case '+': pri = 2; break;
case '-': pri = 2; break;
case '*': pri = 3; break;
case '/': pri = 3; break;
case '(': set++; continue;
case ')': set--; continue;
default: continue;
}
if (set == 0 && pri <= lowpri) {/* 優先順位が低い配列番号を保存 */
lowpri = pri;
rootOperator = i;
}
}
return rootOperator;
}
int insert(struct Node* node){/* 再帰される関数 */
int rootOperator;
int len_str;
if (!node)
return -1;
rootOperator = getRootOperator(node->str);
if (rootOperator == (int)-1) {
node->left = NULL;
node->right = NULL;
return 0;
}
len_str = strlen(node->str);
/* 左側の処理 */
/* 問題箇所->始まり */
node->left = (struct Node *)malloc(sizeof(struct Node));/* メモリ確保 */
if (node->left==NULL) {/* 一応無くても動く */
return -1;
}
strncpy(node->left->str, node->str, rootOperator);/* 最低優先順位演算子の
左側部分を左の子にコピー */
/* 問題箇所->終わり */
node->left->str[rootOperato[/url]='\0'; /* 文字列の最後にNULLをつける */
if (delete_bracket(node->left->str) < 0)/* 外側の括弧を削除する */
return -1;
if (insert(node->left) < 0)/* 再帰 */
return -1;
/* 右側の処理 */
/* 問題箇所->始まり */
node->right = (struct Node *)malloc(sizeof(struct Node));/* メモリ確保 */
if (node->right==NULL) {/* 一応無くても動く */
return -1;
}
strncpy(node->right->str, node->str + rootOperator + 1, len_str - rootOpe
rator);/* 最低優先順位演算子の右側部分を右の子にコピー */
/* 問題箇所->終わり */
if (delete_bracket(node->right->str) < 0)/* 外側の括弧を削除する */
return -1;
if (insert(node->right) < 0)/* 再帰 */
return -1;
/* 親ノードの処理 */
node->str[0] = node->str[rootOperato[/url];
node->str[1] = '\0';
return 0;
}
void reverse_polish_notation(struct Node* node)
{
if (!node)
return;
if (node->left)
reverse_polish_notation(node->left);
if (node->right)
reverse_polish_notation(node->right);
printf("%s ",node->str);
}
/* 木を表示する */
/* hは木の深さを表す */
void Tree(struct Node* node, int h){
int i;
if(node != NULL){
Tree( node->right, h+1 );/* node->rightを表示する */
for( i=0; i<h; i++ )
printf(" ");/* 木を表現するために3空白字下げをする */
printf("%s\n", node->str );/* node->strを出力 */
Tree( node->left, h+1 );/* node->leftを表示する */
}
}
--------------------------------------------------------------------------