「Pythonデータ構造とアルゴリズム分析」読書ノート3-基本データ構造(一)

文書ディレクトリ

3.1本章目標

3.2線形データ構造とは何か

3.3桟

3.3.1スタックとは何か

3.3.2スタック抽象データ型

3.3.3 Pythonでスタックを実現

3.3.4適合括弧

3.3.5一般:一致符号

3.3.6 10進数を2進数に変換

3.3.3.7前、中、後の式

1.中間シーケンスを前シーケンスと後シーケンス

に変換

2.中序から後序への汎用変換法

3.計算後の順序式

3.4キュー

3.1本章の目標

スタック、キュー、両端キュー、リストなどの抽象データ型を理解する.

Pythonリストを使用して、スタック、キュー、および両端キューを実装できます.

基礎線形データ構造の性能を理解する.

前、中、後の式を理解します.

スタックを使用して、後続の式を計算します.

スタックを使用して、中間式を後続式に変換します.

キューを使用して基本的なタイミングシミュレーションを行います.

スタック、キュー、および両端キューがどのような問題を解決するのに適しているかを理解します.

「ノードと参照」モードを使用してリストをチェーンテーブルとして実装できます.

自分のチェーンテーブルとPythonのリスト実装を性能面から比較できる.

3.2線形データ構造とは
スタック、キュー、両端キュー、リストは、要素の順序が追加順序または削除順序に依存する秩序化されたデータセットです.ある要素が追加されると、前後の要素との相対的な位置は変わらず、このようなデータセットは通常、線形データ構造と呼ばれます.
3.3スタック
3.3.1スタックとは
スタックは「下スタック」とも呼ばれ、追加操作と除去操作が常に同じ端、すなわち「先端」で発生し、もう一方の端が「底端」であり、要素が底端に近いほどスタックに存在する時間が長くなる秩序化された集合である. 並べ替えの原則--LIFO(last-in-first-out)、すなわち後進先出. キッチンに積まれた皿やブラウザの多層ページ(URLはスタックに存在し、戻るボタンをクリックするとページを逆方向に閲覧できる). 反転プロパティ:要素を逆方向に並べ替えることができます.
3.3.2スタック抽象データ型
前述したように、スタックの動作順序は、以下の動作をサポートするLIFOである.

Stack()空のスタックを作成します.パラメータなしで、空のスタックを返します.

push(item)スタックの先頭に要素を追加します.パラメータitem、戻り値なし.

pop()スタック先端要素を除去します.パラメータなしで、先頭要素を返します.

peek()スタック先端要素が得られる(除去されない).パラメータなしで、先頭要素を返します.

isEmpty()スタックが空であるかどうかを確認します.引数なしでブール値を返します.

size()スタック内の要素の数が得られる.引数なしで整数を返します.

3.3.3 Pythonでスタックを実現する
Pythonで抽象データ型を実装すると、メソッドによって実装される新しいクラスを作成できます.
Pythonが提供する単純で強力なオリジナルの集合--リストを使用してスタックを実現します(リストの末尾がスタックの先端であると仮定します):

#  3-1 Python   
class Stack：
	def __init__(self):
        self.items = []
    
    def isEmpty(self):
        return self.items == []
    
    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        return self.items.pop()
    
    def peek(self):
        return self.items[len(self.items-1)]
    
    def size(self):
        return len(self.items)

もう1つの実装方法(スタックの先頭としてリストのヘッダを仮定する):

#  3-2 Python   
class Stack：
	def __init__(self):
        self.items = []
    
    def isEmpty(self):
        return self.items == []
    
    def push(self, item):
        self.items.insert(0, item)
    
    def pop(self):
        return self.items.pop(0)
    
    def peek(self):
        return self.items[0]
    
    def size(self):
        return len(self.items)

