問題
中間記法を逆ポーランド記法に変換するpythonプログラムを作ります。
最終目的としては基本情報の過去問にあった以下の二問を解くこととします。
第一問目
過去問道場へのリンク(第一問目)
第二問目
過去問道場へのリンク(第二問目)
逆ポーランド記法
逆ポーランド記法（Reverse Polish Notation、RPN）は、数式を表現するための記法の一つです。この記法では、演算子がオペランドの後ろに置かれます。この記法は括弧を使用せずに演算子の優先順位を明確にすることができることです。
また、計算式を解析する際にスタックを使用することができ、計算の順序が明確になります。これにより、コンピュータが効率的に計算できます。
一方、日常で使うような数式を中間記法(Infix Notation)といいます。
具体例を挙げます。
a + b(中間記法) は ab+(逆ポーランド記法）
3 + 4 * (2 - 1) は 3 4 2 1 - * +
といった感じです。
アルゴリズム
入力された数式の左端に"("、右端に")"を追加します。そして、この数式を一文字ずつ見ていきます。
今、注目している文字が
-
数字だった場合
答えの配列に追加 -
演算子だった場合
1.スタックのトップの演算子が現在の演算子の優先度以上の場合
スタックの演算子を逆ポーランド記法の式に移動します。
これをスタックのトップの演算子が現在の演算子の優先度以上の未満になるまで繰り返します -
左括弧の場合
スタックにプッシュします -
右括弧の場合
スタックの演算子を逆ポーランド記法の式に移動します
左括弧が見つかるまで繰り返します
これをpythonで実装したものが以下です
def get_operant_priority(ope):
if ope in "()":
return 0
elif ope in "+-":
return 2
elif ope in "*/":
return 3
elif ope == "=":
return 1
def getRPN(origin):
operant = ["+", "-", "*", "/", "="]
parenthesis = ["(", ")"]
stack = []
rev_polish_notaion = []
for char in f"({origin})":
if char in operant:
while stack and get_operant_priority(stack[-1]) >= get_operant_priority(char):
ope_added = stack.pop()
if ope_added in "()":
continue
else:
rev_polish_notaion.append(ope_added)
stack.append(char)
elif char == " ":
continue
elif char == "(":
stack.append(char)
elif char == ")":
inner_parenthesis = stack.pop()
while inner_parenthesis != "(":
rev_polish_notaion.append(inner_parenthesis)
inner_parenthesis = stack.pop()
else:
rev_polish_notaion.append(char)
return rev_polish_notaion
for origin in ["c=a+b", "c=a-b", "c=a*b", "c=a/b","a*c+b", "a+b*c " ,"c=a+b*c+d/e*f", "3 + 4 * (2 - 1)"]:
ans = getRPN(origin)
ans = "".join(ans)
print(f"input: {origin:<12} -> output: {ans:<12}")
input: c=a+b -> output: cab+=
input: c=a-b -> output: cab-=
input: c=a*b -> output: cab*=
input: c=a/b -> output: cab/=
input: a*c+b -> output: ac*b+
input: a+b*c -> output: abc*+
input: c=a+b*c+d/e*f -> output: cabc*+de/f*+=
input: 3 + 4 * (2 - 1) -> output: 3421-*+
とかせてみる
では、本記事の目的である基本情報の過去問を解いていきましょう。
過去問道場へのリンク(第一問目)
input: ((a+b)*c)-d -> output: ab+c*d-
input: (a+(b*c))-d -> output: abc*+d-
input: (a+b)*(c-d) -> output: ab+cd-*
input: a+(b*(c-d)) -> output: abcd-*+
この結果からエが答えとなります。
第二問目
過去問道場へのリンク(第二問目)
input: Y=(A+B)*(C-(D/E)) -> output: YAB+CDE/-*=
プログラムに入力するため若干の変更を加えています。
この出力からイが答えであると分かります。
最後に
実は逆ポーランド記法に変換するプログラムは、コンパイラの学習でつくりました。そこで、基本情報でこういう問題やったなーと思って解かせてみました。
今回は題材として基本情報の問題を取り上げましたが、ただ問題を解くだけでなく、その知識を元にコンパイラやプログラミングの応用範囲を広げたいと思ってます。