[Python] 後置記法(逆ポーランド法)のアルゴリズムを実装する方法

後置記法(逆ポーランド記法)は、演算子をオペランドの後に配置する表記法です。

Pythonで後置記法の式を評価するには、スタックを使用するのが一般的です。

アルゴリズムの流れは次の通りです。

まず、式を左から右に読み、数値が出てきたらスタックに積みます。

演算子が出てきたら、スタックから必要な数値を取り出し、演算を行い、その結果を再びスタックに積みます。

最終的にスタックに残った値が結果となります。

この記事でわかること

後置記法の基本と利点
スタックを用いた評価アルゴリズム
複雑な数式の処理方法
応用例としての電卓アプリ
中置記法から後置記法への変換方法

目次から探す

後置記法(逆ポーランド法)とは

後置記法(逆ポーランド法)は、数式を表現するための方法の一つで、演算子をオペランドの後に置く形式です。

この方式では、括弧を使用せずに演算の優先順位を明示的に示すことができるため、計算機による評価が容易になります。

例えば、通常の中置記法での式 3 + 4 を後置記法では 3 4 + と表現します。

後置記法は、スタックを利用したアルゴリズムに適しており、特に計算機科学やプログラミング言語の設計において広く用いられています。

後置記法のアルゴリズム

スタックを使った基本的な考え方

後置記法の評価にはスタックデータ構造が利用されます。

スタックはLIFO(Last In, First Out)方式で動作し、最後に追加された要素が最初に取り出されます。

この特性を利用して、オペランドをスタックにプッシュし、演算子が現れた際に必要なオペランドをスタックからポップして計算を行います。

演算子とオペランドの処理方法

後置記法では、数値(オペランド)と演算子が交互に現れます。

オペランドはスタックに追加され、演算子が現れると、スタックから必要な数のオペランドを取り出して演算を行い、その結果を再びスタックにプッシュします。

これにより、演算の結果を次の計算に利用することができます。

アルゴリズムの流れ

入力された後置記法の式を左から右に読み取る。
各トークン(数値または演算子)を確認する。

数値の場合、スタックにプッシュする。
演算子の場合、スタックから必要なオペランドをポップし、演算を実行する。

演算結果をスタックにプッシュする。
全てのトークンを処理した後、スタックに残った値が最終結果となる。

例：簡単な後置記法の式の評価

例えば、後置記法の式 5 3 + 2 * を評価する場合、以下のように処理が進みます。

5をスタックにプッシュ → スタック: [5]
3をスタックにプッシュ → スタック: [5, 3]
+が現れたので、5と3をポップして加算 → スタック: [8]
2をスタックにプッシュ → スタック: [8, 2]
*が現れたので、8と2をポップして乗算 → スタック: [16]

最終的にスタックに残った16がこの式の評価結果です。

Pythonでの後置記法アルゴリズムの実装

スタックの実装方法

Pythonでは、リストを使ってスタックを簡単に実装できます。

リストのappend()メソッドで要素をプッシュし、pop()メソッドで要素を取り出すことができます。

以下はスタックの基本的な実装例です。

class Stack:
    def __init__(self):
        self.items = []
    def push(self, item):
        self.items.append(item)
    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        raise IndexError("スタックは空です")
    def is_empty(self):
        return len(self.items) == 0
    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        raise IndexError("スタックは空です")

数値と演算子の判別方法

後置記法の式を評価する際、トークンが数値か演算子かを判別する必要があります。

Pythonでは、str.isdigit()メソッドを使って数値を判別できます。

演算子は、あらかじめ定義したリストやセットを使って確認します。

def is_operator(token):
    return token in ['+', '-', '*', '/']

演算の実行と結果の保存

演算子が現れた場合、スタックからオペランドをポップし、演算を実行します。

演算の結果は再びスタックにプッシュします。

以下は演算を実行する関数の例です。

def perform_operation(operator, operand1, operand2):
    if operator == '+':
        return operand1 + operand2
    elif operator == '-':
        return operand1 - operand2
    elif operator == '*':
        return operand1 * operand2
    elif operator == '/':
        return operand1 / operand2
    raise ValueError("無効な演算子です")

実装例：基本的な後置記法の評価

以下は、後置記法の式を評価するための完全な実装例です。

def evaluate_postfix(expression):
    stack = Stack()
    tokens = expression.split()
    for token in tokens:
        if token.isdigit():  # 数値の場合
            stack.push(int(token))
        elif is_operator(token):  # 演算子の場合
            operand2 = stack.pop()
            operand1 = stack.pop()
            result = perform_operation(token, operand1, operand2)
            stack.push(result)
        else:
            raise ValueError("無効なトークンです")
    return stack.pop()
# 使用例
result = evaluate_postfix("5 3 + 2 *")
print(result)  # 出力: 16

エラーハンドリングの実装

