はじめに

基本情報技術者試験のアルゴリズム問題のPythonによる実装の続きです。

実装

今回は、平成23年秋期のアルゴリズム問題（代入文の処理）を対象とします。
- ご興味があるようなら、ぜひ問題にチャレンジしてみてください（所要時間30分）。
問題文と異なる実装を以下に示す。
変数stとerrを統合して、stとして扱う。stが、-1や10以上の場合はエラー状態を表す。
表1 文字とコードの対応はコードの番号を詰めて以下の通り再定義した。

S[i]の内容	≪	≫	英字	数字	=	+,-	*,/
V[i]に格納する内容	0	1	2	3	4	5	6

表2状態遷移表は横軸は文字コードに合わせ、縦軸は「終端」、「エラー」を追加して、以下の通り再定義した（起こりえない遷移項目は99とした。）。

縦軸:st 横軸:S[i],V[i]	≪ (0)	≫ (1)	英字 (2)	数字 (3)	= (4)	+,- (5)	*,/ (6)
開始(0)	99	15	1	12	13	14	14
左辺(1)	99	25	1	1	2	24	24
代入(2)	99	35	3	4	33	34	34
変数(3)	99	6	3	3	43	5	5
定数(4)	99	6	51	4	53	5	5
演算(5)	99	65	3	4	63	64	64
終端(6)	99	99	99	99	99	99	99
エラー(10以上)	99	99	99	99	99	99	99

代入文の構文解析(1)、(2)は関数make_codeを作成し、同時に実施した。
代入文の変換(2)は、問題文の副プログラム1としてnext_pos1，副プログラム2としてnext_pos2を作成し、変数testmodeの値で、どちらの副プログラムを使用するか決めるようにした。
副プログラム1はαをeの解答Getpos(S[], "=") + 2で置き換えた方で実装した。
代入文の変換(4)で使用する、nextの位置の演算子とその前後の項からなる文字列を抜き出す関数nukidashi_posを作成した。
代入文の変換(4)の、文字列を置き換える処理は、リストのスライス及び結合で実施した。問題文の副プログラム3は不要なので作成していない。
TEST01、TEST02、TEST03を実施した。
TEST01：最初の代入文の例Ans=X1+10*X2、及び設問1の代入文1～4の構文解析を続けて実施
TEST02：最初の代入文の例Ans=X1+10*X2の代入文の変換を副プログラム1で実施
TEST03：最初の代入文の例Ans=X1+10*X2の代入文の変換を副プログラム2で実施

h23f.py

# グローバル変数の設定
testmode = 1        # テストモード　1:副プログラム1(next_pos1())を使用、2:副プログラム2(next_pos2())を使用
S = ""
V = [-1]*100

def kaiseki(Sp):
    """
    代入文の構文解析
    解析結果に応じたst値を返す
    """
    global S,V
    S = "≪" + Sp + "≫"
    st = make_code()            # 代入文の構文解析(1),(2)の処理
    if st == -1:                # 代入文の構文解析(1)で代入文に不適切な文字が含まれていた場合の処理
        return st

    st_table = [                # 表2 状態遷移表
        [99,15, 1,12,13,14,14],
        [99,25, 1, 1, 2,24,24],
        [99,35, 3, 4,33,34,34],
        [99, 6, 3, 3,43, 5, 5],
        [99, 6,51, 4,53, 5, 5],
        [99,65, 3, 4,63,64,64],
        [99,99,99,99,99,99,99],
        [99,99,99,99,99,99,99]
    ]

    i = 0                       # 代入文の構文解析(3)（stはmake_codeで設定)
    while True:                 # 代入文の構文解析(4)
        i += 1
        st = st_table[st][V[i]]
        if st >= 10:            # 代入文の構文解析(5) 代入文に文法上の誤りがあった場合。
            print(f"エラーコード={st}")
            return st
        if st == 6:             # 代入文の構文解析(6) 代入文に文法上の誤りがなかった場合。
            print("エラーなし")
            return st

def make_code():
    """
    Sに対して、表1 文字とコードの対応に従いVを作成する。
    代入文に不適切な文字が含まれていた場合、-1を返す。
    """
    global S,V
    V = [-1]*100                # Vを初期化する。
    st = 0                      # stの初期値は0
    for i in range(len(S)):     
        if S[i] == "≪":
            V[i] = 0
        elif S[i] == "≫":
            V[i] = 1
        elif "a" <= S[i] <= "z" or "A" <= S[i] <= "Z" or S[i] == "#":
            V[i] = 2      
        elif "0" <= S[i] <= "9":
            V[i] = 3
        elif S[i] == "=":
            V[i] = 4
        elif S[i] in "+-":
            V[i] = 5
        elif S[i] in "*/":
            V[i] = 6
        else:
            st = -1             # 代入文に不適切な文字が含まれていた場合、stは-1とする。
    return st

