この記事の目的

プログラムを勉強する中で、ゼロからアルゴリズムを考える機会が少なかったので、アルゴリズムを考えコードを書く練習として簡易的な計算機をpythonで作っていく。

今回作る計算機の仕様

入力される文字列は以下のルールに従う。

使用できる文字は整数、括弧、演算子(+,-,*,/,%,^)、スペースである
文字は半角を受け付ける
数字と数字の間にスペースがある場合は１つの数字として扱う(例:12 34→1234)
単項マイナス演算子は必ず括弧で囲む(例:-2→(-2))
括弧を用いる際の乗算の省略は不可(例:3(4+5)→3*(4+5))

設計

計算までの流れ

処理の流れは大きく分けて

文字列から配列に変換する
配列を逆ポーランド記法の並びに変換する
変換した配列とスタックとポップを用いて計算を行う

の三つのパートからなる。

続いて上記の処理の流れをどのように実装していくかを考えていく。

1.文字列から配列へ変換する

今回入力される文字は、数字・演算子・括弧のみなので、以下のようなルールで配列に要素を格納していく。

演算子や括弧が入力される:1文字を1つの要素として格納
数字が入力される:次に数字以外の文字が来るまでの文字列を1つの要素として、数字へと変換してから格納

2.配列を逆ポーランド記法の並びに変える

逆ポーランド記法への並び替えを行うために以下のルールを満たす配列prelistを生成していく。

長さは1または3
長さが1の配列は必ず[数字]となっている
長さが3の配列prelistは必ず[配列prelistまたは数字, 配列prelistまたは数字, 演算子]となっている

この配列prelistの要素を左から計算処理用の配列calへ追加していく。この時、配列の場合はその中身の要素を追加していく。

計算における演算子の優先順位は以下の順番とする。

括弧内の項
冪乗
乗法と除法と剰余
加法と減法

逆ポーランド記法への変換は以下のステップで行われる。

式の中に括弧がある場合、括弧の中を一つの式として先に変換を行い１つの配列にする。
括弧を除く演算子の中での最も優先順位の高い演算子とその左右の要素を[左の要素,右の要素,演算子]という1つの配列に変換する。同じ優先順位の演算子が複数個ある場合、配列の左にある演算子から変換を行う。この操作をすべての演算子に対して行う。
すべての演算子を変換したら、１次元配列となるように変換する。

配列の並び替えの例は以下の画像の流れとなる。

3.配列とスタックとポップを用いて計算を行う

計算用の配列stackListを用意しスタックとポップ機能を用いて計算を行っていく。
スタックとポップの大まかな説明は以下のとおりである。

スタック:配列の末尾にある要素を追加する。
ポップ:配列の末尾にある要素を取り出す。

今回pythonを用いるので、スタックの機能としてappend()を、ポップ機能としてpop()を用いる。

計算の流れを以下に示す。
また、逆ポーランド記法により並び替えた1次元配列をlinearArrayとする。

配列linearArrayの要素を左から読み込んでいき以下のルールで処理する。
- 読み込んだ要素が数字の場合、配列stackListに読み込んだ数字をスタックする。
- 読み込んだ数字が演算子の場合、配列stackListから2回ポップし取り出した値を (2回目に取り出した数字)演算子(1回目に取り出した数字) として計算を行う。
- 最後に計算結果を配列stackListにスタックする。
配列linearArrayを末尾まで読み込み終わったら、配列stackListには最終的な計算結果のみが格納されているので、最後に配列stackListからポップして結果を出力する。

計算の流れの例を以下の画像に示す。

実装

今回作成したコードを以下に示す。

メインの処理の部分

ここでは作成した関数を用いて入力された式を計算している。

main.py

import ChangeLists
import Calculation

#入力部分
moji=input()
#文字列を配列へと変換する
middleList=ChangeLists.getList(moji)
#配列を逆ポーランド記法の並びに変換する
PLLists=ChangeLists.createPL(middleList)
#並び替えた配列を1次元配列として返す
PLList=ChangeLists.oneList(PLLists)
#実際に計算を行い、結果を出力する
print('計算結果:'+str(Calculation.calc(PLList)))

配列の変換などの処理を行う部分

ここでは配列への変換を行う関数をまとめている。

ChangeLists.py

#文字列をリストに変換する
def getList(text):
    #スペース除去
    result = text.replace(' ','')
    MFlist = []
    number = 0
    
    #整数を追加するためのフラグ
    addTrigger= False
    
    #整数以外で入力可能な文字のリスト
    mylist=['(',')','^','*','/','+','-','%']
    
    #1文字ずつ読み込んでいく
    for t in result:
        if t.isdecimal():
            addTrigger=True
            number=number*10+int(t)
        else:
            #演算子の手前に数字があった場合は先に数字を追加した後に演算子を追加する
            if addTrigger:
                MFlist.append(number)
                addTrigger=False
                number=0
                if t in mylist:
                    MFlist.append(t)
            elif t in mylist:
                MFlist.append(t)
    #最後が数字で終わっている場合はここで追加する
    if result[-1].isdecimal():
        MFlist.append(number)
    return MFlist

