2009-06-03T00:48:05の更新内容

programming/tips/polish/index.wiki.txt

current previous
1,386 1,11
 
${smdncms:keywords,ポーランド記法,逆ポーランド記法,前置記法,後置記法,中置記法,二分木}
${smdncms:keywords,ポーランド記法,逆ポーランド記法,前置記法,後置記法,中置記法,二分木}
~
${smdncms:tags,lang/c,lang/c#,lang/vb,lang/ruby,algo}
${smdncms:tags,lang/c,algo}
~
*二分木を使った数式のポーランド記法・逆ポーランド記法化
*二分木によるポーランド記法・逆ポーランド記法化
~
#googleadunit
[[二分木を使って数式を逆ポーランド記法にする:http://smdn.invisiblefulmoon.net/ikimasshoy/cpp/polish.html]]のバグ修正版。
~

          
-中置記法を二分木に分解し、ポーランド記法(前置記法)、逆ポーランド記法(後置記法)、中置記法で出力する
+
**二分木を使った逆ポーランド記法化のアルゴリズム
+
***逆ポーランド記法とは
+
一般に人が読むことを前提にした数式は「x = 3 * 2 + 1」の様な形式で表記されるわけですが、コンピュータにとってはこの表記が意外にわかりにくいのです。 コンピュータとしてはこの式を「x32*1+=」と表記してくれるとありがたいのです。 この表記方法を逆ポーランド記法(後置記法)と言います。 対して、最初の記法を中置記法と言います。
+

          
+
例えばこの数式を口に出して読んでみると、「xは3と2を掛けたものに1を足して代入したもの」と言うようになります。 さらに「xは3と2を*したものに1を+して=したもの」と言い換えればわかりやすいかもしれないですね。 プログラミングなどで「x = 3 * 2 + 1;」なんて式を書くと思いますが、実は実行時にはスタックというものを使って逆ポーランド記法的に計算しているわけです。 今回はスタックではなく、二分木を使って数式を逆ポーランド記法に変換してみようと思います。
+

          
+
***二分木とは
+
二分木とは節から二本に枝分かれした木のようなデータ構造です。 この木構造は二分探索などのアルゴリズムでよく用いられるデータ構造です。 二分木の構造として、まず''根(root)''があり、そこから二本に枝分かれします。 枝分かれする元を''節(node)''、枝分かれした先を''葉(leaf)''といいます。 また、葉から見た根本の節を''親(parent)''といい、節から見た''枝(branch)''の先を''子(child)''、同じレベルにある子同士を''兄弟(sibling)''といいます。 さらに、ある節を根としてそれ以下の構造を''部分木(subtree)''とも言います。 図にすると次のような感じです。
+
#ref(0.png,二分木)
+

          
+
実際にプログラミングによって木構造を再現する場合は、次のような構造体を用いることが多いです。 この例では各々の節が持ちうる値はint型であるとしています。
+
#code(c) {{
+
struct Node
+
{
+
    int   data;
+
    Node* left;
+
    Node* right;
+
};
+
}}
+

          
+
つまり、右と左の節へのポインタと、その節自体が持つデータを構造体のメンバとして持つわけです。 もちろんのことですが、葉も節として扱います。
+

          
+
***数式を木構造に変換する。
+
さて、ここからが本題なのですが、変換する式として「X=A*B+C」を例にとって考えてみたいと思います。 参考までに、この式を逆ポーランド記法にすると「XAB*C+=」になります。 まずはじめに、式を木構造に変換する方法を定義します。
+

          
+
:定義1|演算子は2つの部分式(項)を必要とする。 これを木構造で表す場合、演算子の左側の部分式を左の葉、演算子の右側の部分式を右の葉、演算子自体を節に持つこととする。
+

          
+
つまり、式A+Bは次のような木構造になるとします。
+
#ref(1.png,A+Bの木構造)
+

          
+
さらに、式X=A+Bについて考えてみると、演算子=の左の部分式をX、右の部分式をA+Bと考えることができるので、このような木構造になるとします。
+
#ref(2.png,X=A+Bの木構造)
+

          
+
しかし、ここで演算子+を中心として部分式X=Aと部分式Bに分けてしまうこともできます。 このままではどこで分けるかあいまいなので、次の定義を加えます。
+
:定義2|式を木構造で表す場合、最も低い優先順位の演算子を選び出して、その演算子を中心に部分式に分けることとする。
+
:定義3|分けた後の部分式に演算子が含まれる場合は、さらにその節について分割を続ける。
+

          
+
例えば「X=A+B」の場合、A+Bを先に計算し、その結果をXに代入せよと言う意味なので、=は+より優先順位が低いことになります。
+

          
+
この要領で、「X=A*B+C」を1ステップずつ変換していくことにします。 まず、この式の中で最も優先順位が低いのは「=」なので、これを中心に、「X」と「A*B+C」に分割します。
+
#ref(3.png,XとA*B+C)
+

          
+
つぎに、部分式「A*B+C」を木構造に変換します。 この式の中で最も優先順位が低いのは「+」なので、この式は「A*B」と「C」の部分式に分かれます。
+
#ref(4.png,XとA*BとC)
+

          
+
最後に、「A*B」は「*」を中心に「A」と「B」に分割されるので、
+
#ref(5.png,A*BとC)
+

          
+
となり、これで式「X=A*B+C」は無事木構造へと変換されました。
+

          
+
***できあがった木構造から逆ポーランド記法の数式を得る。
+
さて、ここまでで無事木構造が完成しました。 しかし、なぜ木構造にする必要があったかという疑問が生じているのではないでしょうか。 実は木構造からデータを読み出す順序を定義すると簡単に逆ポーランド記法化した式が得られるのです。
+

          
+
まず、木構造からデータを読み出す方法には三種類あります。 ここではその三種類の方法を示します。 木を探索することをトラバースすると言います。 トラバースする方法によって木から得られるデータの順番が変わってきます。
+

          
+
+''先行順序訪問 / 行きがけ順''
+
++ある節にたどり着いたら、その節のデータを読む
+
++その節の左の節のデータを読む。 もし、その節が部分木を持つのであれば1を繰り返す
+
++その節の右の節のデータを読む。 もし、その節が部分木を持つのであれば1を繰り返す
+
++親の節へ戻る
+
+''中間順序訪問 / 通りがけ順''
+
++ある節にたどり着いたら、その節の左の節のデータを読む。 もし、その節が部分木を持つのであれば1を繰り返す
+
++その節のデータを読む
+
++その節の右の節のデータを読む。 もし、その節が部分木を持つのであれば1を繰り返す
+
++親の節へ戻る
+
+''後行順序訪問 / 帰りがけ順''
+
++ある節にたどり着いたら、その節の左の節のデータを読む。 もし、その節が部分木を持つのであれば1を繰り返す
+
++その節の右の節のデータを読む。 もし、その節が部分木を持つのであれば1を繰り返す
+
++その節のデータを読む
+
++親の節へ戻る
+

          
+
ちょっと分かりにくいかと思いますが、簡単に説明すると、一筆書きの要領で木を左からなぞり、行きがけ順では最初に到達したとき、通りがけ順では通り過ぎるとき、帰りがけ順では巡回が終わった後にデータを読むわけです。 この方法通りにトラバースした場合、次のようになります。
+
#ref(6.png,三種類のトラバース方法)
+

          
+
つまり、行きがけ順では「A→B→C」、通りがけ順では「B→A→C」、帰りがけ順では「B→C→A」の順でデータが読み出されます。 ここで、先ほどの式「X=A*B+C」から作った木を各方法でトラバースしてみると、
+
#ref(5.png,X=A*B+C)
+

          
+
行きがけ順では「=X+*ABC」、通りがけ順では「X=A*B+C」、帰りがけ順では「XAB*C+=」のように読み出されます。 帰りがけ順では、ここでの目的である逆ポーランド化された式が読み出されています。 また、トラバース方法を変えて通りがけ順で読み出すと、我々が一般的に使っている中置記法で取得できました。
+

          
+
さて、ここまででアルゴリズムの説明は終わりました。 次は実際にプログラムをみてみましょう。
+

          
+
**Cでの実装
+
ここで紹介するのはCでの実装です。 このプログラムは、
+
-中置記法を二分木に分解し、ポーランド記法(前置記法)、逆ポーランド記法(後置記法)、中置記法で出力
 
-2項演算子のうち、四則演算子(+,-,*,/)、代入演算子(=)が使用可能
-2項演算子のうち、四則演算子(+,-,*,/)、代入演算子(=)が使用可能
 
-演算優先順位の指定に丸括弧()が使用可能
-演算優先順位の指定に丸括弧()が使用可能
~
-式の途中に空白を含むことも可能
-new/delete使用なし
+

          
+
となっています。
+

          
+
まずは部分毎に説明していきます。 プログラム全文は最後に掲載しますので、必要に応じて参照してください。
+

          
+
***mainとNode構造体
+
まずは木構造を表現するためのNode型とmain関数でのプログラム全体の流れを見ていきます。
+

          
+
#code(c){{
+
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 parse_expression(Node* node);
+
void traverse_tree_postorder(Node* node);
+
void traverse_tree_inorder(Node* node);
+
void traverse_tree_preorder(Node* node);
+

          
+
int main()
+
{
+
    Node* root = create_node();
+

          
+
    printf("input expression: ");
+
    scanf("%[^\n]", root->exp);
+

          
+
    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;
+
}
+
}}
+

          
+
Node型は、
+
:left|左の節(部分木)へのポインタ
+
:right|右の節(部分木)へのポインタ
+
:exp|その節の持つ部分式(項)
+

          
+
を保持します。 最大MAX_NODES個(この例では80としました)のNodeをあらかじめ用意しておき、必要になったらcreate_node()関数で取得することにします。 また一つのNodeに格納できる部分式は終端文字を含めて最大MAX_EXP_LEN文字までとします。
+

          
+
main関数の流れは、
+
+分解前の式全体を格納しておくため木構造の根、rootを作成
+
+入力された式をrootにコピー
+
+変換の前準備として、邪魔になる空白を削除(remove_space)
+
+式を木構造に分割(parse_expression)
+
+分割した木構造を
+
++帰りがけ順でトラバースして表示(traverse_tree_postorder)
+
++通りがけ順でトラバースして表示(traverse_tree_inorder)
+
++行きがけ順でトラバースして表示(traverse_tree_preorder)
+

          
+
となります。
+

          
+
***木構造への分割
+
次に、木構造への分割を行う部分の関数を見てみます。
+

          
+
#code(cs){{
+
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;
+
}
+
}}
+

          
+
parse_expressionの流れを簡単に説明すると、
+
+まずget_pos_operatorで最も優先順位の低い演算子の位置を取得する
+
++演算子がなかった場合は、木構造への分割が完了したとして処理を終える
+
+演算子があった場合は、その演算子を中心に左右の部分式へ分割する
+
++ここで、remove_bracketで分割した部分式に含まれる、最も外側の括弧を削除する
+
++分割した部分式について、parse_expressionでさらに分割する
+

          
+
となっています。 parse_expressionは分割した部分式に演算子が含まれる限り、再帰的に呼び出され分割を繰り返します。 get_pos_operatorは、部分式のうち、括弧で括られていない部分で、かつ最も優先順位の低い演算子の位置を返します。
+

          
+
***木構造のトラバース
+
続いて、木構造のトラバースを行う関数を見てみます。
+

          
+
#code(c){{
+
void traverse_tree_postorder(Node* node)
+
{
+
    if
+
        traverse_tree_postorder(node->left);
+
    if
+
        traverse_tree_postorder(node->right);
+

          
+
    printf(node->exp);
+
}
+

          
+
void traverse_tree_inorder(Node* node)
+
{
+
    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)