この実装形態では、appendおよびpopメソッドを直接使用するのではなく、insertおよびpopメソッドを使用して、0と表記された要素に明示的にアクセスする.
両方の方法で実現される機能は同じであり、スタックサポートの方法を完了することができるが、性能には差がある:append()とpop()方法の時間複雑度はいずれもO(1);一方,insert(0)およびpop(0)メソッドの時間的複雑さはいずれもO(n)である.
3.3.4かっこの一致
かっこマッチングとは、各左かっこに対応する右かっこがあり、カッコペアに正しいネスト関係があることを意味します.
正しく一致する括弧列:(()()()())(((())))(()(()()))不一致括弧列:(((((())())))())()()スタックでカッコマッチングアルゴリズムを完了するには、次の手順に従います. :空のスタックから順にカッコ列をスキャンし、左カッコに遭遇するとpush()スタックに押し込み、右カッコに遭遇するとpop()スタックから取り出す.一致する括弧列を処理した後にスタックが空でない場合、一致しません.逆に一致します.

#  3-3     
from pythonds.basic import Stack

def parChecker(str):
    s = Stack()
    balanced = True
    index = 0
    while index < len(str) and balanced:
        symbol = str[index]
        if symbol == "(":
            s.push(symbol)
        else:
            if s.isEmpty():
                balanced = False
            else:
                s.pop()
        index = index + 1
    if balanced and s.isEmpty():
        return True
    else:
        return False

3.3.5一般:一致記号
上記の状況を中括弧、中括弧などに拡張します(マッチング方法を追加します):

#  3-4     
from pythonds.basic import Stack

def parChecker(symStr):
    s = Stack()
    balanced = True
    index = 0
    while index < len(symStr) and balanced:
        symbol = symStr[index]
        if symbol in "([{":
            s.push(symbol)
        else:
            if s.isEmpty():
                balanced = False
            else:
                top = s.pop()
                if not matches(top, symbol):
                    balanced = False
        index = index + 1
    if balanced and s.isEmpty():
        return True
    else:
        return False

def matches(left, right):
    lefts = "([{"
    rights = ")]}"
    return lefts.index(left) == rights.index(right)

3.3.6 10進数を2進数に変換する
1つの10進数を2で割って、残数を記録して、逆にその2進数の数値なので、スタックでこの問題を解決することができます.例えば、10進数(233)10を2進数(11101001)2に変換するプロセス:
10進数を任意の進数に変換します(基数が16以下).

#  3-5     
from pythonds.basic import Stack
def baseConvert(num, base):
    digits = "0123456789ABCDEF"
    remstack = Stack()
    while num > 0:
        rem = num % base
        remstack.push(rem)
        num = num // base
        
    newStr = ""
    while not remstack.isEmpty():
        newStr = newStr + digits[remstack.pop()]
    
    return newStr

