数式を中置記法から後置記法（逆ポーランド記法）に変換してみた

数式を示す文字列を、逆ポーランド記法に変換してみました。数値は自然数のみ、演算は加減乗除と一部の三角関数のみに対応したものですが、追々応用していけばよろしいかと思ったわけです。手法としては、スタックを使った変換です。

逆ポーランド記法については ウィキペディア を参照してください。

目次

  1. 逆ポーランド記法に変換するアルゴリズム
  2. 逆ポーランド記法における三角関数
  3. スタックで逆ポーランド記法に変換するときに三角関数をどう扱うか
  4. 試してみた

逆ポーランド記法に変換するアルゴリズム

数式を逆ポーランド記法に変換 や 逆ポーランド記法への変換２ を参考にさせていただきました。

逆ポーランド記法における三角関数

ウィキペディア では三角関数には触れていませんが、そこに記載されている定義では

逆ポーランド記法（ぎゃくポーランドきほう、英語: Reverse Polish Notation, RPN）は、数式やプログラムの記法の一種。演算子を被演算子の後にすることから、後置記法 (Postfix Notation) とも言う。

となっていますので、数値の後ろに関数名を置いてみます。

スタックで逆ポーランド記法に変換するときに三角関数をどう扱うか

三角関数には常に括弧が付いてきます。（括弧を付ける仕様にします。）

そして、逆ポーランド記法に変換する過程で、括弧の対を消滅させたときに演算子を積んでいる方のスタックの最上段に積まれているものを、三角関数かどうか見るようにします。

試してみた

下記のようなコードにしました。ファイル名はrpn.pyです。

INPUTED_TEXT = '1+2*s(3+c(4*t(5)+6))/7'
stack = []
buffer = []

for token in INPUTED_TEXT:
    if token == '(' or token == 'c' or token == 's' or token == 't':
        stack.append(token)
    elif token == ')':
        while len(stack) > 0:
            te = stack.pop()
            if te == '(':
                break
            else:
                buffer.append(te)
        if len(stack) > 0:
            if stack[-1] == 'c' or stack[-1] == 's' or stack[-1] == 't':
                buffer.append(stack.pop())
    elif token == '*' or token == '/':
        while len(stack) > 0:
            if stack[-1] == '*' or stack[-1] == '/':
                buffer.append(stack.pop())
            else:
                break
        stack.append(token)
    elif token == '+' or token == '-':
        while len(stack) > 0:
            if stack[-1] == '*' or stack[-1] == '/' or stack[-1] == '+' or stack[-1] == '-':
                buffer.append(stack.pop())
            else:
                break
        stack.append(token)
    else:
        buffer.append(token)

while len(stack) > 0:
    buffer.append(stack.pop())

print(buffer)

実行すると、こうなります。

>python rpn.py
['1', '2', '3', '4', '5', 't', '*', '6', '+', 'c', '+', 's', '*', '7', '/', '+']
反復処理 (while)   stringパッケージで定義されている定数

公開日

広告

作ってみたカテゴリの投稿