+
{
+
    printf(node->exp);
+

          
+
    if
+
        traverse_tree_preorder(node->left);
+

          
+
    if
+
        traverse_tree_preorder(node->right);
+
}
+
}}
+

          
+
順に、帰りがけ順、通りがけ順、行きがけ順でトラバースする関数です。 通りがけ順では見やすさのために括弧を付けて表示します。
+

          
+
***プログラム全文
+
最後に、プログラム全文と実行例です。
 

        

        
 
#code(c){{
#code(c){{
 
// gcc polish.c -o polish
// gcc polish.c -o polish
551,6 176,9
 

        

        
 
void traverse_tree_postorder(Node* node)
void traverse_tree_postorder(Node* node)
 
{
{
-
    if
-
        return;
-

          
 
    if
    if
 
        traverse_tree_postorder(node->left);
        traverse_tree_postorder(node->left);
 
    if
    if
561,6 189,9
 

        

        
 
void traverse_tree_inorder(Node* node)
void traverse_tree_inorder(Node* node)
 
{
{
-
    if
-
        return;
-

          
 
    if
    if
 
        printf("(");
        printf("(");
 

        

        
578,6 209,9
 

        

        
 
void traverse_tree_preorder(Node* node)
void traverse_tree_preorder(Node* node)
 
{
{
-
    if
-
        return;
-

          
 
    printf(node->exp);
    printf(node->exp);
 

        

        
 
    if
    if
591,8 225,12
 
{
{
 
    Node* root = create_node();
    Node* root = create_node();
 

        

        
-
#if 0
-
    strcpy(root->exp, "X =;
-
#else
 
    printf("input expression: ");
    printf("input expression: ");
 
    scanf("%[^\n]", root->exp);
    scanf("%[^\n]", root->exp);
-
#endif
 

        

        
 
    remove_space(root->exp);
    remove_space(root->exp);
 

        

        
627,457 265,3
 
polish notation: =x+*y4/-2z3
polish notation: =x+*y4/-2z3
 
}}
}}
 

        

        
+
**他の言語での実装
+
比較して読めるように、Cでの実装に近い記述にしてあります。
+

          
+
***C# 3.0での実装
+
#code(cs){{
+
// gmcs polish.cs && mono polish.exe
+
using System;
+

          
+
class Node {
+
  public string Expression;
+
  public Node Left = null;
+
  public Node Right = null;
+

          
+
  public Node(string expression)
+
  {
+
    this.Expression = expression;
+
  }
+

          
+
  public void Parse()
+
  {
+
    var posOperator = GetOperatorPos(Expression);
+

          
+
    if {
+
      Left = null;
+
      Right = null;
+
      return;
+
    }
+

          
+
    // left-hand side
+
    Left = new Node(RemoveBracket(this.Expression.Substring(0, posOperator)));
+
    Left.Parse();
+

          
+
    // right-hand side
+
    Right = new Node(RemoveBracket(this.Expression.Substring(posOperator + 1)));
+
    Right.Parse();
+

          
+
    // operator
+
    this.Expression = this.Expression.Substring(posOperator, 1);
+
  }
+

          
+
  private static string RemoveBracket(string str)
+
  {
+
    if
+
      return str;
+

          
+
    var nest = 1;
+

          
+
    for {
+
      if
+
        nest++;
+
      else if
+
        nest--;
+

          
+
      if
+
        return str;
+
    }
+

          
+
    if
+
      throw new Exception(string.Format("unbalanced bracket: {0}", str));
+

          
+
    str = str.Substring(1, str.Length - 2);
+

          
+
    if
+
      return RemoveBracket(str);
+
    else
+
      return str;
+
  }
+

          
+
  private static int GetOperatorPos(string expression)
+
  {
+
    if
+
      return -1;
+

          
+
    var pos = -1;
+
    var nest = 0;
+
    var priority = 0;
+
    var lowestPriority = 4;
+

          
+
    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 {
+
        lowestPriority = priority;
+
        pos = i;
+
      }
+
    }
+

          
+
    return pos;
+
  }
+

          
+
  public void TraversePostorder()
+
  {
+
    if
+
      Left.TraversePostorder();
+
    if
+
      Right.TraversePostorder();
+

          
+
    Console.Write(Expression);
+
  }
+

          
+
  public void TraverseInorder()
+
  {
+
    if
+
      Console.Write("(");
+

          
+
    if
+
      Left.TraverseInorder();
+

          
+
    Console.Write(Expression);
+

          
+
    if
+
      Right.TraverseInorder();
+

          
+
    if
+
      Console.Write(")");
+
  }
+

          
+
  public void TraversePreorder()
+
  {
+
    Console.Write(Expression);
+

          
+
    if
+
      Left.TraversePreorder();
+
    if
+
      Right.TraversePreorder();
+
  }
+
}
+

          
+
class Polish {
+
  public static void Main()
+
  {
+
    Console.Write("input expression: ");
+

          
+
    var root = new Node(Console.ReadLine().Replace(" ", string.Empty));
+

          
+
    Console.WriteLine("expression: {0}", root.Expression);
+

          
+
    root.Parse();
+

          
+
    Console.Write("reverse polish notation: ");
+
    root.TraversePostorder();
+
    Console.WriteLine();
+

          
+
    Console.Write("infix notation: ");
+
    root.TraverseInorder();
+
    Console.WriteLine();
+

          
+
    Console.Write("polish notation: ");
+
    root.TraversePreorder();
+
    Console.WriteLine();
+
  }
+
}
+
}}
+

          
+
***VB8での実装
+
#code(vb){{
+
' vbnc polish.vb && mono polish.exe
+
Option Explicit On
+

          
+
Imports System
+

          
+
Class Node
+
  Public Expression As String
+
  Public Left As Node = Nothing
+
  Public Right As Node = Nothing
+

          
+
  Public Sub New(ByVal expression As String)
+
    Me.Expression = expression
+
  End Sub
+

          
+
  Public Sub Parse()
+
    Dim posOperator As Integer = GetOperatorPos(Expression)
+

          
+
    If posOperator < 0 Then
+
      Left = Nothing
+
      Right = Nothing
+
      Return
+
    End If
+

          
+
    ' left-hand side
+
    Left = new Node(RemoveBracket(Me.Expression.Substring(0, posOperator)))
+
    Left.Parse()
+

          
+
    ' right-hand side
+
    Right = new Node(RemoveBracket(Me.Expression.Substring(posOperator + 1)))
+
    Right.Parse()
+

          
+
    ' operator
+
    Me.Expression = Me.Expression.Substring(posOperator, 1)
+
  End Sub
+

          
+
  Private Shared Function RemoveBracket(ByVal str As String) As String
+
    If Not Then Return str
+

          
+
    Dim nest As Integer = 1
+

          
+
    For i As Integer = 1 To str.Length - 1
+
      If str(i) = "(" Then
+
        nest += 1
+
      Else If str(i) = ")" Then
+
        nest -= 1
+
      End If
+

          
+
      If nest = 0 Then Return str
+
    Next
+

          
+
    If nest <> 1 Then Throw New Exception(String.Format("unbalanced bracket: {0}", str))
+

          
+
    str = str.Substring(1, str.Length - 2)
+

          
+
    If str.StartsWith("(") Then
+
      Return RemoveBracket(str)
+
    Else
+
      Return str
+
    End If
+
  End Function
+

          
+
  Private Shared Function GetOperatorPos(ByVal expression As String) As Integer
+
    If String.IsNullOrEmpty(expression) Then Return -1
+

          
+
    Dim pos As Integer = -1
+
    Dim nest As Integer = 0
+
    Dim priority As Integer = 0
+
    Dim lowestPriority As Integer = 4
+

          
+
    For i As Integer = 0 To expression.Length - 1
+
      Select Case expression(i)
+
        Case "=": priority = 1
+
        Case "+": priority = 2
+
        Case "-": priority = 2
+
        Case "*": priority = 3
+
        Case "/": priority = 3
+
        Case "(": nest += 1: Continue For
+
        Case ")": nest -= 1: Continue For
+
        Case Else: Continue For
+
      End Select
+

          
+
      If nest = 0 AndAlso priority <= lowestPriority Then
+
        lowestPriority = priority
+
        pos = i
+
      End If
+
    Next
+

          
+
    Return pos
+
  End Function
+

          
+
  Public Sub TraversePostorder()
+
    If Left  IsNot Nothing Then Left .TraversePostorder()
+
    If Right IsNot Nothing Then Right.TraversePostorder()
+

          
+
    Console.Write(Expression)
+
  End Sub
+

          
+
  Public Sub TraverseInorder()
+
    If Left IsNot Nothing AndAlso Right IsNot Nothing Then Console.Write("(")
+

          
+
    If Left IsNot Nothing Then Left.TraverseInorder()
+

          
+
    Console.Write(Expression)
+

          
+
    If Right IsNot Nothing Then Right.TraverseInorder()
+

          
+
    If Left IsNot Nothing AndAlso Right IsNot Nothing Then Console.Write(")")
+
  End Sub
+

          
+
  Public Sub TraversePreorder()
+
    Console.Write(Expression)
+

          
+
    If Left  IsNot Nothing Then Left .TraversePreorder()
+
    If Right IsNot Nothing Then Right.TraversePreorder()
+
  End Sub
+
End Class
+

          
+
Class Polish
+
  Public Shared Sub Main()
+
    Console.Write("input expression: ")
+

          
+
    Dim root As Node = new Node(Console.ReadLine().Replace(" ", String.Empty))
+

          
+
    Console.WriteLine("expression: {0}", root.Expression)
+

          
+
    root.Parse()
+

          
+
    Console.Write("reverse polish notation: ")
+
    root.TraversePostorder()
+
    Console.WriteLine()
+

          
+
    Console.Write("infix notation: ")
+
    root.TraverseInorder()
+
    Console.WriteLine()
+

          
+
    Console.Write("polish notation: ")
+
    root.TraversePreorder()
+
    Console.WriteLine()
+
  End Sub
+
End Class
+
}}
+

          
+
***Rubyでの実装
+
#code(rb){{
+
#!/usr/bin/env ruby
+

          
+
class Node
+
  @expression