def henkan():
    """
    代入文の変換
    """
    global S,V,testmode
    w = 0                       # 代入文の変換(1)
    while True:
        # 代入文の変換(2) testmodeによって副プログラム1,2を使い分ける
        if testmode == 1:
            next = next_pos1()
        elif testmode == 2:
            next = next_pos2()

        if next == 0:           # 代入文の変換(3)
            print(S[1:-1])
            return
        else:                   # 代入文の変換(4)
            from_pos, to_pos = nukidashi_pos(next)  # 文字列抜き出し位置計算
            N = S[from_pos:to_pos+1]                # 文字列を抜き出す(リストのスライスを利用)
            w += 1
            sahen = "wt#" + str(w)
            print(sahen + "=" + N)                  # 代入文の出力
            S = S[:from_pos] + sahen + S[to_pos+1:] # Sの置き換え(リストのスライスと結合を利用)
            # print(S)
            st = make_code()                        # Vの更新

def next_pos1():
    """
    代入文の変換(2) 副プログラム1
    """
    global V
#    i = 1                      # ←α
    i = Getpos(S, "=") + 2      # e（置き換え後を採用。）
    next = 0
    priority = 4
    while V[i] != 1:
        if priority < V[i]:     # c
            next = i
            priority = V[i]
        i += 1
    return next

def next_pos2():
    """
    代入文の変換(2) 副プログラム2
    """
    global V
    i = Getpos(S, "≫") - 1
    next = 0
    priority = 5
    while V[i] != 0:
        if priority <= V[i]:    # d
            next = i
            priority = V[i]
        i -= 1
    return next

def Getpos(str, chr):
    """
    副プログラムGetpos
    """
    return list(str).index(chr)

def nukidashi_pos(pos):
    """
    posの位置の演算子とその前後の項からなる文字列の抜き出し位置の計算プログラム
    抜き出し開始位置from_posと抜き出し終了位置to_posを計算
    問題文には詳しく書かれていない。
    """
    # 文字コード2(英字)または3(数字)が続く範囲のfrom_posを計算
    from_pos = pos
    while (V[from_pos-1] == 2) or (V[from_pos-1] == 3):
        from_pos -= 1

    # 文字コード2(英字)または3(数字)が続く範囲のto_posを計算
    to_pos = pos
    while (V[to_pos+1] == 2) or (V[to_pos+1] == 3):
        to_pos += 1

    return from_pos, to_pos 

def test01(Str):
    print(f"代入文：{Str}")
    st = kaiseki(Str)

def test02():
    henkan()    

print("=========TEST01=========")   # 最初の代入文の例、及び設問1の代入文1～4を続けて解析
Strs = [
    "Ans=X1+10*X2",
    "Answer=One+Two+Three+",
    "HexaSum=7FFF+0001",
    "Position=Index++",
    "X1+10*X2=Ans"
]
for Str in Strs:
    test01(Str)

print("=========TEST02=========")   # 最初の代入文の例を副プログラム1で評価
testmode = 1
Str = "Ans=X1+10*X2"
test01(Str)
test02()

print("=========TEST03=========")   # 最初の代入文の例を副プログラム2で評価
testmode = 2
Str = "Ans=X1+10*X2"
test01(Str)
test02()

実行結果

=========TEST01=========
代入文：Ans=X1+10*X2
エラーなし
代入文：Answer=One+Two+Three+
エラーコード=65
代入文：HexaSum=7FFF+0001    
エラーコード=51
代入文：Position=Index++
エラーコード=64
代入文：X1+10*X2=Ans
エラーコード=24
=========TEST02=========
代入文：Ans=X1+10*X2
エラーなし
wt#1=10*X2
wt#2=X1+wt#1
Ans=wt#2
=========TEST03=========
代入文：Ans=X1+10*X2
エラーなし
wt#1=10*X2
wt#2=X1+wt#1
Ans=wt#2

TEST01から、代入文②のときエラーコード51（設問１のa）、代入文③の場合エラーコード64（設問１のb）となることがわかる。
TEST02、TEST03から、どちらの場合でも適切な代入文の変換結果が得られていることがわかる。

感想

問題文で示された処理のうち疑似言語化されていないものがあり、自分で実装しなければならなかった（make_code、nukidashi_pos等）。
一方で、文字列の置き換えは、副プログラム3を実装せずとも、Pythonのリストのスライス及び結合で簡単に処理できた。Getposの実装も簡単である（index()メソッドそのもの）。Pythonの便利さを感じることができた。
ここはおかしい、こうしたほうが良いという箇所があれば、ご指摘いただけますと幸いです。