ページ 11

木構造における逆ポーランド記法について

Posted: 2009年8月08日(土) 00:09
by かりむ
下のプログラムは入力された計算式を逆ポーランド記法で表示し、その後木構造で表示するプログラムです。


---------------------------------------------------------------------


#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を表示する */
}
}



--------------------------------------------------------------------------

Re:木構造における逆ポーランド記法について

Posted: 2009年8月08日(土) 00:32
by box
> 下のプログラムは入力された計算式を逆ポーランド記法で表示し、その後木構造で表示するプログラムです。

お聞きになりたいことは何ですか?

ソース投稿時は、ソース全体を
<pre>と</pre> (<と>は、半角)
ではさんでください。