+
  @left
+
  @right
+

          
+
  attr_reader :expression
+

          
+
  def initialize(expression)
+
    @expression = expression
+
  end
+

          
+
  def parse
+
    pos_operator = get_operator_pos(expression)
+

          
+
    if pos_operator < 0
+
      @left = nil
+
      @right = nil
+
      return
+
    end
+

          
+
    # left-hand side
+
    @left = Node.new(remove_bracket(@expression[0, pos_operator]))
+
    @left.parse
+

          
+
    # right-hand side
+
    @right = Node.new(remove_bracket(@expression[pos_operator + 1, @expression.length]))
+
    @right.parse
+

          
+
    # operator
+
    @expression = @expression[pos_operator, 1]
+
  end
+

          
+
  def remove_bracket(s)
+
    return s unless s =~ /^\((.*)\)$/
+

          
+
    removed = $1.dup
+

          
+
    nest = 1
+

          
+
    removed.length.times do |i|
+
      if removed[i, 1] == '('
+
        nest += 1
+
      elsif removed[i, 1] == ')'
+
        nest -= 1
+
      end
+

          
+
      return s if nest == 0
+
    end
+

          
+
    raise("unbalanced bracket: #{s}") unless nest == 1
+

          
+
    if removed[0, 1] == '('
+
      return remove_bracket(removed)
