基本情報技術者試験のデータ構造及びアルゴリズム問題をPythonで実装する（平成三十年度秋期）。

トレースって大事だよね。

はろー、yukiです。

他の方の試験体験記を読んでも、アルゴリズム問題ではトレースが大事と言わています。

大事なのは、時間内に落ち着いてトレースし、処理内容を把握することだと思います。

今回の試験内容は、整数式の文字列処理と数値処理。

ある整数式から文字列を解析処理し、配列と変数を用いて数値を計算処理するもの。

実装したのは下記。

試験問題でも、プログラムは解析処理と計算処理に分かれています。

ですが、関数としては一つにまとめられていますので、それに沿います。

# H30 秋

# examle
Expression = ['2', '*', '(', '3', '4', '-', '(', '5', '+', '6', '7', ')', '/', '8']
ExpLen = len(Expression)

def Compute(Expression, ExpLen):
    Operator = []
    OpCnt = 0
    Priority = []
    Value = []
    chr = 0
    i = 0
    ip = 0
    nest = 0

    Value = [OpCnt]

    # Analysis
    for i in range(i, ExpLen):
        chr = Expression[i]

        if '0' <= chr and chr <= '9':
            Value[OpCnt] = 10 * Value[OpCnt] + int(chr)
            
        if chr == '+' or chr == '-' or chr == '*' or chr == '/':
            Operator.append(chr)
            #Operator[OpCnt] = chr -> list index out of range

            if chr == '+' or chr == '-':
                Priority.append(nest + 1)
                #Priority[OpCnt] = nest + 1 -> list index out of range
            else:
                Priority.append(nest + 2)
                #Priority[OpCnt] = nest + 2 -> list index out of range

            OpCnt = OpCnt + 1
            Value.append(0)

        if chr == '(':
            nest = nest + 10

        if chr == ')':
            nest = nest - 10

    print("Value[]:", Value)
    print("Operator[]:", Operator)
    print("Priority[]:", Priority)
    print("OpCnt:", OpCnt)

    # Calculate
    i = 1
    #if OpCnt > 0:
    while OpCnt > 0:
        ip = 0

        for i in range(1, OpCnt):
            if Priority[ip] < Priority[i]:
                ip = i
        
        chr = Operator[ip]

        if chr == '+': 
            Value[ip] = Value[ip] + Value[ip + 1]

        if chr == '-': 
            Value[ip] = Value[ip] - Value[ip + 1]

        if chr == '*': 
            Value[ip] = Value[ip] * Value[ip + 1]

        if chr == '/': 
            Value[ip] = Value[ip] / Value[ip + 1]

        for i in range(ip + 1, OpCnt):
            Value[i] = Value[i + 1]
            Operator[i - 1] = Operator[i]
            Priority[i - 1] = Priority[i]

        OpCnt = OpCnt - 1

    print("Value[0]:", Value[0])

    return Value[0]

Compute(Expression, ExpLen)

要は「2*(34-(5+67)/8)」の計算問題です。

それぞれの文字を配列に分類し、計算順序を正しく処理することになります。

計算結果は50になります。

上記のコードでは、各配列と変数に代入する値を出力するようにしています。

それが次のものです。

Value[]: [2, 34, 5, 67, 8]      
Operator[]: ['*', '-', '+', '/']
Priority[]: [2, 11, 21, 12]     
OpCnt: 4
Value[0]: 50.0

それぞれの配列には、数値、演算子、（計算のための）優先順序が入っています。

そして最終的に、Value[0]すなわち計算結果が50になっています。

この試験では、IPAが出している解説にもありますが、トレースする能力を問うています。

前述した通り、時間内に落ち着いてトレースしたいものです。

以上。