Webページでは数式を表すためにLaTeX表記が使えるMathJaxを利用しています。 WebブラウザにはSafari/Chrome/Firefoxを使って下さい(IEでは表示できないようです。)

スタックの応用(承前)

以下では、スタックデータ構造 データクラス stackの理解を前提にしている。

2項演算の後置き記法(逆ポーランド記法)

2つの演算数(オペランド(operand)という)$a, b$の間での2項演算子 $\odot$ を $a\odot b$ と記す表記を中置き式(infix notation)という(ただし、一般に非可換 $a\odot b\not=b\odot a$ である)。 中置き式の場合、別の2項演算子 $\boxdot$ とを混在させる場合には、演算子の優先順位(procedence)があると括弧が必要になる。 たとえば、$\odot\prec\boxdot$ の時、 $a\odot b \boxdot c= a\odot(b\boxdot c)\not=(a\odot b)\boxdot c$ である。

オペランド $a, b$ の間の2項演算子 $\odot$ を $a b\odot$ と記す表記を後置き式(postfix notation)または逆ポーランド記法(reverse Polish notation)という。 また、$\odot a b$ と記す表記を前置き式(prefix notation)という。 中置き式と異なり、後置き式や前置き式の表記では括弧は不要になる。 $\odot\prec\boxdot$ の時、 中置き式 $a\odot b \boxdot c$ は後置き式で $a b c\boxdot \odot$ に、中置き式 $(a\odot b)\boxdot c$ は後置き式で $a b\odot c\boxdot$ と表すことができる。

演習: $\odot\prec\boxdot$ の時、中置き式 $a\odot b \boxdot c$ および $(a\odot b)\boxdot c$ を後置き式と前置き式で表しなさい。

四則演算子 $[+], [-], [\times],[\div]$ と括弧の優先順位は次のように、それぞれ加と減および乗と除は同じ優先、乗除は加減よりも優先順位が高い。

\[ [+] = [-] , [\times]=[\div],\quad [+],[-]\prec [\times],[\div] \]

$2 + 3\times 4= 14$、$(2+3)\times 4 =20$ は誰でも知っている。

演習: 中置き式 $2\times (3+4) + (5-7) \div 8$ および $(2+3)\times (4+5)-(6-7 \div 8)$ を後置き式で表し、その式の値を求めなさい。

中置き記法を後置き記法に書き換える

$\times$ を * で、$\div$ を / で表した四則演算子 +, -, *, / および括弧 (, ) を使って正しく中置き記法で書かれた計算文字列 infix_expression を後置き記法で書かれた文字式に変換する関数 postfix_from_infix(infix_expression) を考えてみよう。

2項演算子 +, -, *, / と括弧 (, ) の優先順位は、たとえばPythonのデータ型 ディクショナリ を使って

     preced = {"*": 3, "/": 3, "+": 2, "-": 2, ")": 1, "(": 0} 
によって保持できる( ディクショナリ型とは、キー key と値 value がコロン(:)を使って key: value と対応付けられた並びをカンマ(,)で区切って中括弧記号 { と } で挟んだものである)。 このとき、2項演算子文字をキーとして preced["*"] によって優先度の値 3 を、preced["+"] によって優先度の値 2 をアクセスすることによって、2項演算子同士の優先度を比較することができるようになる。

次のコードは、スタックを表す stack クラスが定義されている前提で、関数 postfix_from_infix(infix_expression) を記述した例である。 15行目で、与えられた中置き記法の文字列 infix_expression を、空白文字 ' ' を空文字 '' に置き換えた後に、中置き記法の記号列の各1文字からなるリスト infix_list に変換して、17行からそのリスト要素である記号 symbol を先頭から調べている。

18行目で使う関数 is_operand(symbol) は中置き記法の記号 symbol がオペランドであるかどうかを判定する関数で、37行目で定義されている。

# declaration of stack class is assumed