+
    else
+
      return removed
+
    end
+
  end
+

          
+
  def get_operator_pos(exp)
+
    return -1 if exp.to_s.empty?
+

          
+
    pos = -1
+
    nest = 0
+
    priority = 0
+
    lowest_priority = 4
+

          
+
    exp.length.times do |i|
+
      case exp[i, 1]
+
        when '=' then priority = 1
+
        when '+' then priority = 2
+
        when '-' then priority = 2
+
        when '*' then priority = 3
+
        when '/' then priority = 3
+
        when '(' then nest += 1; next
+
        when ')' then nest -= 1; next
+
        else next
+
      end
+

          
+
      if nest == 0 and priority <= lowest_priority
+
        lowest_priority = priority
+
        pos = i
+
      end
+
    end
+

          
+
    return pos
+
  end
+

          
+
  def traverse_postorder
+
    @left .traverse_postorder if @left
+
    @right.traverse_postorder if @right
+

          
+
    print @expression
+
  end
+

          
+
  def traverse_inorder
+
    print '(' if @left and @right
+

          
+
    @left .traverse_inorder if @left
+

          
+
    print @expression
+

          
+
    @right.traverse_inorder if @right
+

          
+
    print ')' if @left and @right
+
  end
+

          
+
  def traverse_preorder
+
    print @expression
+

          
+
    @left .traverse_preorder if @left
+
    @right.traverse_preorder if @right
+
  end
+
end
+

          
+
print 'input expression: '
+

          
+
root = Node.new(gets.chomp.gsub(' ', ''))
+

          
+
print "expression: #{root.expression}\n"
+

          
+
root.parse
+

          
+
print "reverse polish notation: "
+
root.traverse_postorder
+
print "\n"
+

          
+
print "infix notation: "
+
root.traverse_inorder
+
print "\n"
+

          
+
print "polish notation: "
+
root.traverse_preorder
+
print "\n"
+
}}
+

          
+
**文書情報
+
:2009-06-03|アルゴリズムの説明に加筆・修正
+
Cでの実装の説明を修正
+
new/deleteを用いた実装を削除
+
C# 1.0での実装を削除
+
C# 3.0, VB8, Rubyでの実装を追記
+
:2009-03-21|new/deleteを用いない実装を追記
+
:2003-02-08|初版公開