2017-12-23T01:49:59の更新内容

programming/tips/polish/impl_cs/index.wiki.txt

current previous
1,13 1,189
 
${smdncms:set-metadata,title,数式の二分木化・記法変換・計算 (C#)}
${smdncms:set-metadata,title,数式の二分木化・記法変換・計算 (C#)}
 
${smdncms:set-metadata,tags,lang/c#,algo}
${smdncms:set-metadata,tags,lang/c#,algo}
 

                

                
~
以下のコードは[[programming/tips/polish]]で掲載しているアルゴリズムをC#で実装したものです。 コードの詳細な解説等については[[programming/tips/polish#Implementation_C]]を参照してください。 また、他の言語での実装については以下のページをご覧ください。
以下のコードは[[programming/tips/polish#Implementation_C]]で紹介した逆ポーランド記法化のアルゴリズムをC#で実装したものです。
 

                

                
~
#page-tree(programming/tips/polish,include=impl_,exclude=impl_ruby)
#adunit
-

                  
-
#code(cs){{
-
// mcs 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 (posOperator < 0) {
-
      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 (!(str.StartsWith("(") && str.EndsWith(")")))
-
      return str;
-

                  
-
    var nest = 1;
-

                  
-
    for (var i = 1; i < str.Length - 1; i++) {
-
      if (str[i] == '(')
-
        nest++;
-
      else if (str[i] == ')')
-
        nest--;
-

                  
-
      if (nest == 0)
-
        return str;
-
    }
-

                  
-
    if (nest != 1)
-
      throw new Exception(string.Format("unbalanced bracket: {0}", str));
-

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

                  
-
    if (str.StartsWith("("))
-
      return RemoveBracket(str);
-
    else
-
      return str;
-
  }
-

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

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

                  
-
    for (var i = 0; i < expression.Length; i++) {
-
      switch (expression[i]) {
-
        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 (nest == 0 && priority <= lowestPriority) {
-
        lowestPriority = priority;
-
        pos = i;
-
      }
-
    }
 

                

                
~
#adunit
    return pos;
-
  }
-

                  
-
  public void TraversePostorder()
-
  {
-
    if (Left != null)
-
      Left.TraversePostorder();
-
    if (Right != null)
-
      Right.TraversePostorder();
-

                  
-
    Console.Write(Expression);
-
  }
-

                  
-
  public void TraverseInorder()
-
  {
-
    if (Left != null && Right != null)
-
      Console.Write("(");
-

                  
-
    if (Left != null)
-
      Left.TraverseInorder();
-

                  
-
    Console.Write(Expression);
-

                  
-
    if (Right != null)
-
      Right.TraverseInorder();
-

                  
-
    if (Left != null && Right != null)
-
      Console.Write(")");
-
  }
-

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

                  
-
    if (Left != null)
-
      Left.TraversePreorder();
-
    if (Right != null)
-
      Right.TraversePreorder();
-
  }
-

                  
-
  public void Calculate()
-
  {
-
    if (Left != null && Right != null) {
-
      var leftOperand  = Left.calculate();
-
      var rightOperand = Right.calculate();
-

                  
-
      switch (this.expression) {
-
        case "+": return leftOperand + rightOperand;
-
        case "-": return leftOperand - rightOperand;
-
        case "*": return leftOperand * rightOperand;
-
        case "/": return leftOperand / rightOperand;
-
        default:  return 0.0;
-
      }
-
    }
-
    else {
-
      return double.Parse(Expression);
-
    }
-
  }
-
}
-

                  
-
class Polish {
-
  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();
-

                  
-
    Console.WriteLine("calculated result: {0}", root.Calculate());
-
  }
-
}
-
}}
 

                

                
+
なお、本コードは[[misc/license/MIT]]にて公開します。 複製・改変・再配布は、ライセンスに従った形で行ってください。
 

                

                
+
#code(source=../_source/polish.cs,license=mit,copyrightyear=2017)
 

                

                

programming/tips/polish/impl_java/index.wiki.txt

current previous
1,13 1,185
 
${smdncms:set-metadata,title,数式の二分木化・記法変換・計算 (Java)}
${smdncms:set-metadata,title,数式の二分木化・記法変換・計算 (Java)}
 
${smdncms:set-metadata,tags,lang/java,algo}
${smdncms:set-metadata,tags,lang/java,algo}
 

                

                
~
以下のコードは[[programming/tips/polish]]で掲載しているアルゴリズムをJavaで実装したものです。 コードの詳細な解説等については[[programming/tips/polish#Implementation_C]]を参照してください。 また、他の言語での実装については以下のページをご覧ください。
以下のコードは[[programming/tips/polish#Implementation_C]]で紹介した逆ポーランド記法化のアルゴリズムをJavaで実装したものです。
 

                

                
~
#page-tree(programming/tips/polish,include=impl_,exclude=impl_ruby)
#adunit
-

                  
-
#code(java){{
-
// javac Polish.java && java Polish
-
import java.io.*;
-

                  
-
class Node {
-
  public String expression;
-
  public Node left = null;
-
  public Node right = null;
-

                  
-
  public Node(String expression) {
-
    this.expression = expression;
-
  }
-

                  
-
  public void parse() {
-
    int posOperator = getOperatorPos(expression);
-

                  
-
    if (posOperator < 0) {
-
      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, posOperator + 1);
-
  }
-

                  
-
  private static String removeBracket(String str) {
-
    if (!(str.startsWith("(") && str.endsWith(")")))
-
      return str;
-

                  
-
    int nest = 1;
-

                  
-
    for (int i = 1; i < str.length() - 1; i++) {
-
      if (str.charAt(i) == '(')
-
        nest++;
-
      else if (str.charAt(i) == ')')
-
        nest--;
-

                  
-
      if (nest == 0)
-
        return str;
-
    }
-

                  
-
    if (nest != 1)
-
      throw new RuntimeException("unbalanced bracket: " + str);
-

                  
-
    str = str.substring(1, str.length() - 1);
-

                  
-
    if (str.startsWith("("))
-
      return removeBracket(str);
-
    else
-
      return str;
-
  }
-

                  
-
  private static int getOperatorPos(String expression) {
-
    if (expression == null || expression.length() == 0)
-
      return -1;
-

                  
-
    int pos = -1;
-
    int nest = 0;
-
    int priority = 0;
-
    int lowestPriority = 4;
-

                  
-
    for (int i = 0; i < expression.length(); i++) {
-
      switch (expression.charAt(i)) {
-
        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 (nest == 0 && priority <= lowestPriority) {
-
        lowestPriority = priority;
-
        pos = i;
-
      }
-
    }
-

                  
-
    return pos;
-
  }
 

                

                
~
#adunit
  public void traversePostorder() {
-
    if (left != null)
-
      left.traversePostorder();
-
    if (right != null)
-
      right.traversePostorder();
-

                  
-
    System.out.print(expression);
-
  }
-

                  
-
  public void traverseInorder() {
-
    if (left != null && right != null)
-
      System.out.print("(");
-

                  
-
    if (left != null)
-
      left.traverseInorder();
-

                  
-
    System.out.print(expression);
-

                  
-
    if (right != null)
-
      right.traverseInorder();
-

                  
-
    if (left != null && right != null)
-
      System.out.print(")");
-
  }
-

                  
-
  public void traversePreorder() {
-
    System.out.print(expression);
-

                  
-
    if (left != null)
-
      left.traversePreorder();
-
    if (right != null)
-
      right.traversePreorder();
-
  }
-

                  
-
  public double calculate() {
-
    if (left != null && right != null) {
-
      double leftOperand  = left.calculate();
-
      double rightOperand = right.calculate();
-

                  
-
      if (expression.equals("+"))
-
        return leftOperand + rightOperand;
-
      else if (expression.equals("-"))
-
        return leftOperand - rightOperand;
-
      else if (expression.equals("*"))
-
        return leftOperand * rightOperand;
-
      else if (expression.equals("/"))
-
        return leftOperand / rightOperand;
-
      else
-
        return 0.0;
-
    }
-
    else {
-
      return Double.parseDouble(expression);
-
    }
-
  }
-
}
-

                  
-
public class Polish {
-
  public static void main(String[] args) throws IOException {
-
    BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
-

                  
-
    System.out.print("input expression: ");
-

                  
-
    Node root = new Node(r.readLine().replace(" ", ""));
-

                  
-
    System.out.println("expression: " + root.expression);
-

                  
-
    root.parse();
-

                  
-
    System.out.print("reverse polish notation: ");
-
    root.traversePostorder();
-
    System.out.println();
-

                  
-
    System.out.print("infix notation: ");
-
    root.traverseInorder();
-
    System.out.println();
-

                  
-
    System.out.print("polish notation: ");
-
    root.traversePreorder();
-
    System.out.println();
-

                  
-
    System.out.println("calculated result: " + root.calculate());
-
  }
-
}
-
}}
 

                

                
+
なお、本コードは[[misc/license/MIT]]にて公開します。 複製・改変・再配布は、ライセンスに従った形で行ってください。
 

                

                
+
#code(source=../_source/Polish.java,license=mit,copyrightyear=2017)
 

                

                

programming/tips/polish/impl_javascript/index.wiki.txt

current previous
1,13 0,0
+
${smdncms:set-metadata,title,数式の二分木化・記法変換・計算 (JavaScript)}
+
${smdncms:set-metadata,tags,lang/javascript,algo}
+

                  
+
以下のコードは[[programming/tips/polish]]で掲載しているアルゴリズムをJavaScriptで実装したものです。 コードの詳細な解説等については[[programming/tips/polish#Implementation_C]]、ブラウザ上で動作するサンプルについては[[programming/tips/polish#ConversionDemo]]を参照してください。 また、他の言語での実装については以下のページをご覧ください。
+

                  
+
#page-tree(programming/tips/polish,include=impl_,exclude=impl_ruby)
+

                  
+
#adunit
+

                  
+
なお、本コードは[[misc/license/MIT]]にて公開します。 複製・改変・再配布は、ライセンスに従った形で行ってください。
+

                  
+
#code(source=../_source/polish.js,license=mit,copyrightyear=2017)
+

                  

programming/tips/polish/impl_python/index.wiki.txt

current previous
1,13 0,0
+
${smdncms:set-metadata,title,数式の二分木化・記法変換・計算 (Python)}
+
${smdncms:set-metadata,tags,lang/python,algo}
+

                  
+
以下のコードは[[programming/tips/polish]]で掲載しているアルゴリズムをPythonで実装したものです。 コードの詳細な解説等については[[programming/tips/polish#Implementation_C]]を参照してください。 また、他の言語での実装については以下のページをご覧ください。
+

                  
+
#page-tree(programming/tips/polish,include=impl_,exclude=impl_ruby)
+

                  
+
#adunit
+

                  
+
なお、本コードは[[misc/license/MIT]]にて公開します。 複製・改変・再配布は、ライセンスに従った形で行ってください。
+

                  
+
#code(python,source=../_source/polish.py,license=mit,copyrightyear=2017)
+

                  

programming/tips/polish/impl_vb/index.wiki.txt

current previous
1,13 1,171
 
${smdncms:set-metadata,title,数式の二分木化・記法変換・計算 (Visual Basic)}
${smdncms:set-metadata,title,数式の二分木化・記法変換・計算 (Visual Basic)}
 
${smdncms:set-metadata,tags,lang/vb,algo}
${smdncms:set-metadata,tags,lang/vb,algo}
 

                

                
~
以下のコードは[[programming/tips/polish]]で掲載しているアルゴリズムをVisual Basicで実装したものです。 コードの詳細な解説等については[[programming/tips/polish#Implementation_C]]を参照してください。 また、他の言語での実装については以下のページをご覧ください。
以下のコードは[[programming/tips/polish#Implementation_C]]で紹介した逆ポーランド記法化のアルゴリズムをVisual Basicで実装したものです。
 

                

                
~
#page-tree(programming/tips/polish,include=impl_,exclude=impl_ruby)
#adunit
-

                  
-
#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 (str.StartsWith("(") AndAlso str.EndsWith(")")) Then Return str
-

                  
-
    Dim nest As Integer = 1
-

                  
-
    For i As Integer = 1 To str.Length - 2
-
      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
 

                

                
~
#adunit
    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
-

                  
-
  Public Function Calculate() As Double
-
    If Left IsNot Nothing AndAlso Right IsNot Nothing Then
-
      Dim leftOperand  As Double = Left.Calculate()
-
      Dim rightOperand As Double = Right.Calculate()
-

                  
-
      Select Case Expression
-
        Case "+": Return leftOperand + rightOperand
-
        Case "-": Return leftOperand - rightOperand
-
        Case "*": Return leftOperand * rightOperand
-
        Case "/": Return leftOperand / rightOperand
-
        Case Else: Return 0.0
-
      End Select
-
    Else
-
      Return Double.Parse(Expression)
-
    End If
-
  End Function
-
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()
-

                  
-
    Console.WriteLine("calculated result: {0}", root.Calculate())
-
  End Sub
-
End Class
-
}}
 

                

                
+
なお、本コードは[[misc/license/MIT]]にて公開します。 複製・改変・再配布は、ライセンスに従った形で行ってください。
 

                

                
+
#code(source=../_source/polish.vb,license=mit,copyrightyear=2017)
 

                

                

programming/tips/polish/index.wiki.txt

current previous
2,8 2,6
 
${smdncms:set-metadata,keywords,ポーランド記法,逆ポーランド記法,前置記法,後置記法,中置記法,二分木}
${smdncms:set-metadata,keywords,ポーランド記法,逆ポーランド記法,前置記法,後置記法,中置記法,二分木}
 
${smdncms:set-metadata,tags,lang/c,algo}
${smdncms:set-metadata,tags,lang/c,algo}
 

                

                
+
[[逆ポーランド記法とは>#SummaryReversePolishNotation]]何か、[[数式を逆ポーランド記法化する>#ConversionDemo]]とどのようになるか、また[[二分木を使って数式を逆ポーランド記法化するアルゴリズム>#Algorithm]]と[[C言語による実装>#Implementation_C]]を紹介します。
+

                  
 
*逆ポーランド記法とは [#SummaryReversePolishNotation]
*逆ポーランド記法とは [#SummaryReversePolishNotation]
 
一般に人が読むことを前提にした数式は``x = 3 * 2 + 1``の様な形式で表記されますが、演算の順序などを考えるとコンピュータにとってはこの表記は扱いにくいものです。 コンピュータとしてはこの式は``x32*1+=``と表記されていたほうが扱いやすくなります。 このような形式での表記が逆ポーランド記法です。
一般に人が読むことを前提にした数式は``x = 3 * 2 + 1``の様な形式で表記されますが、演算の順序などを考えるとコンピュータにとってはこの表記は扱いにくいものです。 コンピュータとしてはこの式は``x32*1+=``と表記されていたほうが扱いやすくなります。 このような形式での表記が逆ポーランド記法です。
 

                

                
21,28 19,16
 
    <tr>
    <tr>
 
      <th>変換する数式</th>
      <th>変換する数式</th>
 
      <td>
      <td>
-
        <input type="text" id="polish_demo_input" value="" size="25" />
-
        <input type="button" value="変換" onclick="polish_demo_convert();"/>
-
        <input type="reset" value="クリア"/>
 
        <div>
        <div>
~
          <input type="text" id="polish_demo_input" value="" size="25" list="polish_demo_expressions" />
        記入例
~
          <datalist id="polish_demo_expressions">
        <ul>
~
            <option value="x = 3 * 2 + 1" />
          <li><code class="inline">x = a * (b + c)</code></li>
~
            <option value="x = a * (b + c)" />
          <li><code class="inline">2+5*3-4</code></li>
~
            <option value="2+5*3-4" />
          <li><code class="inline">1+4*2+(7-3)/2</code></li>
~
            <option value="1+4*2+(7-3)/2" />
        </ul>
+
            <option value="1 + 2 + X = Y + 3 + 4" />
+
          </datalist>
+
          <input type="button" value="変換" onclick="polish_demo_convert();"/>
+
          <input type="reset" value="クリア"/>
+
        </div>
+
        <div id="polish_demo_result_error"></div>
+
        <div>
+
          記入例
+
          <ul>
+
            <li><code class="inline">x = 3 * 2 + 1</code></li>
+
            <li><code class="inline">x = a * (b + c)</code></li>
+
            <li><code class="inline">2+5*3-4</code></li>
+
            <li><code class="inline">1+4*2+(7-3)/2</code></li>
+
            <li><code class="inline">1 + 2 + X = Y + 3 + 4</code></li>
+
          </ul>
 
        </div>
        </div>
 
      </td>
      </td>
 
    </tr>
    </tr>
74,108 60,195
 
</form>
</form>
 
}}
}}
 

                

                
~
#javascript(polish_demo_implementation,source=_source/polish.js)
#javascript(polish_demo_code,noscript=実行するにはJavaScriptを有効にしてください){{
-
function Node(expression)
-
{
-
  this.expression = expression;
-
  this.left = null;
-
  this.right = null;
-

                  
-
  this.parse = function()
-
  {
-
    var posOperator = this.getOperatorPos(this.expression);
-

                  
-
    if (posOperator < 0) {
-
      this.left = null;
-
      this.right = null;
-
      return;
-
    }
 

                

                
~
#javascript(polish_demo_runner,noscript=実行するにはJavaScriptを有効にしてください){{
    // left-hand side
~
"use strict"
    this.left = new Node(this.removeBracket(this.expression.substr(0, posOperator)));
-
    this.left.parse();
 

                

                
~
class PseudoStdOut {
    // right-hand side
~
  constructor()
    this.right = new Node(this.removeBracket(this.expression.substr(posOperator + 1)));
-
    this.right.parse();
-

                  
-
    // operator
-
    this.expression = this.expression.substr(posOperator, 1);
-
  };
-

                  
-
  this.removeBracket = function(str)
 
  {
  {
~
    this.buffer = "";
    if (!(str.indexOf('(') == 0 && str.lastIndexOf(')') == str.length - 1))
~
  }
      return str;
-

                  
-
    var nest = 1;
-

                  
-
    for (var i = 1; i < str.length - 1; i++) {
-
      if (str[i] == '(')
-
        nest++;
-
      else if (str[i] == ')')
-
        nest--;
-

                  
-
      if (nest == 0)
-
        return str;
-
    }
-

                  
-
    if (nest != 1)
-
      throw 'unbalanced bracket:' + str;
-

                  
-
    str = str.substr(1, str.length - 2)
-

                  
-
    if (str.indexOf('(') == 0)
-
      return this.removeBracket(str);
-
    else
-
      return str;
-
  };
 

                

                
~
  write(val)
  this.getOperatorPos = function(expression)
 
  {
  {
~
    this.buffer += val;
    if (!expression)
~
  }
      return -1;
~
}

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

                  
-
    for (var i = 0; i < expression.length; i++) {
-
      switch (expression[i]) {
-
        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 (nest == 0 && priority <= lowestPriority) {
-
        lowestPriority = priority;
-
        pos = i;
-
      }
-
    }
-

                  
-
    return pos;
-
  };
 

                

                
~
class DemoNode extends Node {
  this.traversePostorder = function()
+
  constructor(expression)
 
  {
  {
~
    super(expression);
    var ret = '';
~
  }

                  
-
    if (this.left)
-
      ret += this.left.traversePostorder();
-
    if (this.right)
-
      ret += this.right.traversePostorder();
-

                  
-
    return ret + this.expression;
-
  };
 

                

                
~
  getPostorerNotation()
  this.traverseInorder = function()
 
  {
  {
~
    let stdout = new PseudoStdOut();
    var ret = '';
-

                  
-
    if (this.left && this.right)
-
      ret += '(';
 

                

                
~
    this.traversePostorder(stdout);
    if (this.left)
-
      ret += this.left.traverseInorder();
 

                

                
~
    return stdout.buffer;
    ret += this.expression;
+
  }
 

                

                
~
  getInorderNotation()
    if (this.right)
~
  {
      ret += this.right.traverseInorder();
+
    let stdout = new PseudoStdOut();
 

                

                
~
    this.traverseInorder(stdout);
    if (this.left && this.right)
-
      ret += ')';
 

                

                
~
    return stdout.buffer;
    return ret;
~
  }
  };
 

                

                
~
  getPreorderNotation()
  this.traversePreorder = function()
 
  {
  {
~
    let stdout = new PseudoStdOut();
    var ret = this.expression;
 

                

                
~
    this.traversePreorder(stdout);
    if (this.left)
-
      ret += this.left.traversePreorder();
-
    if (this.right)
-
      ret += this.right.traversePreorder();
 

                

                
~
    return stdout.buffer;
    return ret;
~
  }
  };
-

                  
-
  this.calculate = function()
-
  {
-
    if (this.left && this.right) {
-
      var left_operand  = this.left.calculate();
-
      var right_operand = this.right.calculate();
-

                  
-
      switch (this.expression) {
-
        case "+": return left_operand + right_operand;
-
        case "-": return left_operand - right_operand;
-
        case "*": return left_operand * right_operand;
-
        case "/": return left_operand / right_operand;
-
        default:  return 0.0;
-
      }
-
    }
-
    else {
-
      return parseFloat(this.expression);
-
    }
-
  };
 
}
}
 

                

                
 
function polish_demo_convert()
function polish_demo_convert()
 
{
{
+
  $('#polish_demo_result_postorder').val('');
+
  $('#polish_demo_result_inorder').val('');
+
  $('#polish_demo_result_preorder').val('');
+
  $('#polish_demo_result_calculate').val('');
+
  $('#polish_demo_result_error').html('<pre></pre>');
+

                  
 
  try {
  try {
~
    let expression = $('#polish_demo_input').val();
    var expression = $('#polish_demo_input').val();
~
    let root = new DemoNode(expression.replace(/\s+/g, ''));
    var root = new Node(expression.replace(/\s+/g, ''));
 

                

                
 
    root.parse();
    root.parse();
 

                

                
~
    $('#polish_demo_result_postorder').val(root.getPostorerNotation());
    $('#polish_demo_result_postorder').val(root.traversePostorder());
~
    $('#polish_demo_result_inorder').val(root.getInorderNotation());
    $('#polish_demo_result_inorder').val(root.traverseInorder());
~
    $('#polish_demo_result_preorder').val(root.getPreorderNotation());
    $('#polish_demo_result_preorder').val(root.traversePreorder());
~

                  
    $('#polish_demo_result_calculate').val(root.calculate());
+
    if (root.calculate()) {
+
      $('#polish_demo_result_calculate').val(root.expression);
+
      $('#polish_demo_result_error').html('<pre style="color:green;">expression calculated</pre>');
+
    }
+
    else {
+
      $('#polish_demo_result_calculate').val(root.getInorderNotation());
+
      $('#polish_demo_result_error').html('<pre style="color:orange;">expression not calculated</pre>');
+
    }
 
  }
  }
 
  catch (e) {
  catch (e) {
~
    $('#polish_demo_result_calculate').val('');
    alert(e);
+
    $('#polish_demo_result_error').html('<pre style="color:red;">' + e + '</pre>');
 
  }
  }
 
}
}
 

                

                
 
$(function(){
$(function(){
 
  // set default expression
  // set default expression
~
  $('#polish_demo_input').val('x = 3 * 2 + 1');
  $('#polish_demo_input').val('x = a * (b + c)');
 
});
});
 
}}
}}
 

                

                
 
#adunit
#adunit
 

                

                
~
このデモでできる変換処理と制限事項については[[Cでの実装の項>#Implementation_C]]をご覧ください。
変換アルゴリズムについてはこの後解説します。 なお、このデモで出来る変換処理については[[Cでの実装の項>#Implementation_C]]をご覧ください。
 

                

                
 

                

                
 
*二分木を使った逆ポーランド記法化のアルゴリズム [#Algorithm]
*二分木を使った逆ポーランド記法化のアルゴリズム [#Algorithm]
~
逆ポーランド記法化を行うアルゴリズムには様々なものがあり、一例として[[スタック(stack)>programming/netfx/collections/2_generic_5_1_stack#Stack]]を使うものがありますが、ここではスタックではなく二分木を使って数式を逆ポーランド記法に変換する方法について解説します。 また、二分木に変換した数式を使って数式の計算を行う方法についても解説します。
逆ポーランド記法化を行うアルゴリズムには様々なものがあり、一例としてスタックを使うものがありますが、ここではスタックではなく二分木を使って数式を逆ポーランド記法に変換する方法について解説します。 また、二分木に変換した数式を使って数式の計算を行う方法についても解説します。
 

                

                
 

                

                
 

                

                
 
**二分木とは [#Algorithm_BinaryTree]
**二分木とは [#Algorithm_BinaryTree]
~
''二分木(binary tree)''とは節から''二本に枝分かれ''した''木(tree)''のようなデータ構造です。 この木構造は二分探索などのアルゴリズムでよく用いられるデータ構造です。
''二分木(binary tree)''とは節から二本に枝分かれした''木(tree)''のようなデータ構造です。 この木構造は二分探索などのアルゴリズムでよく用いられるデータ構造です。
 

                

                
 
二分木の構造として、まず''根(root)''があり、そこから二本に枝分かれします。 枝分かれする元を''節(node)''、枝分かれした先を''葉(leaf)''といいます。 根や葉を区別せずに全てまとめてノードと呼ぶこともあります。
二分木の構造として、まず''根(root)''があり、そこから二本に枝分かれします。 枝分かれする元を''節(node)''、枝分かれした先を''葉(leaf)''といいます。 根や葉を区別せずに全てまとめてノードと呼ぶこともあります。
 

                

                
184,7 257,7
 
二分岐の一例と構造上の名称を図にすると次のようになります。
二分岐の一例と構造上の名称を図にすると次のようになります。
 
#image(0.png,nopopup,二分木)
#image(0.png,nopopup,二分木)
 

                

                
~
実際にプログラミングによって二分木のデータ構造を表現する場合は、次のような構造体を用いることが多いです。 この例では各々のノードが持ちうる値は``int``型であるとしています。
実際にプログラミングによって二分木を再現する場合は、次のような構造体を用いることが多いです。 この例では各々のノードが持ちうる値は``int``型であるとしています。
 
#code(c) {{
#code(c) {{
 
struct Node
struct Node
 
{
{
199,7 272,7
 

                

                
 

                

                
 
**数式を二分木に変換する [#Algorithm_ParseExpression]
**数式を二分木に変換する [#Algorithm_ParseExpression]
~
数式を逆ポーランド記法化する前の下準備としてに、式を二分木に変換します。 なぜ二分木にする必要があるのか、どのような利点があるのかという点については後述するとして、まずは変換する式として``X=A*B+C``を例にとって二分木に変換する方法を考えていきます。 まずはじめに、式を二分木に変換する方法を次のように定義します。
数式を逆ポーランド記法化する前の下準備としてに、式を二分木に変換します。 なぜ二分木にする必要があるのかという点については後述するとして、まずは変換する式として``X=A*B+C``を例にとって二分木に変換する方法を考えてみたいと思います。 まずはじめに、式を二分木に変換する方法を次のように定義します。
 

                

                
 
:ルール1|演算子は2つの部分式(項)を必要とする。 これを二分木で表す場合、演算子の左側の部分式を左の子ノード、演算子の右側の部分式を右の子ノード、演算子自体をノード自身に持つこととする。
:ルール1|演算子は2つの部分式(項)を必要とする。 これを二分木で表す場合、演算子の左側の部分式を左の子ノード、演算子の右側の部分式を右の子ノード、演算子自体をノード自身に持つこととする。
 

                

                
209,9 282,7
 
さらに、式``X=A+B``について考えてみると、演算子``=``の左の部分式を``X``、右の部分式を``A+B``と考えることができるので、このような二分木になるものとします。
さらに、式``X=A+B``について考えてみると、演算子``=``の左の部分式を``X``、右の部分式を``A+B``と考えることができるので、このような二分木になるものとします。
 
#image(2.png,nopopup,X=A+Bの二分木)
#image(2.png,nopopup,X=A+Bの二分木)
 

                

                
~
しかし、単純に演算子の左側・右側で部分式に分けるというルールでは、式``X=A+B``は演算子``+``を中心として部分式``X=A``と部分式``B``に分けてしまうこともできてしまいます。 式``1+2*3``の場合も同様に、「部分式``1+2``演算子``*``部分式``3``」あるいは「部分式``1``演算子``+``部分式``2*3``」のどちらにも考えることができてしまいます。
しかし、単純に演算子の左側・右側で部分式に分けるというルールでは、式``X=A+B``は演算子``+``を中心として部分式``X=A``と部分式``B``に分けてしまうこともできてします。 このままでは式に複数の演算子が含まれている場合にどの演算子で分けるかあいまいなので、次のルールを加えます。
+

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

                

                
233,7 304,7
 
**二分木から逆ポーランド記法化した数式を得る [#Algorithm_TraverseBinaryTree]
**二分木から逆ポーランド記法化した数式を得る [#Algorithm_TraverseBinaryTree]
 
ここまでの手順で式を二分木にすることができました。 しかし、なぜ二分木にするのかという点については理由を明らかにしていませんでした。 式を二分木にした理由は、二分木からデータを読み出す順序を定義すると簡単に逆ポーランド記法化した式が得られるためです。
ここまでの手順で式を二分木にすることができました。 しかし、なぜ二分木にするのかという点については理由を明らかにしていませんでした。 式を二分木にした理由は、二分木からデータを読み出す順序を定義すると簡単に逆ポーランド記法化した式が得られるためです。
 

                

                
~
まず、二分木からデータを読み出す方法には次の三種類があります。 ノードを巡回(''traverse'')してデータを読み出す順序によって、木から得られるデータの順番も変わってきます。 三種類の巡回順序はそれぞれ次のとおりです。
まず、二分木からデータを読み出す方法には三種類あります。 ここではその三種類の方法を示します。 木を探索することをトラバースすると言います。 トラバースする方法によって木から得られるデータの順番が変わってきます。
 

                

                
 
+''先行順序訪問 / 行きがけ順 (preorder traversal)''
+''先行順序訪問 / 行きがけ順 (preorder traversal)''
 
++あるノードNにたどり着いたら、そのノードNのデータを読む
++あるノードNにたどり着いたら、そのノードNのデータを読む
251,21 322,11
 
++ノードNのデータを読む
++ノードNのデータを読む
 
++ノードNの親ノードへ戻る
++ノードNの親ノードへ戻る
 

                

                
~
言葉での表現では分かりにくいかと思いますが、上記の手順を図に表すと次のようになります。
ちょっと分かりにくいかと思いますが、上記の手順を端的に表すと次のようになります。 一筆書きの要領で木を左からなぞって巡回していき、行きがけ順では''ノードに到達したとき''、通りがけ順では左の子ノードの巡回が終わって''右の子ノードに移動するとき''、帰りがけ順では右の子ノードの''巡回が終わったとき''ノードのデータを読むようにします。 この方法通りにトラバースした場合、次のようになります。
 

                

                
~
#column(行きがけ順でのノードの参照順序)
&image(6-1.png,nopopup,先行順序訪問/行きがけ順でのノードの参照順序); &image(6-2.png,nopopup,中間順序訪問/通りがけ順でのノードの参照順序); &image(6-3.png,nopopup,後行順序訪問/帰りがけ順でのノードの参照順序);
+
#image(6-1.png,nopopup,先行順序訪問/行きがけ順でのノードの参照順序)
+
#column(通りがけ順でのノードの参照順序)
+
#image(6-2.png,nopopup,中間順序訪問/通りがけ順でのノードの参照順序)
+
#column(帰りがけ順でのノードの参照順序)
+
#image(6-3.png,nopopup,後行順序訪問/帰りがけ順でのノードの参照順序)
+
#column-end
 

                

                
~
どの巡回順序でも、''一筆書きの要領''で木を左からなぞって巡回するところは共通していますが、ノードのデータを読むタイミングは異なります。 行きがけ順では''ノードに到達したとき''、通りがけ順では左の子ノードの巡回が終わって''右の子ノードに移動するとき''、帰りがけ順では右の子ノードの''巡回が終わったとき''にノードのデータを読むようにします。
つまり、行きがけ順では「N→L→R」、通りがけ順では「L→N→R」、帰りがけ順では「L→R→N」の順でデータが読み出されることになります。 ここで、先ほどの式``X=A*B+C``から作った木を各方法でトラバースしてみると、
+

                  
+
つまり、行きがけ順ではN→L→R、通りがけ順ではL→N→R、帰りがけ順ではL→R→Nの順でデータが読み出されることになります。 個々のノードがさらに子ノードを持つ場合も、同じ手順で巡回します。
+

                  
+
さて、先ほどの式``X=A*B+C``から作った二分木に対して、上記の3つの順序を当てはめて巡回しデータを読み出してみます。
 

                

                
 
#image(7.png,nopopup,X=A*B+C)
#image(7.png,nopopup,X=A*B+C)
 

                

                
276,174 337,645
 

                

                
 

                

                
 
**二分木化した数式を使って計算を行う [#Algorithm_CalculateExpressionTree]
**二分木化した数式を使って計算を行う [#Algorithm_CalculateExpressionTree]
~
ここまででは、式から作成した二分木を巡回することで式を様々な記法に変換する方法について解説してきました。 ここからは作成した二分木を使って式の計算を行う方法を考えていきます。
ここまででは式から作成した二分木を探索(トラバース)することで式を様々な記法に変換する方法について解説してきましたが、ここからは作成した二分木を使って式の計算を行う方法をみていきます。 ここでは、等号や変数(記号)を含む場合については考えず、簡単化のため定数(数字)と四則演算子のみを含む式の計算を行う方法を考えます。 以下、計算する式として``2+5*3-4``を例にとり、最終的な計算結果として```13```を得るための方法をみていきます。
+

                  
+
ここでは、等号``=``や変数(記号)を含む場合については考えず、簡単化のため定数(数字)と四則演算子のみを含む式の計算を行う方法を考えます。 以下、計算する式として``2+5*3-4``を例にとり、最終的な計算結果として```13```を得るための方法を考えていきます。
 

                

                
~
まず、式``2+5*3-4``を計算する場合、どのような手順をとれば正しい答えが得られるかを考えます。 式``2+5*3-4``は、値``2``と部分式``5*3-4``の演算結果を足したもの(``+``)と見ることができます。 式全体を計算するには、先にこの部分式``5*3-4``がどのような値となるかを計算する必要があります。 同様に、式``5*3-4``は部分式``5*3``の演算結果から値``4``を引いたもの(``-``)と見ることができます。 この部分式``5*3``の結果を求めれば式``5*3-4``の値も求まり、式``2+5*3-4``全体を計算できることになります。
まず、式``2+5*3-4``を計算する場合、どのような手順をとれば正しい答えが得られるかを考えます。 式``2+5*3-4``は、値``2``と部分式``5*3-4``の演算結果を足したもの(``+``)と見ることができます。 式全体を計算するには、先に部分式``5*3-4``がどのような値となるかを計算する必要があります。 同様に、式``5*3-4``は部分式``5*3``の演算結果から値``4``を引いたもの(``-``)と見ることができます。 この部分式``5*3``の結果を求めれば式``5*3-4``の値も求まり、式``2+5*3-4``全体を計算できることになります。
 

                

                
~
つまり、まず式全体を左項・右項と演算子のみの部分式になるまで分割したのち、それぞれの部分式の演算結果を求めていくことにより、最終的に式全体の計算結果を得ることができます。 式全体を部分式に分割する手順は、[[式を二分木に変換する際に使った手順>#Algorithm_ParseExpression]]をそのまま適用することができます。 ここからは、左記のことを踏まえて、二分木に分割した式から計算結果を求める手順を考えてみます。
つまり、まず式を左項・右項と演算子のみの部分式になるまで分割したのち、それぞれの部分式の演算結果を求めていくことにより最終的に式全体の計算結果を得ることができます。 部分式に分割する手順は、先に式を二分木に変換する際に使った手順をそのまま適用することができます。 そこで、この計算手順を二分木にあてはめて考えてみます。
 

                

                
~
まず、先に使った手順に従って式``2+5*3-4``を二分木に変換すると次の図のようになります。 演算子ノードの子ノードに演算の対象となる部分式または値(''被演算子'', ''operand'')が位置している点、また演算子の優先順位に従って式の分割を行ったため優先度の高い式が二分木の先端部分に位置している点に着目してください。
まず、先に使った手順に従って式``2+5*3-4``を二分木に変換すると次の図のようになります。 演算子ノードの子ノードに演算の対象となる部分式または値(オペランド)が位置している点、また演算子の優先順位に従って式の分割を行ったため優先度の高い式が二分木の先端部分に位置している点に着目してください。
 

                

                
 
#image(8-1.png,nopopup,二分木化した式「2+5*3-4」)
#image(8-1.png,nopopup,二分木化した式「2+5*3-4」)
 

                

                
~
二分木化した式では、すでに左項・右項と演算子のみに分割された状態になっています。 この二分木の末端部分から順に値を求めていけば、最終的に木全体の値、すなわち式の計算結果を得ることができます。 つまり手順としては、
二分木化した式では、すでに左項・右項と演算子のみに分割された状態になっています。 従って、この二分木に対して、
 

                

                
~
+二分木を根(root)から順に巡回し
+二分木を根(root)から順に見ていき
~
+ノードに設定されている演算子に従って左の子ノード(部分式の左項)と右の子ノード(部分式の右項)の値を演算する
+ノードに設定されている演算子に従って左項(左の子ノード)と右項(右の子ノード)の値を演算する
~
+このとき、左または右の子ノードがさらに子ノードを持っている場合(項が値そのものではなく未計算の部分式の場合)は、先に2の操作を繰り返して子ノードの値(部分式の演算結果)を求める
+このとき、項が部分式の場合(左または右の子ノードがさらに子ノードを持っている場合)は、先に2の操作を繰り返して部分式の演算結果を求める
 

                

                
~
という操作を行うことにより、計算結果を得ることができます。
という操作を行うことにより、最終的に式全体の値、すなわち式の計算結果を得ることができます。 この操作を、式``2+5*3-4``の二分木に対して行なっていくと次のようになります。
+

                  
+
この操作を、式``2+5*3-4``の二分木に対して行なっていくと次のようになります。
 

                

                
 
#image(8-2.png,nopopup,二分木化した式の計算 step1)
#image(8-2.png,nopopup,二分木化した式の計算 step1)
 

                

                
~
まず、二分木の根を見ると、式は演算子が``+``で左項は値``2``、右項は子ノードを持っているため部分式となります。 この部分式``5*3-4``にあたる部分木も、左項に部分式``5*3``の子ノードを含んでいるため、まずは部分式``5*3``にあたるノードの値を求めます。 このノードは左項が値``5``、右項が値``3``、演算子が``*``であるため、このノードは演算結果として値``15``を持つことになります。
まず、二分木の根を見ると、式は演算子が``+``で左項は値``2``、右項は子ノードを持っているため部分式となります。 部分式``5*3-4``にあたる部分木も左項に部分式``5*3``の子ノードを含んでいるため、まず部分式``5*3``にあたるノードの値を求めます。 このノードは左項が値``5``、右項が値``3``、演算子が``*``であるため、このノードは演算結果として値``15``を持つことになります。
 

                

                
 
#image(8-3.png,nopopup,二分木化した式の計算 step2)
#image(8-3.png,nopopup,二分木化した式の計算 step2)
 

                

                
~
部分式のノードの値が求まったことにより、上位の部分式の値を求めることができるようになったので、演算を続けます。 このノードは、左項が先の演算によって得られた値``15``、右項が値``4``、演算子は``-``であるため、このノードは演算結果として値``11``を持つことになります。
部分式のノードの値が求まったことにより、上位の部分式の値を求めることができるようになったので、演算を続けます。 このノードは左項が先の演算によって得られた値``15``、右項が値``4``、演算子は``-``であるため、このノードは演算結果として値``11``を持つことになります。
 

                

                
 
#image(8-4.png,nopopup,二分木化した式の計算 step3)
#image(8-4.png,nopopup,二分木化した式の計算 step3)
 

                

                
~
最終的に、根のノードの左項と右項の値が求まったため、このノードの値を演算した結果、すなわち値``13``が式``2+5*3-4``の計算結果となります。 このように、式を演算子と項に分割した二分木へと変換し、個々のノードの値を再帰的に演算していくことにより、式の計算を行うことができます。
最終的に、根のノードの左項と右項の値が求まったため、このノードの値を演算した結果、即ち値``13``が式``2+5*3-4``の結果となります。 このように、式を演算子と項に分割した二分木に変換し、個々のノードの値を再帰的に演算していくことにより、式の計算を行うことができます。
 

                

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

                

                
 
*Cでの実装 [#Implementation_C]
*Cでの実装 [#Implementation_C]
~
以下で紹介するのはC言語での実装です。 [[このプログラム>#Implementation_C_Complete]]は、ここまでで解説してきた[[アルゴリズム>#Algorithm]]を用いて数式の二分木化と各記法での表示、計算を行うものです。
ここで紹介するのはC言語での実装です。 このプログラムは、
~

                  
-中置記法を二分木に分解し、ポーランド記法(前置記法)、逆ポーランド記法(後置記法)、中置記法で出力
+
このプログラムは以下のことが可能で、[[冒頭に掲載しているデモ>#ConversionDemo]]と同様に動作します。
+

                  
+
-中置記法を二分木に分割し、ポーランド記法(前置記法)、逆ポーランド記法(後置記法)、中置記法で出力
 
-2項演算子のうち、四則演算子(``+``,``-``,``*``,``/``)、代入演算子(``=``)が使用可能
-2項演算子のうち、四則演算子(``+``,``-``,``*``,``/``)、代入演算子(``=``)が使用可能
 
-演算優先順位の指定に丸括弧``(`` ``)``が使用可能
-演算優先順位の指定に丸括弧``(`` ``)``が使用可能
~
-値として整数と小数が使用可能
-式の途中に空白を含むことも可能
~
-式の途中(演算子と項の間)に空白(`` ``)を含むことも可能
-式が四則演算子と数値のみの場合は、式の計算を行うことが可能
+
-数のみが含まれる場合に限り、部分式(または式全体)の計算を行うことが可能
 

                

                
~
一方、電卓のような用途を目的としたプログラムとしては不完全ではあるものの、アルゴリズムの説明の範囲を超えるため、以下の点は制限事項としています。
となっています。
+
-``+1``や``-1``などの符号付きの値は、左項がない不正な式として扱う (``(0+1)``, ``(0-1)``として記述することで代用可能)
+
-数値の間に空白を含んでいる場合は無視する (``1 2 + 3``は``12+3``として扱われる)
+
-暗黙の乗算を含む部分式に関する動作は未定義 (この実装では式``2(1+2)``は項``2(1+2)``として扱われ、部分式の分割および計算はされない)
+
-式の計算に関して
+
--計算できる部分式のみが計算されるため、``x + 1 = 2 + 1``の計算結果は``((x+1)=3)``となる
+
--数学的には等価な式でも、二分木への分割のされ方により計算される場合とされない場合がある (例:``X + 1 + 2``と``1 + 2 + X``)
+
--ゼロ除算やオーバーフローは考慮しておらず、また浮動小数点型を用いているため式によっては計算誤差なども生じる
 

                

                
~
以下、プログラムについて部分ごとに説明していきます。 [[プログラム全文は最後に掲載>#Implementation_C_Complete]]していますので、必要に応じて参照してください。 [[C以外の言語での実装>#Implementation_OtherLang]]も用意しています。
まずは部分毎に説明していきます。 [[プログラム全文は最後に掲載>#Implementation_C_Complete]]していますので、必要に応じて参照してください。 [[C以外の言語での実装>#Implementation_OtherLang]]も用意しています。
 

                

                
-
**データ構造とプログラムの概略 [#Implementation_C_Summary]
-
まずは二分木を表現するための``Node``型と、``main``関数でのプログラム全体の流れを見ていきます。
-

                  
-
#code(c){{
-
typedef struct Node Node;
 

                

                
~
**データ構造とプログラムの概略 [#Implementation_C_Summary]
#define MAX_NODES   80
~
まずは二分木を表現するための``Node``型と、``main``関数でのプログラム全体の流れを見ていきます。 (プログラム全文は[[#Implementation_C_Complete]]を参照してください。)
#define MAX_EXP_LEN 0x100
 

                

                
~
***データ構造 [#Implementation_C_Summary_Node]
struct Node {
~
二分木を表現するためのデータ構造は、``Node``型として次のように実装します。
    char exp[MAX_EXP_LEN];
-
    Node* left;
-
    Node* right;
-
};
 

                

                
~
#code(source=_source/polish.c,source-line-from=6,source-line-to=29,title=Node型,license=mit,copyrightyear=2017)
static Node nodes[MAX_NODES];
-
static int nb_node_used = 0;
 

                

                
~
``Node``型は次の3つの値を保持します。
Node* create_node()
~
:``left``|左の子ノード(部分木)へのポインタ
{
~
:``right``|右の子ノード(部分木)へのポインタ
    if (nb_node_used == MAX_NODES)
~
:``exp``|そのノードの持つ部分式(項または演算子)の文字列
        return NULL;
-
    else
-
        return &nodes[nb_node_used++];
-
}
 

                

                
~
また、``Node``型はあらかじめ最大``MAX_NODES``個(この例では80としました)を配列として用意しておき、必要になったら``create_node()``関数を呼び出すことで取得するようにします。 なお、各``Node``の``exp``に格納できる部分式は終端文字を含めて最大``MAX_EXP_LEN``文字(この例では256)までとします。
void remove_space(char *exp)
-
{
-
    char *dst = exp;
-
    char *src = exp;
-

                  
-
    while (*src) {
-
        if (*src == ' ')
-
            src++;
-
        else
-
            *(dst++) = *(src++);
-
    }
-

                  
-
    *dst = '\0';
-
}
 

                

                
+
***main関数 [#Implementation_C_Summary_Main]
+
``main``関数でのプログラム全体の流れ、およびその他の関数の定義は次のとおりです。
+
#code(c,title=mainから呼び出すその他の関数の定義,type=fragment){{
 
/*
/*
 
 * 以下の関数については後述
 * 以下の関数については後述
 
 */
 */
 
int parse_expression(Node* node);
int parse_expression(Node* node);
~
void traverse_postorder(Node* node);
void traverse_tree_postorder(Node* node);
~
void traverse_inorder(Node* node);
void traverse_tree_inorder(Node* node);
~
void traverse_preorder(Node* node);
void traverse_tree_preorder(Node* node);
~
int calculate(Node* node);
double calculate(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 (parse_expression(root) < 0) {
-
        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");
-

                  
-
    printf("calculated result: %f\n", calculate(root));
-

                  
-
    return 0;
-
}
 
}}
}}
 

                

                
~
#code(source=_source/polish.c,source-line-from=304,title=main関数,license=mit,copyrightyear=2017)
``Node``型は、
-
:left|左の子ノード(部分木)へのポインタ
-
:right|右の子ノード(部分木)へのポインタ
-
:exp|そのノードの持つ部分式(項または演算子)
-

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

                

                
 
``main``関数の流れは、
``main``関数の流れは、
~
+分割前の式全体を格納しておくため二分木の根、``root``を作成
+分解前の式全体を格納しておくため二分木の根、``root``を作成
~
+入力された式を``root->exp``に格納
+入力された式を``root->exp``にコピー
~
+二分木への変換の前準備として、邪魔になる空白を削除(``remove_space``)
+変換の前準備として、邪魔になる空白を削除(``remove_space``)
~
+[[式を二分木に分割>#Implementation_C_ParseExpression]]する(``parse_expression``)
+[[式を二分木に分割>#Implementation_C_ParseExpression]](``parse_expression``)
 
+分割した二分木を
+分割した二分木を
~
++帰りがけ順で[[巡回して表示する>#Implementation_C_TraverseBinaryTree]](``traverse_postorder``)
++帰りがけ順で[[トラバースして表示>#Implementation_C_TraverseBinaryTree]](``traverse_tree_postorder``)
~
++通りがけ順で巡回して表示する(``traverse_inorder``)
++通りがけ順でトラバースして表示(``traverse_tree_inorder``)
~
++行きがけ順で巡回して表示する(``traverse_preorder``)
++行きがけ順でトラバースして表示(``traverse_tree_preorder``)
~
++[[計算する>#Implementation_C_CalculateExpressionTree]](``calculate``)
++[[計算して>#Implementation_C_CalculateExpressionTree]]その値を取得・表示(``calculate``)
+
+++計算できた場合はその値、できなかった場合は中置記法(通りがけ順で巡回)した結果を表示する
 

                

                
 
となります。
となります。
 

                

                
 
**二分木への分割 [#Implementation_C_ParseExpression]
**二分木への分割 [#Implementation_C_ParseExpression]
~
次に、入力された式から二分木への分割を行う部分の関数``parse_expression``を見ていきます。 この関数は、二分木への分割に際して、式の最も外側にある丸括弧を削除する関数``remove_outer_most_bracket``、および、式中の演算子の位置を取得する関数``get_pos_operator``を呼び出します。
次に、入力された式を二分木への分割を行う部分の関数を見てみます。
-

                  
-
#code(cs){{
-
int remove_bracket(char *exp)
-
{
-
    size_t i;
-
    size_t len = strlen(exp);
-
    int nest = 1;
-

                  
-
    if (!(exp[0] == '(' && exp[len - 1] == ')'))
-
        return 0;
-

                  
-
    for (i = 1; i < len - 1; i++) {
-
        if (exp[i] == '(')
-
            nest++;
-
        else if (exp[i] == ')')
-
            nest--;
-

                  
-
        if (nest == 0)
-
            return 0;
-
    }
-

                  
-
    if (nest != 1) {
-
        fprintf(stderr, "unbalanced bracket: %s\n", exp);
-
        return -1;
-
    }
-

                  
-
    for (i = 0; i < len - 2; i++) {
-
        exp[i] = exp[i + 1];
-
    }
-
    exp[i] = '\0';
-

                  
-
    if (exp[0] == '(')
-
        remove_bracket(exp);
-

                  
-
    return 0;
-
}
 

                

                
~
#code(source=_source/polish.c,source-line-from=31,source-line-to=206,title=二分木への分割を行う関数群,license=mit,copyrightyear=2017)
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 (!exp)
-
        return -1;
-

                  
-
    for (i = 0; exp[i]; i++) {
-
        switch (exp[i]) {
-
            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 (nest == 0 && priority <= priority_lowest) {
-
            priority_lowest = priority;
-
            pos_op = i;
-
        }
-
    }
-

                  
-
    return pos_op;
-
}
-

                  
-
int parse_expression(Node* node)
-
{
-
    size_t pos_op;
-
    size_t len_exp;
-

                  
-
    if (!node)
-
        return -1;
-

                  
-
    pos_op = get_pos_operator(node->exp);
-

                  
-
    if (pos_op == (size_t)-1) {
-
        node->left  = NULL;
-
        node->right = NULL;
-

                  
-
        return 0;
-
    }
-

                  
-
    len_exp = strlen(node->exp);
-

                  
-
    // left-hand side
-
    node->left  = create_node();
-

                  
-
    if (!node->left) {
-
        fprintf(stderr, "expression too long\n");
-
        return -1;
-
    }
-

                  
-
    memset(node->left->exp, 0, MAX_EXP_LEN);
-
    strncpy(node->left->exp, node->exp, pos_op);
-

                  
-
    if (remove_bracket(node->left->exp) < 0)
-
        return -1;
-

                  
-
    if (parse_expression(node->left) < 0)
-
        return -1;
-

                  
-
    // right-hand side
-
    node->right = create_node();
-

                  
-
    if (!node->right) {
-
        fprintf(stderr, "expression too long\n");
-
        return -1;
-
    }
-

                  
-
    memset(node->right->exp, 0, MAX_EXP_LEN);
-
    strncpy(node->right->exp, node->exp + pos_op + 1, len_exp - pos_op);
-

                  
-
    if (remove_bracket(node->right->exp) < 0)
-
        return -1;
-

                  
-
    if (parse_expression(node->right) < 0)
-
        return -1;
-

                  
-
    // operator
-
    node->exp[0] = node->exp[pos_op];
-
    node->exp[1] = '\0';
-

                  
-
    return 0;
-
}
-
}}
 

                

                
 
``parse_expression``の流れを簡単に説明すると、
``parse_expression``の流れを簡単に説明すると、
~
+まず、``remove_outer_most_bracket``で分割する部分式に含まれる、最も外側の丸括弧を削除する (例:``(1+2)``を``1+2``にする)
+まず``get_pos_operator``で最も優先順位の低い演算子の位置を取得する
~
++丸括弧の数が一致しない場合などは、不正な式と判断して処理を終える (例:``node->exp``が``(1+2``などの場合)
++演算子がなかった場合は、二分木への分割が完了したとして処理を終える
~
+次に、``get_pos_operator``で最も優先順位の低い演算子の位置を取得する
+演算子があった場合は、その演算子を中心に左右の部分式へ分割する
~
++演算子が式の先頭または末尾にあった場合は、不正な式と判断して処理を終える (例:``node->exp``が``1-``、``+1``などの場合)
++ここで、``remove_bracket``で分割した部分式に含まれる、最も外側の括弧を削除する
~
++演算子がなかった場合は、二分木への分割が完了したとして処理を終える (例:``node->exp``が``1``、``2``などの場合)
++分割した部分式について、``parse_expression``でさらに分割する
+
++演算子があった場合は、その演算子を中心として左右の部分式へ分割する
+
+++``node->left``および``node->right``に新しくノードを作成(``create_node``)して代入する
+
+++``node->exp``から、左右それぞれの部分式にあたる部分を``node->left->exp``および``node->right->exp``にコピーする
+
+++``node->left``および``node->right``に対して``parse_expression``を呼び出すことで、左右それぞれの部分式を再帰的に分割していく
 

                

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

                  
-
**二分木のトラバース [#Implementation_C_TraverseBinaryTree]
-
続いて、二分木のトラバースを行う関数を見てみます。
-

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

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

                  
-
void traverse_tree_inorder(Node* node)
-
{
-
    if (node->left && node->right)
-
        printf("(");
-

                  
-
    if (node->left)
-
        traverse_tree_inorder(node->left);
-

                  
-
    printf(node->exp);
 

                

                
~
ここで``get_pos_operator``は、部分式のうち、''丸括弧``( )``で括られていない部分''で、かつ''最も優先順位の低い''演算子の位置を返します。 例えば式``1*(2+3)``の場合は、``*``の位置が分割すべき位置として判断されます。 なお、演算子の優先順位は次の順で定義しています。
    if (node->right)
~
+``=``
        traverse_tree_inorder(node->right);
+
+``+``および``-``
+
+``*``および``/``
 

                

                
~
``parse_expression``は、分割された部分式に演算子が含まれる限り、再帰的に呼び出され、式の分割を繰り返します。
    if (node->left && node->right)
-
        printf(")");
-
}
 

                

                
~
**二分木の巡回 [#Implementation_C_TraverseBinaryTree]
void traverse_tree_preorder(Node* node)
~
続いて、二分木の巡回を行う関数``traverse_postorder``, ``traverse_inorder``, ``traverse_preorder``を見ていきます。
{
-
    printf(node->exp);
 

                

                
~
#code(source=_source/polish.c,source-line-from=208,source-line-to=258,title=二分木の巡回を行う関数群,license=mit,copyrightyear=2017)
    if (node->left)
-
        traverse_tree_preorder(node->left);
-

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

                

                
~
それぞれ``traverse_postorder``が帰りがけ順、``traverse_inorder``が通りがけ順、``traverse_preorder``が行きがけ順で巡回する関数です。 各関数とも、与えられたノード``node``に対して、ノードの持つ値(``node->exp``)の表示を行い、子ノード(``node->left``, ``node->right``)がある場合は再帰的に巡回します。 値の表示と再帰呼出しの順序を変えることで、ノードの巡回順序も変わることに注目してください。 なお、``traverse_inorder``では結果のわかりやすさのために丸括弧を補って表示しています。
順に、帰りがけ順、通りがけ順、行きがけ順でトラバースする関数です。 与えられたノードに対してノードの持つ値の表示を行い、子ノードがある場合は再帰的にトラバースします。 なお、通りがけ順では見やすさのために括弧を付けて表示します。
 

                

                
 
**二分木からの値の演算 [#Implementation_C_CalculateExpressionTree]
**二分木からの値の演算 [#Implementation_C_CalculateExpressionTree]
~
続いて、二分木から値の演算を行う関数``calculate``を見ていきます。
続いて、二分木から値の演算を行う関数を見てみます。
 

                

                
~
#code(source=_source/polish.c,source-line-from=260,source-line-to=302,title=二分木から値の演算を行う関数,license=mit,copyrightyear=2017)
#code(c){{
-
double calculate(Node* node)
-
{
-
    double left_operand, right_operand;
-

                  
-
    if (node->left && node->right) {
-
        left_operand  = calculate(node->left);
-
        right_operand = calculate(node->right);
-

                  
-
        if (0 == strcmp(node->exp, "+"))
-
            return left_operand + right_operand;
-
        else if (0 == strcmp(node->exp, "-"))
-
            return left_operand - right_operand;
-
        else if (0 == strcmp(node->exp, "*"))
-
            return left_operand * right_operand;
-
        else if (0 == strcmp(node->exp, "/"))
-
            return left_operand / right_operand;
-
        else
-
            return 0.0;
-
    }
-
    else {
-
        return atof(node->exp);
-
    }
-
}
-
}}
 

                

                
 
``calculate``関数では、引数で与えられたノードについて、
``calculate``関数では、引数で与えられたノードについて、
~
+左右の両方に子ノードを持たない場合
+左と右の両方に子ノードを持つ場合
~
++``node->exp``には''項の値''が設定されているため、それ以上計算できないものとして処理を終える
++再帰的に``calculate``関数を呼び出すことで左と右の部分木の計算結果を求め
~
+左右の両方に子ノードを持つ場合
++求めた左項・右項の値を使い、ノード自体の持つ演算子に従って演算結果を返す
~
++再帰的に``calculate``関数を呼び出すことで左右の部分木の計算結果を求める
+子ノードを持たない場合
~
++``sscanf``関数を用いて、``node->left->exp``および``node->right->exp``の値を文字列から``double``へと変換することで、左項・右項の値を得る
++``atof``関数により文字列から``double``に変換することでノード自身の持つ値を返す
~
+++変換できない場合は、左項または右項がそれ以上計算できないものとして処理を終える

                  
~
++得られた左項・右項の値と、``node->exp``に設定されている演算子にしたがって演算を行う
という処理を行います。 再帰呼び出しを行うことにより、末端の部分木から順次値が定まって行きます。 この関数では0除算や、値を数値に変換できない場合などは考慮していません。
~
++``snprintf``関数を用いて、演算結果の値を再度``node->exp``に文字列として格納する

                  
~
++``node->left``および``node->right``に``NULL``を設定し、``node``を値のみのノードとする
**プログラム全文 [#Implementation_C_Complete]
-
最後に、プログラム全文と実行例です。
-

                  
-
#code(c){{
-
// gcc polish.c -o polish
-
#include <stdio.h>
-
#include <stdlib.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 (nb_node_used == MAX_NODES)
-
        return NULL;
-
    else
-
        return &nodes[nb_node_used++];
-
}
-

                  
-
void remove_space(char *exp)
-
{
-
    char *dst = exp;
-
    char *src = exp;
-

                  
-
    while (*src) {
-
        if (*src == ' ')
-
            src++;
-
        else
-
            *(dst++) = *(src++);
-
    }
-

                  
-
    *dst = '\0';
-
}
-

                  
-
int remove_bracket(char *exp)
-
{
-
    size_t i;
-
    size_t len = strlen(exp);
-
    int nest = 1;
-

                  
-
    if (!(exp[0] == '(' && exp[len - 1] == ')'))
-
        return 0;
-

                  
-
    for (i = 1; i < len - 1; i++) {
-
        if (exp[i] == '(')
-
            nest++;
-
        else if (exp[i] == ')')
-
            nest--;
-

                  
-
        if (nest == 0)
-
            return 0;
-
    }
-

                  
-
    if (nest != 1) {
-
        fprintf(stderr, "unbalanced bracket: %s\n", exp);
-
        return -1;
-
    }
-

                  
-
    for (i = 0; i < len - 2; i++) {
-
        exp[i] = exp[i + 1];
-
    }
-
    exp[i] = '\0';
-

                  
-
    if (exp[0] == '(')
-
        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 (!exp)
-
        return -1;
-

                  
-
    for (i = 0; exp[i]; i++) {
-
        switch (exp[i]) {
-
            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 (nest == 0 && priority <= priority_lowest) {
-
            priority_lowest = priority;
-
            pos_op = i;
-
        }
-
    }
-

                  
-
    return pos_op;
-
}
-

                  
-
int parse_expression(Node* node)
-
{
-
    size_t pos_op;
-
    size_t len_exp;
-

                  
-
    if (!node)
-
        return -1;
-

                  
-
    pos_op = get_pos_operator(node->exp);
-

                  
-
    if (pos_op == (size_t)-1) {
-
        node->left  = NULL;
-
        node->right = NULL;
-

                  
-
        return 0;
-
    }
-

                  
-
    len_exp = strlen(node->exp);
-

                  
-
    // left-hand side
-
    node->left  = create_node();
-

                  
-
    if (!node->left) {
-
        fprintf(stderr, "expression too long\n");
-
        return -1;
-
    }
-

                  
-
    memset(node->left->exp, 0, MAX_EXP_LEN);
-
    strncpy(node->left->exp, node->exp, pos_op);
-

                  
-
    if (remove_bracket(node->left->exp) < 0)
-
        return -1;
-

                  
-
    if (parse_expression(node->left) < 0)
-
        return -1;
 

                

                
~
という処理を行います。 ``calculate``関数を左右のノードに対して再帰的に呼び出すことにより、末端の部分木から順次値が定まっていきます。 すべての部分木の値が定まることで、最終的に木全体の値(つまり式の演算結果)が求まります。
    // right-hand side
-
    node->right = create_node();
-

                  
-
    if (!node->right) {
-
        fprintf(stderr, "expression too long\n");
-
        return -1;
-
    }
-

                  
-
    memset(node->right->exp, 0, MAX_EXP_LEN);
-
    strncpy(node->right->exp, node->exp + pos_op + 1, len_exp - pos_op);
-

                  
-
    if (remove_bracket(node->right->exp) < 0)
-
        return -1;
-

                  
-
    if (parse_expression(node->right) < 0)
-
        return -1;
-

                  
-
    // operator
-
    node->exp[0] = node->exp[pos_op];
-
    node->exp[1] = '\0';
-

                  
-
    return 0;
-
}
-

                  
-
void traverse_tree_postorder(Node* node)
-
{
-
    if (node->left)
-
        traverse_tree_postorder(node->left);
-
    if (node->right)
-
        traverse_tree_postorder(node->right);
-

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

                  
-
void traverse_tree_inorder(Node* node)
-
{
-
    if (node->left && node->right)
-
        printf("(");
 

                

                
~
なお、この関数ではゼロ除算(``1/0``)やオーバーフローなどについては考慮していません。 また、部分式に数値に変換できない文字が含まれている場合は、部分式の値が計算できないものと判断します。
    if (node->left)
-
        traverse_tree_inorder(node->left);
 

                

                
~
#remarks
    printf(node->exp);
+
式``X+1+2``と式``1+2+X``では異なる結果となります。 式がどのように二分木に分割され、計算されるかを考察すると結果が異なる理由がわかります。
+
#remarks-end
 

                

                
~
**プログラム全文 [#Implementation_C_Complete]
    if (node->right)
~
最後に、プログラム全文とコンパイル・実行例です。 なお、このプログラムは[[misc/license/MIT]]にて公開します。 複製・改変・再配布は、ライセンスに従った形で行ってください。
        traverse_tree_inorder(node->right);
-

                  
-
    if (node->left && node->right)
-
        printf(")");
-
}
-

                  
-
void traverse_tree_preorder(Node* node)
-
{
-
    printf(node->exp);
-

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

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

                  
-
double calculate(Node* node)
-
{
-
    double left_operand, right_operand;
-

                  
-
    if (node->left && node->right) {
-
        left_operand  = calculate(node->left);
-
        right_operand = calculate(node->right);
-

                  
-
        if (0 == strcmp(node->exp, "+"))
-
            return left_operand + right_operand;
-
        else if (0 == strcmp(node->exp, "-"))
-
            return left_operand - right_operand;
-
        else if (0 == strcmp(node->exp, "*"))
-
            return left_operand * right_operand;
-
        else if (0 == strcmp(node->exp, "/"))
-
            return left_operand / right_operand;
-
        else
-
            return 0.0;
-
    }
-
    else {
-
        return atof(node->exp);
-
    }
-
}
-

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

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

                  
-
    remove_space(root->exp);
-

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

                  
-
    if (parse_expression(root) < 0) {
-
        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");
 

                

                
~
#code(source=_source/polish.c,license=mit,copyrightyear=2017)
    printf("calculated result: %f\n", calculate(root));
 

                

                
~
#prompt(プログラムのコンパイルと実行(GCCを用いた場合の例)){{
    return 0;
~
$ gcc polish.c -o polish
}
+
$ ./polish
 
}}
}}
 

                

                
 
#prompt(実行例1){{
#prompt(実行例1){{
452,25 984,16
 
reverse polish notation: xy4*2z-3/+=
reverse polish notation: xy4*2z-3/+=
 
infix notation: (x=((y*4)+((2-z)/3)))
infix notation: (x=((y*4)+((2-z)/3)))
 
polish notation: =x+*y4/-2z3
polish notation: =x+*y4/-2z3
~
calculated expression: (x=((y*4)+((2-z)/3)))
calculated result: 0.000000
 
}}
}}
 

                

                
 
#prompt(実行例2){{
#prompt(実行例2){{
 
input expression: 1+4*2+(7-3)/2
input expression: 1+4*2+(7-3)/2
 
expression: 1+4*2+(7-3)/2
expression: 1+4*2+(7-3)/2
~
reverse polish notation: 142*73-2/++
reverse polish notation: 142*+73-2/+
~
infix notation: (1+((4*2)+((7-3)/2)))
infix notation: ((1+(4*2))+((7-3)/2))
~
polish notation: +1+*42/-732
polish notation: ++1*42/-732
~
calculated result: 11
calculated result: 11.000000
+
}}
+

                  
+
#prompt(実行例3){{
+
input expression: x = 3 * 2 + 1
+
expression: x=3*2+1
+
reverse polish notation: x32*1+=
+
infix notation: (x=((3*2)+1))
+
polish notation: =x+*321
+
calculated expression: (x=7)
 
}}
}}
 

                

                
 
*他の言語での実装 [#Implementation_OtherLang]
*他の言語での実装 [#Implementation_OtherLang]
481,15 1004,6
 
なお、[[最初に挙げたデモ>#ConversionDemo]]はJavaScriptで実装しています。 ソースコードについてはこのページのソースに含まれています。
なお、[[最初に挙げたデモ>#ConversionDemo]]はJavaScriptで実装しています。 ソースコードについてはこのページのソースに含まれています。
 

                

                
 
*文書情報 [#DocumentLog]
*文書情報 [#DocumentLog]
+
:2017-12-22|
+
::各言語での実装について|処理内容を記述したコメントを追記
+
ソースコードのライセンスを[[misc/license/MIT]]に設定
+
定数以外(XやAなどの記号)を含む部分式の場合でも、計算できる部分は計算するように変更(式``X=1+2``、``1+2=3*4+A``など)
+
開き丸括弧``(``および閉じ丸括弧``)``が正しく開いて/閉じていない場合にエラーとなるように修正(式``(2+3``、``1+(2+3))``など)
+
[[Pythonでの実装>programming/tips/polish/impl_python]]および[[JavaScriptでの実装>programming/tips/polish/impl_javascript]]を追加
+
[[Rubyでの実装>programming/tips/polish/impl_ruby]]を更新停止
+
::本文について|一部解説に加筆
+
用語の不統一を修正
 
:2017-12-09|Cでの実装について、strncpyの前にmemsetすることで文字列を終端させるように修正
:2017-12-09|Cでの実装について、strncpyの前にmemsetすることで文字列を終端させるように修正
 
:2013-07-02|二分木に変換した数式の計算を行うアルゴリズムについてを加筆
:2013-07-02|二分木に変換した数式の計算を行うアルゴリズムについてを加筆
 
用語の不統一を修正
用語の不統一を修正