エラーハンドリングは、無効なトークンやスタックが空の状態でのポップ操作を防ぐために重要です。

上記の実装では、無効なトークンやスタックが空の場合に例外を発生させるようにしています。

これにより、プログラムが予期しない動作をすることを防ぎます。

複雑な後置記法の処理

複数桁の数値や負の数の扱い

後置記法では、複数桁の数値や負の数を正しく処理する必要があります。

複数桁の数値は、空白で区切られたトークンとして扱われるため、isdigit()メソッドだけでは判別できません。

負の数は、演算子の前にマイナス記号がある場合に特別に処理する必要があります。

以下は、複数桁の数値と負の数を扱うための修正例です。

def is_number(token):
    try:
        float(token)  # 数値に変換できるか確認
        return True
    except ValueError:
        return False

括弧を含む式の処理

後置記法では通常、括弧は使用しませんが、もし中置記法から後置記法に変換する場合、括弧の処理が必要です。

括弧の優先順位を考慮し、適切に演算を行うためには、Shunting Yardアルゴリズムなどを使用して中置記法を後置記法に変換することが一般的です。

優先順位の考慮

後置記法では、演算子の優先順位を考慮する必要がありませんが、もし中置記法から変換する場合、演算子の優先順位を考慮する必要があります。

例えば、*や/は+や-よりも優先されます。

これを考慮して、演算子のスタックを使用して適切に処理します。

実装例：複雑な後置記法の評価

以下は、複数桁の数値や負の数を含む後置記法の評価を行う実装例です。

def evaluate_complex_postfix(expression):
    stack = Stack()
    tokens = expression.split()
    for token in tokens:
        if is_number(token):  # 数値の場合
            stack.push(float(token))
        elif is_operator(token):  # 演算子の場合
            operand2 = stack.pop()
            operand1 = stack.pop()
            result = perform_operation(token, operand1, operand2)
            stack.push(result)
        else:
            raise ValueError("無効なトークンです")
    return stack.pop()
# 使用例
result = evaluate_complex_postfix("5 3.5 + 2 * -1 +")
print(result)  # 出力: 16.5

この実装では、複数桁の数値や負の数を正しく処理し、演算を行うことができます。

入力された式に応じて、適切な結果を返すことができます。

応用例

四則演算以外の演算子の追加

後置記法のアルゴリズムに新しい演算子を追加することは簡単です。

例えば、累乗演算子^や平方根演算子√を追加する場合、perform_operation関数を修正し、演算子の判別を行う部分に新しい演算子を追加します。

def perform_operation(operator, operand1, operand2=None):
    if operator == '+':
        return operand1 + operand2
    elif operator == '-':
        return operand1 - operand2
    elif operator == '*':
        return operand1 * operand2
    elif operator == '/':
        return operand1 / operand2
    elif operator == '^':
        return operand1 ** operand2
    elif operator == '√':
        return operand1 ** 0.5
    raise ValueError("無効な演算子です")

関数や変数を含む後置記法の実装

後置記法に関数や変数を追加することで、より柔軟な計算が可能になります。

例えば、sinやcosなどの三角関数を追加する場合、関数名をトークンとして認識し、スタックからオペランドをポップして計算を行います。

import math
def perform_function(func, operand):
    if func == 'sin':
        return math.sin(operand)
    elif func == 'cos':
        return math.cos(operand)
    raise ValueError("無効な関数です")

中置記法から後置記法への変換

中置記法を後置記法に変換するためには、Shunting Yardアルゴリズムを使用します。

このアルゴリズムは、演算子の優先順位と括弧を考慮しながら、入力された中置記法の式を後置記法に変換します。

def infix_to_postfix(expression):
    output = []
    stack = Stack()
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    for token in expression.split():
        if is_number(token):
            output.append(token)
        elif token in precedence:
            while (not stack.is_empty() and
                   precedence[stack.peek()] >= precedence[token]):
                output.append(stack.pop())
            stack.push(token)
        elif token == '(':
            stack.push(token)
        elif token == ')':
            while not stack.is_empty() and stack.peek() != '(':
                output.append(stack.pop())
            stack.pop()  # '('をポップ
        else:
            raise ValueError("無効なトークンです")
    while not stack.is_empty():
        output.append(stack.pop())
    return ' '.join(output)

後置記法を使った電卓アプリの作成

後置記法を利用した簡単な電卓アプリを作成することができます。

ユーザーからの入力を受け取り、後置記法に変換し、評価を行うことで計算結果を表示します。

def calculator():
    expression = input("中置記法の式を入力してください: ")
    postfix_expression = infix_to_postfix(expression)
    result = evaluate_postfix(postfix_expression)
    print(f"計算結果: {result}")
# 使用例
calculator()

この電卓アプリでは、ユーザーが中置記法の式を入力すると、後置記法に変換され、その結果が表示されます。

これにより、後置記法の利点を活かした計算が可能になります。