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

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

#オリジナル問題
- 基本情報技術者試験平成30年度秋期午後問題問8
- 問題文は[こちら](https://www.fe-siken.com/kakomon/30_aki/pm08.html)(基本情報技術者試験ドットコム)

#書いたプログラム
- 整数式を受け取って計算し、値を返すプログラム

```python: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リストに文字として格納します

```python:practice.py

Expression = []

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

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

print(Expression)

```

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

```python:コンソール
['2', '*', '(', '3', '4', '-', '(', '5', '+', '6', '7', ')', '/', '8', ')']
```

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

#####1-2. 空のリストを3つ用意
 - Valueリスト：式の数値部分を格納
 - Operatorリスト：式の演算子部分を格納
 - Priorityリスト：値の降順でOperatorリスト内演算子の優先順位を表す

```python:practice.py

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

```

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

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

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

```python

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という値を受け取れます

#感想
- 楽しかった^^