#配列を逆ポーランド記法の並びに変換する
def createPL(prelist):
    end=len(prelist)
    index=0
    appendList=list()
    
    #-2のような符号反転がある場合は0-2のように変換を行う
    if prelist[0]=='-':
        prelist.insert(0, 0)
    
    #括弧の中身を先に逆ポーランド記法の並びに変換していく
    for i, j in enumerate(prelist):
        if j=='(':
            parenthesisNumber = 0
            for h in range(i+1,end):
                if prelist[h] == ')':
                    if parenthesisNumber == 0:
                        golist=prelist[i+1:h]
                        del prelist[i:h+1]
                        prelist.insert(i,createPL(golist))
                        break
                    else:
                        parenthesisNumber -= 1
                elif prelist[h]=='(':
                    parenthesisNumber += 1
    
    #指数がある項を変換していく
    i = 0
    while i < len(prelist):
        if prelist[i]=='^':
            operationList= []
            operationList.append(prelist[i-1])
            operationList.append(prelist[i+1])
            operationList.append(prelist[i])
            del prelist[i-1:i+2]
            prelist.insert(i-1,operationList)
            i -= 1
        i += 1
    
    #乗算除算剰余がある項を変換していく
    i = 0
    while i < len(prelist):
        if prelist[i]=='*'or prelist[i]=='/'  or prelist[i]=='%':
            operationList= []
            operationList.append(prelist[i-1])
            operationList.append(prelist[i+1])
            operationList.append(prelist[i])
            del prelist[i-1:i+2]
            prelist.insert(i-1,operationList)
            i -= 1
        i += 1

    #加算減算がある項を変換していく
    i = 0
    while i < len(prelist):
        if prelist[i]=='+'or prelist[i]=='-':
            operationList= []
            operationList.append(prelist[i-1])
            operationList.append(prelist[i+1])
            operationList.append(prelist[i])
            del prelist[i-1:i+2]
            prelist.insert(i-1,operationList)
            i -= 1
        i += 1
    
    return prelist

#並び終えた配列を1次元配列として返す
def oneList(lists):
    #変換先の1次元配列
    outputList=[]
    for t in lists:
        #配列の要素tが配列の場合、配列tの中身を配列outputListに加えていく
        if isinstance(t, list):
            outputList+=oneList(t)
        else:
            outputList.append(t)
    return outputList

計算を行う処理の部分

ここでは計算を行う関数をまとめている。

Calculation.py

import math

#逆ポーランド記法に並び替えられた配列を用いて計算を行う
def calc(linearArray):
    #計算用配列
    stackList=[]
    
    for t in linearArray:
        #演算子が読み込まれた場合,number2<演算子>number1の計算結果をstackListに格納する
        if t=='+':
            number1=stackList.pop()
            number2=stackList.pop()
            stackList.append(number2+number1)
        elif t=='-':
            number1=stackList.pop()
            number2=stackList.pop()
            stackList.append(number2-number1)
        elif t=='*':
            number1=stackList.pop()
            number2=stackList.pop()
            stackList.append(number2*number1)
        elif t=='/':
            number1=stackList.pop()
            number2=stackList.pop()
            stackList.append(number2/number1)
        elif t=='%':
            number1=stackList.pop()
            number2=stackList.pop()
            stackList.append(number2%number1)
        elif t=='^':
            number1=stackList.pop()
            number2=stackList.pop()
            stackList.append(pow(number2,number1))
        else:
        #数字の場合はそのままstackListに格納する。
            stackList.append(t)
    return stackList.pop()

実行例

入力には以下の式を用いる。

1 + (2-3) ^ 2

この式を入力すると計算結果は以下のとおりである。

計算結果:2

分かりやすくするためにCalculation.pyの36行目と37行目にprint(stackList)を追加して再度計算を行う。
計算結果は以下の通りとなる。

[1]
[1, 2]
[1, 2, 3]
[1, -1]
[1, -1, 2]
[1, 1]
[2]
計算結果:2

上記の結果から括弧の中身の次に２乗の計算が行われ、最後に加算が行われているのが分かる。

終わりに

今回、アルゴリズムを考える練習として、簡易的な計算機を考えてきた。
コードの長さを見てもわかる通り、アルゴリズムを考案する中で特に逆ポーランド記法への変換は前提知識ゼロで行ったのでかなり時間をかけている。
計算機のアルゴリズム自体はインターネットにいろいろ載っているので皆様も興味が出たら是非調べて作ってみてほしい。

Pythonを用いて簡易的な計算機を作った話