基本情報平成30年度秋期アルゴリズム問題をPythonで書く

#目的

• 過去問を解いたらアルゴリズム問題めちゃくちゃ間違えた
• 複雑でめんどいからアルゴリズム問題きらい
• でも復習しなきゃ…
• じゃあ楽しく復習するために大好きなPythonで書き直してみよう！

#オリジナル問題

• 基本情報技術者試験平成30年度秋期午後問題問8
• 問題文はこちら(基本情報技術者試験ドットコム)

#書いたプログラム

• 整数式を受け取って計算し、値を返すプログラム

practice.py

Expression = []

formula = input("式を入力してください:")

for j in range(len(formula)):
    Expression.append(formula[j])

Value = []
Operator = []
Priority = []

def calculation():
    OpCnt = 0
    Value.append(0)
    nest = 0

    #解析部分
    for i in range(len(Expression)):
        chr = Expression[i]
        if chr >= '0' and chr <= '9':
            Value[OpCnt] = 10 * Value[OpCnt] + int(chr)

        if chr == '+' or chr == '-' or chr == '*' or chr == '/':
            Operator.append(chr)
            if chr == '+' or chr == '-':
                Priority.append(nest + 1)
            else:
                Priority.append(nest + 2)

            OpCnt = OpCnt + 1
            Value.append(0)

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

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

    #計算部分
    while OpCnt > 0:
        ip = 0
        i = 1
        while i < OpCnt:
            if Priority[ip] < Priority[i]:
                ip = i
            i = i + 1
        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]
        i = ip + 1
        while i < OpCnt:
            Value[i] = Value[i + 1]
            Operator[i - 1] = Operator[i]
            Priority[i - 1] = Priority[i]
            i = i + 1
        OpCnt = OpCnt - 1
    return Value[0]

#####分解してみましょう。

###①前準備
#####1-1. 式を入力してもらい、Expressionリストに文字として格納します

practice.py

Expression = []

formula = input("式を入力してください:")

for j in range(len(formula)):
    Expression.append(formula[j])

print(Expression)

• 問題で与えられた式2*(34-(5+67)/8)を入力すると…

コンソール

['2', '*', '(', '3', '4', '-', '(', '5', '+', '6', '7', ')', '/', '8', ')']

• ちゃんと一文字ずつExpressionリストに格納されてます

#####1-2. 空のリストを3つ用意

• Valueリスト：式の数値部分を格納
• Operatorリスト：式の演算子部分を格納
• Priorityリスト：値の降順でOperatorリスト内演算子の優先順位を表す

practice.py

Value = []
Operator = []
Priority = []

#####続いて関数部分を見ていきましょう。

###②解析処理と演算処理

• 関数は解析処理部分と演算処理部分に分かれています
• 関数部分は書き方をPython用に変えただけです
• 例) Operator[OpCnt] ← chrをOperator.append(chr)に書き換え

practice.py

def calculation():
    OpCnt = 0
    Value.append(0)
    nest = 0

    #解析処理部分
    for i in range(len(Expression)):
        chr = Expression[i]
        if chr >= '0' and chr <= '9':
            Value[OpCnt] = 10 * Value[OpCnt] + int(chr)

        if chr == '+' or chr == '-' or chr == '*' or chr == '/':
            Operator.append(chr)
            if chr == '+' or chr == '-':
                Priority.append(nest + 1)
            else:
                Priority.append(nest + 2)

            OpCnt = OpCnt + 1
            Value.append(0)

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

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

    #計算処理部分
    while OpCnt > 0:
        ip = 0
        i = 1
        while i < OpCnt:
            if Priority[ip] < Priority[i]:
                ip = i
            i = i + 1
        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]
        i = ip + 1
        while i < OpCnt:
            Value[i] = Value[i + 1]
            Operator[i - 1] = Operator[i]
            Priority[i - 1] = Priority[i]
            i = i + 1
        OpCnt = OpCnt - 1
    return Value[0]

#####2-1. 解析処理部分

• Expressionリストに格納されている値が数字なのか、演算子なのか、カッコなのか判別
• 演算処理を行う順序を決定
• 解析処理部分終了時の各リストの中身は以下の通りです

Value = [2, 34, 5, 67, 8]
Operator = ['*', '-', '+', '/']
Priority =[2, 11, 21, 12]

• Priorityの値が大きい順に、式におけるOperatorの演算子の優先度が高いです
• この場合Priority[2]が最大値であるため、Operator[2]の演算子を利用した演算を最初に行います

#####2-2. 演算処理部分

• Priorityリストの値をもとに順番に従って計算します
• 最終的な演算結果が入るValue[0]を戻り値に設定
• 今回の式では50.0という値を受け取れます

#感想

• 楽しかった^^