パズルの説明
Four Fours は数字を使ったパズルです。いろいろなルールがあるのですが、今回は簡易ルールで行きましょう。それでは問題です。
[問題] Four Fours 数字 4 を 4 つと＋, －, ×, ÷, （, ） を使って、答えが 1 から 10 になる式を作りなさい。 数字は 4 だけではなく、44 や 444 のように合体させてもよい。また、－を符号として使うことは禁止する。
数字の 4 を 4 つ使うので Four Fours という名前なのだと思います。ところで、このルールでは 11 になる式を作ることができません。ほかのルール、たとえば小数点を付け加えると、次のように作ることができます。
4 ÷ .4 ＋ 4 ÷ 4 = 11
今回は簡易ルールということで、小数点を使わないで 1 から 10 までの式を作ってください。まずは、ご自分の頭を使って解いてみましょう。気分転換や息抜きのときにでも考えてみてください。
●数式のパターン
それではプログラムを作りましょう。基本的には、数式を生成して答えをチェックするだけです。ところで、数式を解析して計算するのはちょっと面倒ではないかと思われた方もいるでしょう。ところが、近年のスクリプト言語では、プログラムの実行中に数式や別のプログラムを組み立て、それを実行することができるようになっています。これを「動的プログラミング」とか「実行時評価」と呼びます。
もともと動的プログラミングは Lisp や Prolog の得意技だったなのですが、Perl, Ruby, Python などのスクリプト言語でも行うことができます。今回は Python3 (ver 3.8.10) を使いましょう。Python の場合、関数 eval() を使って簡単に数式を計算することができます。
Four Fours の場合、4 つの数値に 3 つの演算子しかありませんから、数式のパターンは簡単に求めることができます。数式を二分木で表すと、次に示す 5 つのパターンになります。
X, Y, Z が演算子を表します。これを式で表すと、次のようになります。
(1) (4 Y 4) X (4 Z 4) (2) 4 X (4 Y (4 Z 4)) (3) ((4 Z 4) Y 4) X 4 (4) 4 X ((4 Z 4) Y 4) (5) (4 Y (4 Z 4)) X 4
あとは、X, Y, Z に演算子 +, -, *, / を入れて数式を計算すればいいわけです。
Four Fours は数字を合体できるので、数字が 3 つで演算子が 2 つ、数字が 2 つで演算子がひとつ、というパターンもあります。演算子がひとつの場合は簡単ですね。演算子が 2 つの場合は、次の式になります。
(A) (a Y b) X c (B) a X (b Y c)
a, b, c が数字で X, Y が演算子を表しています。数字は 4 か 44 になります。この場合、a, b, c の組み合わせを生成する必要があります。組み合わせを (a, b, c) で表すと、(4, 4, 44), (4, 44, 4), (44, 4, 4) の 3 通りとなります。これと演算子の組み合わせにより数式を生成して、答えを求めてチェックします。
●分数の計算
今回は式の値を正確に求めるため「分数 (有理数)」を使うことにします。Python の標準ライブラリ fractions をインポートすると、分数を表すクラス Fraction を使用することができます。分数の生成はコンストラクタ Fraction() を使います。
Fraction(n = 0, d = 1) => 分数
引数 n が分子、d が分母を表します。生成された分数を x とすると、分子は x.numerator で、分母は x.denominator で取得することができます。分数同士だけではなく、整数や実数との四則演算もできます。
簡単な例を示します。
>>> from fractions import Fraction >>> a = Fraction(1, 2) >>> a Fraction(1, 2) >>> print(a) 1/2 >>> b = Fraction(1, 3) >>> b Fraction(1, 3) >>> print(b) 1/3 >>> a + b Fraction(5, 6) >>> a - b Fraction(1, 6) >>> a * b Fraction(1, 6) >>> a / b Fraction(3, 2) >>> a + 1 Fraction(3, 2) >>> a + 1.0 1.5 >>> a / 2 Fraction(1, 4) >>> a / 2.0 0.25
分数を REPL で表示すると Fraction(n, d) となりますが、print() で表示すると n/d となります。分数と整数の計算は分数になり、分数と実数の計算は実数になります。
●f-string
関数 eval() は引数の文字列を Python の式として評価します。式を組み立てるとき、Perl のような「変数展開」があると便利です。変数展開は、文字列の中に変数が使われていると、その値に置き換えた新しい文字列を生成する機能です。Python の場合、文字列フォーマットで同じことができますが、それよりも手軽な方法に「フォーマット済み文字列リテラル (f-string)」があります。
f-string は ver 3.6 から追加された機能で、接頭辞に f または F を付けた文字列リテラルです。
f'... {式} ...' => '... 値 ...'
f-string は文字列の中に {式} を見つけると、{式} の部分を式を評価した値に置き換えた文字列を生成します。
簡単な例を示しましょう。
>>> f'123 + 456 = {123 + 456}'
'123 + 456 = 579'
>>> a = 'ABC'
>>> b = 'DEF'
>>> f'abc {a} def {b} {a * 2} {b * 3}'
'abc ABC def DEF ABCABC DEFDEFDEF'
文字列フォーマットを使うよりも簡単で便利ですね。
●プログラムの作成
それでは、4 が 4 つと演算子が 3 つある場合のプログラムを示します。
リスト : 数字が 4 つある場合
opls = ['+', '-', '*', '/']
f = 'Fraction(4,1)'
f2 = 'Fraction(44,1)'
f3 = 'Fraction(444,1)'
def solver4():
for x in opls:
for y in opls:
for z in opls:
for e in [f'({f} {y} {f}) {x} ({f} {z} {f})',
f'{f} {x} ({f} {y} ({f} {z} {f}))',
f'(({f} {z} {f}) {y} {f}) {x} {f}',
f'{f} {x} (({f} {z} {f}) {y} {f})',
f'({f} {y} ({f} {z} {f})) {x} {f}' ]:
try:
r = eval(e)
if r.denominator == 1 and 0 < r.numerator <= 10:
print(e.replace(f, '4'), '=', r)
except ZeroDivisionError:
pass
4 を表す Fraction(4,1) は大域変数 f に文字列としてセットします。同様に 44 を表す変数 f2 と 444 を表す変数 f3 を定義します。数式の組み立ては f-string を使えば簡単です。演算子を変数 x, y, z にセットし、それを使って 5 種類の数式を組み立てればいいわけです。
そして、組み立てた数式 e を関数 eval() で評価します。計算結果が整数で 1 以上 10 以下であれば print() で式を表示します。このとき、メソッド replace() で 'Fraction(4,1)' を '4' に置換しています。なお、式の中には 0 で除算する場合があります。たとえば、4 * 4 / (4 - 4) を実行すると、実行時にエラーが送出されます。このエラーを捕捉するため try 文を使っています。この場合はエラーを無視してプログラムの実行を継続するだけです。
数字が 3 つで演算子が 2 つの場合も、基本的には同じプログラムになります。ただし、数字は引数として渡します。関数名を solver3 とすると、solver3(f, f, f2), slover3(f, f2, f), solver3(f2, f, f) と 3 回呼び出します。solver3 では、引数と演算子を組み合わせて数式を生成し、答えをチェックします。詳細は プログラムリスト を参照してください。
●実行結果
さっそく実行してみたところ、全部で 100 通りの式が出力されました。このプログラムは重複解のチェックを行っていないので、多数の式が出力されることに注意してください。
実行結果の一部を示します。1: (4 - 4) + (4 / 4) 2: (4 / 4) + (4 / 4) 3: ((4 + 4) + 4) / 4 4: 4 + (4 * (4 - 4)) 5: ((4 * 4) + 4) / 4 6: ((4 + 4) / 4) + 4 7: 4 + (4 - (4 / 4)) 8: (4 + 4) + (4 - 4) 9: (4 + 4) + (4 / 4) 10: (44 - 4) / 4
この中で、10 になる式は (44 - 4) / 4 しかありません。数字 4 を 4 つと＋, －, ×, ÷, ( , ) だけでは、10 になる式を作ることはできないのですね。
●構文木を使う方法
eval() を使わない場合は、構文木 (二分木) を作るといいでしょう。構文木を表すクラスは次のようになります。
リスト : 構文木
# 葉
class Lf:
def __init__(self, x):
self.item = x
# 節
class Nd:
def __init__(self, x, l, r):
self.op = x
self.left = l
self.right = r
クラス Lf は二分木の葉を、Nd は節を表します。Lf のインスタンス変数 item に値を格納します。Nd のインスタンス変数 op に演算子、left に左辺式、right に右辺式を格納します。
次は式を計算する関数 calc_expr() を作ります。
リスト : 式の計算
def calc_expr(expr):
if isinstance(expr, Lf):
return expr.item
else:
l = calc_expr(expr.left)
r = calc_expr(expr.right)
op = expr.op
if op == '+':
return l + r
elif op == '-':
return l - r
elif op == '*':
return l * r
else:
return l / r
引数 expr が式を表します。expr が葉ならば expr.item を返します。節の場合、calc_expr() を再帰呼び出しして、左辺式と右辺式の値を求めます。あとは、expr.op が表す演算を行って結果を返すだけです。
最後に、4 が 4 つと演算子が 3 つある場合の式を求める関数 solver4t() を作ります。
リスト : 数字が 4 つある場合
def solver4t(f):
for x in opls:
for y in opls:
for z in opls:
for e in [Nd(x, Nd(y, f, f), Nd(z, f, f)),
Nd(x, f, Nd(y, f, Nd(z, f, f))),
Nd(x, Nd(y, Nd(z, f, f), f), f),
Nd(x, f, Nd(y, Nd(z, f, f), f)),
Nd(x, Nd(y, f, Nd(z, f, f)), f)]:
try:
r = calc_expr(e)
if r.denominator == 1 and 0 < r.numerator <= 10:
print_expr(e, 0)
print(' =', r)
except ZeroDivisionError:
pass
引数 f には葉 Lf(Fraction(4,1)) を渡します。構文木は図で示したパターンをそのままプログラムしただけなので、難しいところはないと思います。構文木 e を組み立てたならば calc_expr() で e を評価して、条件を満たしていれば print_expr() で式を表示します。あとのプログラムは簡単なので説明は割愛させていただきます。詳細は プログラムリスト をお読みくださいませ。
実行結果は eval() を使った場合と同じなので省略します。
●逆ポーランド記法
私達が普通に式を書く場合、1 + 2 のように演算子を真ん中に置きます。この書き方を「中置記法」といいます。中があれば前後もあるだろう、と思われた方はなかなか鋭いです。そのとおりで、「前置記法」と「後置記法」という書き方があります。
前置記法は演算子を前に置く書き方です。たとえば、1 + 2 であれば + 1 2 と書きます。これにカッコを付けると (+ 1 2) となり、M.Hiroi's Home Page ではお馴染みの Lisp プログラムになります。つまり、Lisp は前置記法で数式を表しているのです。
後置記法は演算子を後ろに置く書き方で、「逆ポーランド記法 (RPN : Reverse Polish Notation)」と呼ばれています。1 + 2 であれば 1 2 + のように書きます。逆ポーランド記法の利点は、計算する順番に演算子が現れるため、カッコが不要になることです。たとえば、"1 と 2 の和と 3 と 4 の和との積"、という数式を表してみましょう。
中置記法： (1 + 2) * (3 + 4) 後置記法： 1 2 + 3 4 + *
逆ポーランド記法は、日本語の読み方とまったく同じです。1 2 + で 1 と 2 の和を求め、3 4 + で 3 と 4 を求め、最後に 2 つの結果を掛け算して答えが求まります。
私達は中置記法に慣れているため、逆ポーランド記法はわかりにくいのですが、コンピュータで利用する場合、演算ルーチンが簡単になるという利点があります。実際、FORTH というプログラミング言語では、逆ポーランド記法で数式を表しています。
構文木を RPN に変換するのは簡単です。木を「帰りがけ順」で巡回すると RPN になります。帰りがけ順は、左の子、右の子と出力してから、節のデータを出力する順番で木をたどります。fourfours の数式を RPN で表すと次のようになります。
(1) (4 Y 4) X (4 Z 4) => [4, 4, Y, 4, 4, Z, X] (2) 4 X (4 Y (4 Z 4)) => [4, 4, 4, 4, Z, Y, X] (3) ((4 Z 4) Y 4) X 4 => [4, 4, Z, 4, Y, 4, X] (4) 4 X ((4 Z 4) Y 4) => [4, 4, 4, Z, 4, Y. X] (5) (4 Y (4 Z 4)) X 4 => [4, 4, 4, Z, Y, 4, X]
RPN の式はリストで表すことにします。たとえば (1) の場合、X - Y とたどって Y の左右の葉 4 と 4 を出力し、そのあと Y にもどって演算子 Y を出力します。次に、X の右部分木 Z をたどって Z の左右の葉 4 と 4 を出力します。あとは Z - X と戻って演算子を出力します。したがって、RPN は [4, 4, Y, 4, 4, Z, X] になります。
●スタックの動作
逆ポーランド記法は「スタック (stack)」を使うと簡単に計算することができます。ここで、スタックの動作を簡単に説明しておきましょう。
図 : スタックの動作例
図はバネがついた容器を表していて、上から品物を出し入れすることができます。初めは空の状態です。ここに品物を乗せると、重さによってバネを圧縮し、品物が容器に格納されます。さらにもうひとつ品物を上に乗せると、さらにバネを圧縮し、その品物も容器に格納することができます。バネが限界まで圧縮されると、もう品物は追加できなくなります。取り出す場合は、上にある品物から行います。ひとつ取り出すと、その分バネが伸びて下にある品物が上に押し出されます。
この容器の動作が、スタックの動作なのです。スタックにデータを追加する操作を「プッシュ (PUSH)」といい、スタックからデータを取り出す操作を「ポップ (POP)」といいます。品物をデータに見立てれば、最初に A をスタックにプッシュし (2)、次に B をプッシュします (3)。データを取り出す場合、後から入れた B が先にポップされ (4)、その次に A がポップされてスタックが空になります (5)。このように、スタックは後から入れたデータが先に取り出されるので、「後入れ先出し (LIFO : Last-In, First-Out)」と呼ばれます。
●スタックを使って計算する
スタックを使うと、逆ポーランド記法は簡単に計算できます。
- 数値はスタックに追加する。
- 演算子であればスタックから 2 つ数値を取り出し、演算結果をスタックに追加する。
- 最後にスタックに残った値が答えになる。
たったこれだけの規則で数式を計算することができます。それでは、実際に 1 2 + 3 4 + * を試してみましょう。次の表をみてください。
| 数式 | 操作 | スタック |
|---|---|---|
| 1 | PUSH | [ 1 ] |
| 2 | PUSH | [ 2, 1 ] |
| + | POP (2) | [ 1 ] |
| POP (1) | [ ] | |
| 1+2=3 | [ ] | |
| PUSH | [ 3 ] | |
| 3 | PUSH | [ 3, 3 ] |
| 4 | PUSH | [ 4, 3, 3 ] |
| + | POP (4) | [ 3, 3 ] |
| POP (3) | [ 3 ] | |
| 3+4=7 | [ 3 ] | |
| PUSH | [ 7, 3 ] | |
| * | POP (7) | [ 3 ] |
| POP (3) | [ ] | |
| 3*7=21 | [ ] | |
| PUSH | [ 21 ] |
スタックは [ ] で表しています。最初の 1 と 2 は数値なのでスタックにプッシュします。次は演算子 + なので、スタックからデータを取り出して 1 + 2 を計算します。そして、計算結果 3 をスタックにプッシュします。
次に、3 と 4 は数値なのでスタックにプッシュします。次は演算子 + なので同じように処理して、計算結果 7 をスタックにプッシュします。スタックの中身は [ 7, 3 ] となり、最初の計算結果 3 と次に計算した結果 7 がスタックに格納されています。この状態で最後の * を処理します。7 と 3 を取り出すとスタックは空の状態になります。そして、3 * 7 を計算して 21 をスタックにプッシュします。これで計算は終了です。スタックに残っている値 21 が計算結果となります。
このように、スタックを使うことで逆ポーランド記法で書かれた数式を簡単に計算することができます。実は、数式だけではなく、スタックを用いてプログラムを実行することもできます。たとえば、プログラミング言語 FORTH がそうです。FORTH には「数値」と「ワード」という 2 種類のデータしかありません。ワードには +, -, *, / などの演算子のほかに、いろいろな処理が定義されています。もちろん、ユーザーが新しいワードを定義することもできます。
FORTH の動作は、数値であればスタックにプッシュして、ワードであればそれを実行する、というシンプルなものです。これでプログラミングができるのですから、とてもユニークな言語ですね。
●プログラムの作成
それでは、逆ポーランド記法を使って fourfours を解くプログラムを作ってみましょう。式はリストで表すことすると、式を計算する関数 calc_expr_prn() は次のようになります。
リスト : RPN の式を計算する
def calc_expr_rpn(xs):
st = []
for x in xs:
if isinstance(x, Number):
st.append(x)
else:
r = st.pop()
l = st.pop()
if x == '+':
v = l + r
elif x == '-':
v = l - r
elif x == '*':
v = l * r
else:
v = l / r
st.append(v)
if len(st) != 1:
raise Exception("RPN: 式に間違いがあります")
return st.pop()
引数 xs が RPN の式 (リスト) です。変数 st はスタックとして使用するリストです。for ループで xs から要素を順番に取り出し、数値ならば append() でスタックに積み、それ以外ならば演算処理を行います。Python の append() はリストの末尾にデータを追加します。これを PUSH として使います。
数値の判定は標準ライブラリ numbers の抽象クラス Number を使います。整数、実数、分数、複素数など x が数値であれば isinstance(x, Number) は真を返します。
数値でなければ、pop() でスタックからデータを取り出します。Python の pop() はリストの末尾からデータを取り除いて返します。これを POP として使います。スタックには左辺式、右辺式の順番で積まれているので、最初に取り出す値が右辺式の値、次に取り出す値が左辺式の値になります。あとは、演算子 x に従って計算し、その結果 v をスタックに積みます。
計算が終了したら、スタックに残っている値を返します。計算が正常に終了した場合、スタックにはデータがひとつしか残っていないはずです。そうでなければ raise でエラーを送出します。最後に pop() で値を取り出して return で返します。
RPN を中置記法に変換する場合もスタックを使うと簡単です。
リスト : 式の表示
def print_expr_rpn(xs):
st = []
for x in xs:
if isinstance(x, Number):
st.append(f'{x}')
else:
r = st.pop()
l = st.pop()
st.append(f'({l} {x} {r})')
if len(st) != 1:
raise Exception("RPN: 式に間違いがあります")
expr = st.pop()
print(expr[1:-1], end=' ')
print_expr_rpn() は calc_expr_rpn() とほとんど同じです。数値ならば文字列に変化してスタックに積みます。そうでなければ、スタックからデータを取り出し、文字列 f'({l} {x} {r})' を生成してスタックに積みます。最後にスタックに残っている数式を print() で出力します。このとき、先頭と末尾のカッコを取り除いています。
最後に、4 が 4 つと演算子が 3 つある場合の式を求める関数 solver4r() を作ります。
リスト : 数字が 4 つの場合
def solver4r(f):
for x in opls:
for y in opls:
for z in opls:
for e in [[f, f, y, f, f, z, x],
[f, f, f, f, z, y, x],
[f, f, z, f, y, f, x],
[f, f, f, z, f, y, x],
[f, f, f, z, y, f, x]]:
try:
r = calc_expr_rpn(e)
if r.denominator == 1 and 0 < r.numerator <= 10:
print_expr_rpn(e)
print('=', r)
except ZeroDivisionError:
pass
引数 f には数値 Fraction(4,1) を渡します。プログラムは構文木を RPN に変換するだけなので、難しいところはないと思います。式 e を組み立てたならば calc_expr_rpn() で e を評価して、条件を満たしていれば print_expr_rpn() で式を表示します。あとのプログラムは簡単なので説明は割愛させていただきます。詳細は プログラムリスト をお読みくださいませ。
実行結果は eval() を使った場合と同じなので省略します。興味のある方はいろいろ試してみてください。ルールを変更して新しい演算子を追加してみるのも面白いと思います。
●参考 URL
●プログラムリスト
#
# fourfours.py : ４つの４
#
# Copyright (C) 2022 Makoto Hiroi
#
from fractions import Fraction
from numbers import Number
#
# eval() を使う方法
#
opls = ['+', '-', '*', '/']
f = 'Fraction(4,1)'
f2 = 'Fraction(44,1)'
f3 = 'Fraction(444,1)'
# 数字が 4 つの場合
def solver4():
for x in opls:
for y in opls:
for z in opls:
for e in [f'({f} {y} {f}) {x} ({f} {z} {f})',
f'{f} {x} ({f} {y} ({f} {z} {f}))',
f'(({f} {z} {f}) {y} {f}) {x} {f}',
f'{f} {x} (({f} {z} {f}) {y} {f})',
f'({f} {y} ({f} {z} {f})) {x} {f}' ]:
try:
r = eval(e)
if r.denominator == 1 and 0 < r.numerator <= 10:
print(e.replace(f, '4'), '=', r)
except ZeroDivisionError:
pass
# 数字が 3 つの場合
def solver3(a, b, c):
for x in opls:
for y in opls:
for e in [f'({a} {y} {b}) {x} {c}', f'{a} {x} ({b} {y} {c})']:
try:
r = eval(e)
if r.denominator == 1 and 0 < r.numerator <= 10:
e = e.replace(f, '4')
e = e.replace(f2, '44')
e = e.replace(f3, '444')
print(e, '=', r)
except ZeroDivisionError:
pass
# 数字が 2 つの場合
def solver2(a, b):
for x in opls:
e = f'{a} {x} {b}'
try:
r = eval(e)
if r.denominator == 1 and 0 < r.numerator <= 10:
e = e.replace(f, '4')
e = e.replace(f2, '44')
e = e.replace(f3, '444')
print(e, '=', r)
except ZeroDivisionError:
pass
# 実行
def solver():
solver4()
solver3(f, f, f2)
solver3(f, f2, f)
solver3(f2, f, f)
solver2(f2, f2)
solver2(f3, f)
solver2(f, f3)
#
# 構文木 (二分木) を作る方法
#
# 葉
class Lf:
def __init__(self, x):
self.item = x
# 節
class Nd:
def __init__(self, x, l, r):
self.op = x
self.left = l
self.right = r
# 式の表示
def print_expr(expr, d):
if isinstance(expr, Lf):
print(expr.item, end='')
else:
if d > 0: print('(', end='')
print_expr(expr.left, d + 1)
print(f' {expr.op} ', end='')
print_expr(expr.right, d + 1)
if d > 0: print(')', end='')
# 式の計算
def calc_expr(expr):
if isinstance(expr, Lf):
return expr.item
else:
l = calc_expr(expr.left)
r = calc_expr(expr.right)
op = expr.op
if op == '+':
return l + r
elif op == '-':
return l - r
elif op == '*':
return l * r
else:
return l / r
# 数字が 4 つの場合
def solver4t(f):
for x in opls:
for y in opls:
for z in opls:
for e in [Nd(x, Nd(y, f, f), Nd(z, f, f)),
Nd(x, f, Nd(y, f, Nd(z, f, f))),
Nd(x, Nd(y, Nd(z, f, f), f), f),
Nd(x, f, Nd(y, Nd(z, f, f), f)),
Nd(x, Nd(y, f, Nd(z, f, f)), f)]:
try:
r = calc_expr(e)
if r.denominator == 1 and 0 < r.numerator <= 10:
print_expr(e, 0)
print(' =', r)
except ZeroDivisionError:
pass
# 数字が 3 つの場合
def solver3t(a, b, c):
for x in opls:
for y in opls:
for e in [Nd(x, Nd(y, a, b), c), Nd(x, a, Nd(y, b, c))]:
try:
r = calc_expr(e)
if r.denominator == 1 and 0 < r.numerator <= 10:
print_expr(e, 0)
print(' =', r)
except ZeroDivisionError:
pass
# 数字が 2 つの場合
def solver2t(a, b):
for x in opls:
e = Nd(x, a, b)
try:
r = calc_expr(e)
if r.denominator == 1 and 0 < r.numerator <= 10:
print_expr(e, 0)
print(' =', r)
except ZeroDivisionError:
pass
# 実行
def solver_t():
f = Lf(Fraction(4, 1))
f2 = Lf(Fraction(44, 1))
f3 = Lf(Fraction(444, 1))
solver4t(f)
solver3t(f, f, f2)
solver3t(f, f2, f)
solver3t(f2, f, f)
solver2t(f2, f2)
solver2t(f3, f)
solver2t(f, f3)
#
# RPN
#
def print_expr_rpn(xs):
st = []
for x in xs:
if isinstance(x, Number):
st.append(f'{x}')
else:
r = st.pop()
l = st.pop()
st.append(f'({l} {x} {r})')
if len(st) != 1:
raise Exception("RPN: 式に間違いがあります")
expr = st.pop()
print(expr[1:-1], end=' ')
def calc_expr_rpn(xs):
st = []
for x in xs:
if isinstance(x, Number):
st.append(x)
else:
r = st.pop()
l = st.pop()
if x == '+':
v = l + r
elif x == '-':
v = l - r
elif x == '*':
v = l * r
else:
v = l / r
st.append(v)
if len(st) != 1:
raise Exception("RPN: 式に間違いがあります")
return st.pop()
# 数字が 4 つの場合
def solver4r(f):
for x in opls:
for y in opls:
for z in opls:
for e in [[f, f, y, f, f, z, x],
[f, f, f, f, z, y, x],
[f, f, z, f, y, f, x],
[f, f, f, z, f, y, x],
[f, f, f, z, y, f, x]]:
try:
r = calc_expr_rpn(e)
if r.denominator == 1 and 0 < r.numerator <= 10:
print_expr_rpn(e)
print('=', r)
except ZeroDivisionError:
pass
# 数字が 3 つの場合
def solver3r(a, b, c):
for x in opls:
for y in opls:
for e in [[a, b, y, c, x], [a, b, c, y, x]]:
try:
r = calc_expr_rpn(e)
if r.denominator == 1 and 0 < r.numerator <= 10:
print_expr_rpn(e)
print('=', r)
except ZeroDivisionError:
pass
# 数字が 2 つの場合
def solver2r(a, b):
for x in opls:
e = [a, b, x]
try:
r = calc_expr_rpn(e)
if r.denominator == 1 and 0 < r.numerator <= 10:
print_expr_rpn(e)
print('=', r)
except ZeroDivisionError:
pass
# 実行
def solver_r():
f = Fraction(4, 1)
f2 = Fraction(44, 1)
f3 = Fraction(444, 1)
solver4r(f)
solver3r(f, f, f2)
solver3r(f, f2, f)
solver3r(f2, f, f)
solver2r(f2, f2)
solver2r(f3, f)
solver2r(f, f3)
改訂 2022 年 10 月 22 日