def postfix_from_infix(infix_expression):
    # dictionary of operation *,/,+,- with precedence
    preced = {}
    preced["*"] = 3
    preced["/"] = 3
    preced["+"] = 2
    preced["-"] = 2
    preced["("] = 1
    preced[")"] = 0# symbol ) are never compared(never pushed into stack)

    postfix_list = []
    # set a infix list of letters, removing spaces
    infix_list = list(infix_expression.replace(' ',''))
    operation_stack = stack()
    for symbol in infix_list:
        if is_operand(symbol):
            postfix_list.append(symbol)
        elif symbol == '(':
            operation_stack.push(symbol)
        elif symbol == ')':
            stacktop = operation_stack.pop()
            while stacktop != '(':
                postfix_list.append(stacktop)
                stacktop = operation_stack.pop()
        else:
            while (not operation_stack.is_empty()) and (preced[operation_stack.peek()] >= preced[symbol]):
                postfix_list.append(operation_stack.pop())
            operation_stack.push(symbol)

    while not operation_stack.is_empty():
        postfix_list.append(operation_stack.pop())
    return " ".join(postfix_list)
    # output a post fix sting concatenating a list of letters

def is_operand(symbol):# decide whether symbol is operand
    return symbol != ")" and symbol != "(" and symbol != "+" and symbol != "-" and symbol != "*" and symbol != "/"
演習: 上の関数 postfix_from_infix(infix_expression) が、与えられた中置き記法文字列を後置き記法(逆ポーランド記法)の文字列に変換することを説明しなさい。
演習
print postfix_from_infix("(A * (B - C * D))")
print postfix_from_infix("A + B * C")
print postfix_from_infix("(A + B) * (C + D)")
print postfix_from_infix("(A + B) * C - (D - E) * (F + G)")
を実行するスクリプト to_postfix を書いて、実行してみなさい。 その結果は次のようになる。
$ ./to_postfix.py
A B C D * - *
A B C * +
A B + C D + *
A B + C * D E - F G + * -

後置き記法の計算値

数の四則演算 +, -, *, / を使った計算式が後置き記法(逆ポーランド式)の文字列 postfix_expression として与えられているとき、その値を求める関数 postfix_evaluation(postfix_expression) を書いてみよう。 オペランドが記号 a, b の場合には演算 $a b\odot$ は値 $(a\odot b)$ として、オペランドが数 3, 5 の場合には1桁だけで表された浮動小数(float)だと仮定して 3.0 / 5.0 を計算する。 複数桁の数を取り扱いたい場合には、四則演算子とオペランドだけからなるリストを得るための、文字列処理を行う必要がある。

2項演算子とオペランドが正しく後置き記法文字列 postfix_expression で与えられているときは、まず空白文字を空文字に置き換え、後置き記法での演算子とオペランドだけの文字列となるようにしてから、その各文字列からなるリスト postfix_list を生成する。 そのリスト要素を先頭から読み出して、オペランドならスタック operand_stack にプッシュ、2項演算子 $\odot$ なら、スタックからポップしたものを operand2、続けてポップしたものを operand1 として2項演算 operand1 $\odot$ operand2 として計算し(operand2 $\odot$ operand1 は誤りである)、その計算値値をスタックにプッシュする。

正しく後置き記法で正しく書かれていたならば、スタックには計算結果だけが残っており、これをポップしたものを関数 postfix_evaluation の戻り値とすればよい。

演習: スタック stack クラスを使って、関数 postfix_evaluation(postfix_expression) を定義したスクリプト postfix_eval.py を書いて、実行してみなさい。 たとえば、記号計算 print postfix_evaluation('a b + c d + *'), print postfix_evaluation('a b c * +') を実行すると、次の結果となる。
./postfix_eval.py
((a+b)*(c+d))
(a+(b*c))

数の$r$-進展開

整数の展開

整数 $N$ が整数 $r >1$ を使って \[ N = a_nr^n+a_{n-1}r^{n-1}+\dots a_1r^1 +a_0, \qquad a_i\in\{0,1,\dots,r-1\} \] のようであるとき、整数 $N$ の基数(radix)$r$ の$r$-進展開(r-expansion)といい $[a_n,a_{n-1},\dots, a_1,a_0]_r$ と表す。

10進整数 $N=$ decimal_integer と基数 $r=$ radix を与えて、その$r$-進展開の文字列を返す関数 radix_integer_expansion(decimal_integer, radix) は、次のようにスタックを使って書くことができる。

ここでは、Pythonの整数計算における剰余演算子 % と 整数商演算子 // を使っている。 11行目は、数を関数 str() でキャストして、文字列としての連接を記号 + で表している。

