2009-03-21T22: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);
+
 
+
     // left-hand 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;
+
 
+
     // right-hand 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+(2-z)/3
+
 reverse polish notation: xy4*2z-3/+=
+
 infix notation:
+
 polish notation: =x+*y4/-2z3
+