20090321T22:02:41の更新内容
programming/tips/polish/index.wiki.txt
current  previous  

1,263  0,0  
+ 
${smdncms:tags,ポーランド記法,逆ポーランド記法,前置記法,後置記法,中置記法,二分木} 

+ 
*二分木によるポーランド記法・逆ポーランド記法化 

+ 
[[二分木を使って数式を逆ポーランド記法にする:http://smdn.invisiblefulmoon.net/ikimasshoy/cpp/polish.html]]のバグ修正版。 

+ 
中置記法を二分木に分解し、ポーランド記法(前置記法)、逆ポーランド記法(後置記法)、中置記法で出力する 

+ 
2項演算子のうち、四則演算子(+,,*,/)、代入演算子(=)が使用可能 

+ 
演算優先順位の指定に丸括弧()が使用可能 

+ 
new/delete使用なし 

+  
+ 
// gcc polish.c o polish 

+ 
#include <stdio.h> 

+ 
#include <string.h> 

+ 


+ 
typedef struct Node Node; 

+ 


+ 
#define MAX_NODES 80 

+ 
#define MAX_EXP_LEN 0x100 

+ 


+ 
struct Node { 

+ 
char exp[MAX_EXP_LEN]; 

+ 
Node* left; 

+ 
Node* right; 

+ 
}; 

+ 


+ 
static Node nodes[MAX_NODES]; 

+ 
static int nb_node_used = 0; 

+ 


+ 
Node* create_node() 

+ 
{ 

+ 
if 

+ 
return NULL; 

+ 
else 

+ 
return &nodes[nb_node_used++]; 

+ 
} 

+ 


+ 
void remove_space(char *exp) 

+ 
{ 

+ 
char *dst = exp; 

+ 
char *src = exp; 

+ 


+ 
while { 

+ 
if 

+ 
src++; 

+ 
else 

+ 
*(dst++) = *(src++); 

+ 
} 

+ 


+ 
*dst = '\0'; 

+ 
} 

+ 


+ 
int remove_bracket(char *exp) 

+ 
{ 

+ 
size_t i; 

+ 
size_t len = strlen(exp); 

+ 
int nest = 1; 

+ 


+ 
if 

+ 
return 0; 

+ 


+ 
for { 

+ 
if 

+ 
nest++; 

+ 
else if 

+ 
nest; 

+ 


+ 
if 

+ 
return 0; 

+ 
} 

+ 


+ 
if { 

+ 
fprintf(stderr, "unbalanced bracket: %s\n", exp); 

+ 
return 1; 

+ 
} 

+ 


+ 
for { 

+ 
exp[i] = exp[i + 1]; 

+ 
} 

+ 
exp[i] = '\0'; 

+ 


+ 
if 

+ 
remove_bracket(exp); 

+ 


+ 
return 0; 

+ 
} 

+ 


+ 
size_t get_pos_operator(char *exp) 

+ 
{ 

+ 
size_t i; 

+ 
size_t pos_op = 1; 

+ 
int nest = 0; 

+ 
int priority; 

+ 
int priority_lowest = 4; 

+ 


+ 
if 

+ 
return 1; 

+ 


+ 
for { 

+ 
switch { 

+ 
case '=': priority = 1; break; 

+ 
case '+': priority = 2; break; 

+ 
case '': priority = 2; break; 

+ 
case '*': priority = 3; break; 

+ 
case '/': priority = 3; break; 

+ 
case '(': nest++; continue; 

+ 
case ')': nest; continue; 

+ 
default: continue; 

+ 
} 

+ 


+ 
if { 

+ 
priority_lowest = priority; 

+ 
pos_op = i; 

+ 
} 

+ 
} 

+ 


+ 
return pos_op; 

+ 
} 

+ 


+ 
int parse_expression(Node* node) 

+ 
{ 

+ 
size_t pos_op; 

+ 
size_t len_exp; 

+ 


+ 
if 

+ 
return 1; 

+ 


+ 
pos_op = get_pos_operator(node>exp); 

+ 


+ 
if { 

+ 
node>left = NULL; 

+ 
node>right = NULL; 

+ 


+ 
return 0; 

+ 
} 

+ 


+ 
len_exp = strlen(node>exp); 

+ 


+ 
// lefthand side 

+ 
node>left = create_node(); 

+ 


+ 
if { 

+ 
fprintf(stderr, "expression too long\n"); 

+ 
return 1; 

+ 
} 

+ 


+ 
strncpy(node>left>exp, node>exp, pos_op); 

+ 


+ 
if 

+ 
return 1; 

+ 


+ 
if 

+ 
return 1; 

+ 


+ 
// righthand side 

+ 
node>right = create_node(); 

+ 


+ 
if { 

+ 
fprintf(stderr, "expression too long\n"); 

+ 
return 1; 

+ 
} 

+ 


+ 
strncpy(node>right>exp, node>exp + pos_op + 1, len_exp  pos_op); 

+ 


+ 
if 

+ 
return 1; 

+ 


+ 
if 

+ 
return 1; 

+ 


+ 
// operator 

+ 
node>exp[0] = node>exp[pos_op]; 

+ 
node>exp[1] = '\0'; 

+ 


+ 
return 0; 

+ 
} 

+ 


+ 
void traverse_tree_postorder(Node* node) 

+ 
{ 

+ 
if 

+ 
return; 

+ 


+ 
if 

+ 
traverse_tree_postorder(node>left); 

+ 
if 

+ 
traverse_tree_postorder(node>right); 

+ 


+ 
printf(node>exp); 

+ 
} 

+ 


+ 
void traverse_tree_inorder(Node* node) 

+ 
{ 

+ 
if 

+ 
return; 

+ 


+ 
if 

+ 
printf("("); 

+ 


+ 
if 

+ 
traverse_tree_inorder(node>left); 

+ 


+ 
printf(node>exp); 

+ 


+ 
if 

+ 
traverse_tree_inorder(node>right); 

+ 


+ 
if 

+ 
printf(")"); 

+ 
} 

+ 


+ 
void traverse_tree_preorder(Node* node) 

+ 
{ 

+ 
if 

+ 
return; 

+ 


+ 
printf(node>exp); 

+ 


+ 
if 

+ 
traverse_tree_preorder(node>left); 

+ 


+ 
if 

+ 
traverse_tree_preorder(node>right); 

+ 
} 

+ 


+ 
int main() 

+ 
{ 

+ 
Node* root = create_node(); 

+ 


+ 
#if 0 

+ 
strcpy(root>exp, "X =; 

+ 
#else 

+ 
printf("input expression: "); 

+ 
scanf("%[^\n]", root>exp); 

+ 
#endif 

+ 


+ 
remove_space(root>exp); 

+ 


+ 
printf("expression: %s\n", root>exp); 

+ 


+ 
if { 

+ 
fprintf(stderr, "parser error\n"); 

+ 
return 1; 

+ 
} 

+ 


+ 
printf("reverse polish notation: "); 

+ 
traverse_tree_postorder(root); 

+ 
printf("\n"); 

+ 


+ 
printf("infix notation: "); 

+ 
traverse_tree_inorder(root); 

+ 
printf("\n"); 

+ 


+ 
printf("polish notation: "); 

+ 
traverse_tree_preorder(root); 

+ 
printf("\n"); 

+ 


+ 
return 0; 

+ 
} 

+  
+ 
実行例 

+ 
input expression: x = y * 4 + /3 

+ 
expression: x=y*4+(2z)/3 

+ 
reverse polish notation: xy4*2z3/+= 

+ 
infix notation: 

+ 
polish notation: =x+*y4/2z3 

+ 