3.3.3.7前、中、後の式
ちゅうしんしき
プリアンブル式
ポストシーケンス式
A+B
+AB
AB+
A+B*C
+A*BC
ABC*+
(A+B)*(C+D)
*+AB +CD
AB+CD+*
前順序式と後順序式の演算子に対応するオペランドが明確であるため、式の演算順序は完全に動き演算子の位置によって決定され、中順序式だけが曖昧さを解消するために追加の括弧を必要とする.したがって,中序式は最も理想的ではない数式表現である.
1.中間シーケンスを前および後に変換
任意の複雑な中順序式を前順序式または後順序式に変換するには、中順序式を完全かっこ式として書き、かっこ内の演算子を左かっこ(前順序式)または右かっこ(後順序式)に移動します.
2.中序から後序への汎用変換法
中間式を左から右にスキャンする場合は、スタックで演算子を保存します.これにより、中系列式における先低級後高級の演算を先高級演算、後低級演算に変える反転特性を提供することができる.新しい演算子に遭遇するたびに、スタック内の演算子との優先度を比較する必要があります.「*」、「/」が最上位、「+」、「-」に次いで、「(」の左かっこの優先度が最も低いです.
中系列式の演算子には*、/、+および-が、括弧には(および)、オペランドにはA、B、Cなどが表記されているとします.次の手順では、後続のタグ列が生成されます.

演算子を保存するための空のスタックopstackと、結果を保存するための空のリストを作成します.

文字列メソッドsplitを使用して、入力された中順序式をリストに変換します.

このタグリストを左から右にスキャンします.

タグがオペランドの場合は、結果リストの末尾に追加します.

タグが左かっこの場合は、opstackスタックに押し込みます.

タグが右かっこの場合、対応する左かっこが除去されるまで、opstackスタックから要素を繰り返し除去します.スタックから取り出した各演算子を結果リストの最後に追加します.

タグが演算子の場合、opstackスタックに押し込みます.ただし、その前に、優先度の高い演算子または同じ演算子をスタックから取り出し、結果リストの末尾に追加する必要があります.

入力式の処理が完了したら、opstackをチェックし、残りのすべての演算子を結果リストの末尾に追加します.

Pythonでは、このアルゴリズムを実装します.

#  3-6             
from pythonds.basic import Stack
import string

def midTopost(midExpr):
    prec = {}
    prec["*"] = 3
    prec["/"] = 3
    prec["+"] = 2
    prec["-"] = 2
    prec["("] = 1

    opStack = Stack()
    postExprList = []
    midExprList = midExpr.split()

    for ch in midExprList:
        if ch in string.ascii_uppercase:
            postExprList.append(ch)
        elif ch == "(":
            opStack.push(ch)
        elif ch == ")":
            topch = opStack.pop()
            while topch != "(":
                postExprList.append(topch)
                topch = opStack.pop()
        else:
            while (not opStack.isEmpty()) and \
                (prec[opStack.peek()] >= prec[ch]):
                postExprList.append(opStack.pop())
            opStack.push(ch)
    
    while not opStack.isEmpty():
        postExprList.append(opStack.pop())

    return "".join(postExprList)

3.計算後の順序式
上記の操作で中系列式を後系列式に変換した後、後系列式をどのように計算するかを考慮します.同様にスタックの反転特性を用いてアルゴリズムを完了するが,後系列式をスキャンする場合,演算子ではなくオペランドを保存する必要がある.
演算子に遭遇するたびに、最近遭遇した2つのオペランドを乗算する必要があることを意味します.2回のスタックアウト操作を行うことで、対応する操作数を得ることができ、演算を行った後、演算結果をスタックに押し込み、後続の演算の操作数とすることができる.最後の演算子を処理した後、スタックには1つの値しか残っておらず、それを取り出して式演算の戻り値として使用します.
オペランドタグは、後続式の演算子タグが*、/、+および-であると仮定します.次の手順では、結果が計算され、整数値が返されます.

NullスタックopStackを作成します.

文字列メソッドsplitを使用して、入力された後続式をリストに変換します.

このタグリストを左から右にスキャンします.

タグがオペランドの場合は整数に変換してopStackスタックに押し込む.

タグが演算子の場合、opStackスタックから2つのオペランドが取り出されます.1回目は右操作数、2回目は左操作数を取り出し、対応する算術演算を行い、結果をopStackスタックに押し込む.

入力式の処理が完了すると、スタック内の値は結果として返されます.

Pythonでは、このアルゴリズムを実装します.

#  3-7        
from pythonds.basic import Stack
def postExprCal(postExpr):
    opStack = Stack()
    postExprList = postExpr.split()

    for ch in postExprList:
        if ch in "0123456789":
            opStack.push(int(ch))
        else:
            op2 = opStack.pop()
            op1 = opStack.pop()
            result = doMath(ch, op1, op2)
            opStack.push(result)
    return opStack.pop()

def doMath(op, op1, op2):
    if op =="*":
        return op1*op2
    elif op == "/":
        return op1/op2
    elif op == "+":
        return op1+op2
    elif op == "-":
        return op1-op2

3.4キュー
続きを待つ.