# declaration of stack class is assumed

def radix_integer_expansion(decimal_integer, radix):
   remainder_stack = stack()
   while decimal_integer > 0:
      remainder = decimal_integer % radix
      remainder_stack.push(remainder)
      decimal_integer = decimal_integer // radix
   binary_string = ""
   while not remainder_stack.is_empty():
      binary_string = binary_string + str(remainder_stack.pop())
   return binary_string
演習: 関数 radix_integer_expansion の動作を調べて、これが$r$-進展開の文字列を返すことを説明しなさい。

実数の展開

さて、区間$(0,]$ にある数 が $r>1$ を使って次のように表されているとする。 \[ \frac{a_1}{r} + \frac{a_2}{r^2} + \dots + \frac{a_{n-1}}{r^{n-1}} +\frac{a_n}{r^n}, \qquad a_i\in\{0,1,\dots,r-1\} \] この数を $(a_1,a_2,\dots, a_{n-1},a_n)_r$ と表すことにする。 $n$ が有限であれば、数 $(a_1,a_2,\dots, a_{n-1},a_n)_r$ は 0 と 1 の間の有理数(既約分数)で表される。

区間$(0,]$ 内の任意の数 $x$ を表すためには、一般に $n\rightarrow\infty$ とする必要があり、その表現 $(a_1,a_2,\dots, a_{n-1},a_n,\dots)_r$ を実数 $x$ の$r$-進展開という。 「オブジェクト指向--有理数計算を例にして」で指摘したように、ある$r$-進数を別の$r'$を使って$r$-進展開したときに有限の$r'$-進表現とはならない(有限整数では任意の正数基数を使って有限展開できるのであるが、非整数ではこうした著しい違いがある)。 有理数 1/10 は基数10の場合には $(1)_{10}$ で表されるが、2進展開や3進展開で表そうとすると無限回の展開が必要になる。

区間$(0,1]$ 内の任意の数 $x$ の$r$-進展開を求めるには、写像 $T_r:(0,1]\rightarrow (0,1]$ を \[ T_r(x)= rx - a(x),\qquad a(x) = \lfloor rx \rfloor \] を定義しておく。 ここで、$\lfloor x \rfloor$ は $x$ を越えない最大の整数を返す床関数である。 $T_r$を使うと、次のようにして $x_0=x$ から逐次的に整数の列 $a_n(x)=a(x_{n-1}), n\geq 1$ を計算することができる。 \[ x_n = T_r(x_{n-1}) = rx_{n-1} - a(x_{n-1}) \qquad n\geq 1. \] こうして定まる $(a_1(x),a_2(x),\dots, a_n(x))_r$ が $x\in(0,1]$ の$r$-進展開である(もちろん、一般には$n\rightarrow\infty$が必要である)。

演習: 区間$(0, 1]$内の浮動小数 numeric を正数基数 $r=$ radix > 0 で depth 回だけ$r$-進展開して得られる文字列を返す関数 radix_expression(numeric, radix, depth) を(あえて)「スタックを使って」定義し、幾つかの例を表示するスクリプト numeric_expansion.py を実行しなさい。 たとえば、 数 0.1 を基数 10, 2, 3, 4, 5 を使って 30回展開した結果はそれぞれ次のようになる。
$./numeric_expansion.py
100000000000000000000000000000
000110011001100110011001100110
002200220022002200220022002200
012121212121212121212121212200
022222222222222222222222222222
(ヒント) 整数を$r$-進展開する場合と違って、この場合は展開文字列 $a_1,a_2,\dots, $ を書き出すためにわざわざスタックを使う必要はない(それでもやってみよう)。 スタックに$a_1,a_2,\dots, $の順で積み上がってしまうために、スタックから取り出した文字列を展開文字列 $a_1,a_2,\dots, $ として書き出すには、文字列 st を逆順に print する必要があるからだ。 そのためには、Pythonでは単に print st[::-1] とするだけでよい。

連分数展開と有理数近似でふれたように、同じ回数の展開であっても、$r$-進展開による近似分数 $(a_1,a_2,\dots, a_{n-1},a_n)_r$ よりも、連分数 $[b_1,b_2,\dots, b_{n-1},b_n)]_C$ の方が圧倒的に近似度(収束度)が高いのは言うまでもない。