《problem-solving-with-algorithms

作者: 夏天夏星 | 来源:发表于2017-07-22 16:58 被阅读0次

读书笔记
一、关于栈：栈操作

Stack() 创建一个空的新栈。它不需要参数，并返回一个空栈。
push(item)将一个新项添加到栈的顶部。它需要 item 做参数并不返回任何内容。
pop() 从栈中删除顶部项。它不需要参数并返回 item 。栈被修改。
peek() 从栈返回顶部项，但不会删除它。不需要参数。不修改栈。
isEmpty() 测试栈是否为空。不需要参数，并返回布尔值。
size() 返回栈中的 item 数量。不需要参数，并返回一个整数

image.png

二、Python实现栈
当我们给抽象数据类型一个物理实现时，我们将实现称为数据结构
抽象数据类型：栈
抽象数据类型的选择的实现：创建一个新类
栈操作实现为类的方法
栈的实现由于栈是一个表，因此任何实现表的方法都能实现栈

[1]
[1]:https://www.sogou.com/link?url=DOb0bgH2eKih6L6-zjc6o4XQwy2fLmFtVp0RnDKnmVWGBAHeZ71z-AZFJ5UQUXQ3&query=%E6%A0%88%E6%93%8D%E4%BD%9C%E5%AE%9E%E7%8E%B0%E4%B8%BA%E7%B1%BB%E7%9A%84%E6%96%B9%E6%B3%95%E3%80%82
ActiveCode 1

class Stack:# 创建一个栈
    def __init__(self):

        self.items = []

    def isEmpty(self):

        return selt.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)

python test.py——测试通过
使用栈:
通过实例化 Stack 类执行 Table 1中的操作。
注意，Stack 类的定义是从 pythonds 模块导入的
ActiveCode 2

from pythonds.basic.stack import Stack

s = Stack()

print(s.isEmpty())

s.push(4)

s.push('dog')

print(s.peek())

s.push(True)

print(s.size())

print(s.isEmpty())

s.push(8.4)

print(s.pop())

print(s.pop())

print(s.size())
运行结果：
python test.py
True
dog
3
False
8.4
True
2```

小结：
1.栈实现：创建类
2.栈操作实现：创建类的方法
3.Python的列表作为底层实现
问题：
1.ImportError: No module named 'pythonds'
解决：cmd-输入pip install pythonds安装该模块
小知识：
1958年，JohnMcCarthy设计了Lisp语言。
2.1 栈解决实际问题
 Lisp 使用大量的圆括号是臭名昭著的
如 Lisp 的构造

(defun square(n)
(* n n))

这段代码定义了一个名为 square 的函数，它将返回参数的 n 的平方
ActiveCode 1

from pythonds.basic.stack import Stack

A 如何编写一个算法，能够从左到右读取一串符号，并决定符号是否平衡。

def parChecker(symbolString):

s = Stack()

balanced = True

index = 0

while index < len(symbolString) and balanced:

    symbol = symbolString[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

print(parChecker('((()))'))
print(parChecker('(()'))

结果;
True
False
2.2 符号匹配
在 Python 中，方括号 [ 和 ] 用于列表，花括号 { 和 } 用于字典。括号 ( 和 ) 用于元祖和算术表达式
现在不仅要考虑开始与结束符号是否匹配，还需要保证符号的匹配类型，如（）和[]
ActiveCode 1

from pythonds.basic.stack import Stack

def parChecker(symbolString):

s = Stack()

balanced = True

index = 0

while index < len(symbolString) and balanced:

    symbol = symbolString[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(open, close):

opens = "([{"

closers = ")]}"

return opens.index(open) == closers.index(close)

print(parChecker('{{([][])}()}'))
print(parChecker('[{()]'))

运行结果：
True
False
小结：
1.栈的应用：栈是计算机语言结构处理非常重要的数据结构

2.3 十进制转换成二进制：“除 2”算法，它用栈来跟踪二进制结果的数字
“除 2” 算法假定我们从大于 0 的整数开始。不断迭代的将十进制除以 2，并跟踪余数。第一个除以 2 的余数说明了这个值是偶数还是奇数。偶数有 0 的余数，记为 0。奇数有余数 1，记为 1.我们将得到的二进制构建为数字序列，第一个余数实际上是序列中的最后一个数字。见 Figure 5 , 我们再次看到了反转的属性，表示栈可能是解决这个问题的数据结构。

![image.png](https://img.haomeiwen.com/i5172856/a81fea609c2f9656.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
ActiveCode 1

from pythonds.basic.stack import Stack

def divideBy2(decNumber):

remstack = Stack() # 创建一个栈的实例



while decNumber > 0:
    # 内置的模运算符 % 来提取余数

    rem = decNumber % 2
    # 将余数压到栈上

    remstack.push(rem)

    # 商

    decNumber = decNumber // 2
    # 初始二进制字符串为空



binString = ""

如果栈不空

while not remstack.isEmpty():

不明白：二进制字符串= 二进制字符串 + 栈中弹出的字符串？？？

    binString = binString + str(remstack.pop())

return binString

print(divideBy2(42))

扩展：扩展以执行任何基数的转换
修改 divideBy2 函数，使它不仅能接受十进制参数，还能接受预期转换的基数。‘除 2’ 的概念被简单的替换成更通用的 ‘除基数’

from pythonds.basic.stack import Stack

def baseConverter(decNumber, base):

digits = "0123456789ABCDEF"

remstack = Stack()

while decNumber > 0:

    rem = decNumber % base

    remstack.push(rem)

    decNumber = decNumber // base

newString = ""

while not remstack.isEmpty():

    newString = newString + digits[remstack.pop()]

return newString

print(baseConverter(25, 2))
print(baseConverter(25, 16))

运行结果：
11001
19
小结：
十进制化为二进制：栈实现 “除 2” 算法，栈的反转属性和不断地迭代
三步：创建不断除以2的函数，提取余数，将余数压入栈中，最后构造出一个二进制字符串
2.4 中缀前缀和后缀表达式
一种保证不会对操作顺序产生混淆的表达式的方法是创建一个称为完全括号表达式的表达式。
计算机需要准确知道要执行的操作符和顺序。一种保证不会对操作顺序产生混淆的表达式的方法是创建一个称为完全括号表达式的表达式。这种类型的表达式对每个运算符都使用一对括号。括号没有歧义的指示操作的顺序。也没有必要记住任何优先规则

前缀表达式符号要求所有运算符在它们处理的两个操作数之前
后缀要求其操作符在相应的操作数之后
A+B*C 将在前缀中写为 + A * B C ,乘法运算符紧接在操作数 B 和 C 之前，表示 * 优先于 +,然后加法运算符出现在 A 和乘法的结果之前

在后缀中，表达式将是 A B C * +，再次，操作的顺序被保留，因为 * 紧接在 B 和 C 之后出现，表示 * 具有高优先级，+ 优先级低。

![image.png](https://img.haomeiwen.com/i5172856/740452352a661c8a.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
中缀表达式 

前缀和后缀中，强制先加法
而
中缀需要括号，在乘法之前强制执行加法
![image.png](https://img.haomeiwen.com/i5172856/3b158af1f39091c2.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

为什么在前缀和后缀的时候不需要括号了呢？答案是操作符对于他们的操作数不再模糊，只有中缀才需要括号，前缀和后缀表达式的操作顺序完全由操作符的顺序决定。
2.4.1  中缀表达式转换前缀和后缀
使用特定方法在中缀表达式和等效前缀和后缀表达式符号之间进行转换
考虑的第一种技术使用前面讨论的完全括号表达式的概念
（A +（B * C））：将*移动到C后的右括号除，删除与其相匹配的左括号
得到 B C *，我们实际上已经将子表达式转换为后缀符号
加法运算符也被移动到其相应的右括号位置并且匹配的左括号被去除，
则将得到完整的后缀表达式
同样的将*和+移动到左括号的位置，删除与其相对应的右括号，我们得到前缀符号
所以为了转换表达式，无论是对前缀还是后缀符号，先根据操作的顺序把表达式转换成完全括号表达式
然后将包含的运算符移动到左或右括号的位置，具体取决于需要前缀或后缀符号。+
这里面有个更复杂的例子, (A + B) * C - (D - E) * (F + G)
 ，Figure 8 显示了如何转换为后缀和前缀。

![image.png](https://img.haomeiwen.com/i5172856/dff8dd2046bd4cac.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
2.4.3 中缀转后缀通用法

我们需要开发一个算法来将任何中缀表达式转换为后缀表达式
当我们看到左括号时，我们保存它
当右括号出现时，可以从栈中弹出操作符。
当我们从左到右扫描中缀表达式时，我们将使用栈来保留运算符
反转属性：堆栈的顶部将始终是最近保存的运算符
每当我们读取一个新的运算符时，我们
需要考虑：该运算符如何与已经在栈上的运算符（如果有的话）比较优先级
创建一个名为 opstack 的空栈以保存运算符。给输出创建一个空列表。
通过使用字符串方法拆分将输入的中缀字符串转换为标记列表。
从左到右扫描标记列表。
如果标记是操作数，将其附加到输出列表的末尾。
如果标记是左括号，将其压到 opstack 上。
如果标记是右括号，则弹出 opstack，直到删除相应的左括号。将每个运算符附加到输出列表的末尾。
如果标记是运算符，*，/，+或 - ，将其压入 opstack。但是，首先删除已经在 opstack 中具有更高或相等优先级的任何运算符，并将它们加到输出列表中。
当输入表达式被完全处理时，检查 opstack。仍然在栈上的任何运算符都可以删除并加到输出列表的末尾。
展示了对表达式 A * B + C * D 的转换算法。注意，第一个 * 在看到 + 运算符时被删除。另外，当第二个 * 出现时， + 保留在栈中，因为乘法优先级高于加法。在中缀表达式的末尾，栈被弹出两次，删除两个运算符，并将 + 作为后缀表达式中的最后一个运算符。

![image.png](https://img.haomeiwen.com/i5172856/742b72b976206c20.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
中缀转后缀通用法
在 Python 中编写算法，我们使用一个名为 prec 的字典来保存操作符的优先级。这个字典将每个运算符映射到一个整数，可以与其他运算符的优先级（我们使用整数3，2和1）进行比较。左括号将赋予最低的值。这样，与其进行比较的任何运算符将具有更高的优先级，将被放置在它的顶部。第15行将操作数定义为任何大写字符或数字
 
ActiveCode 1

from pythonds.basic.stack import Stack

def infixToPostfix(infixexpr):

prec = {}

# 名为 prec 的字典来保存操作符的优先级
prec["*"] = 3

prec["/"] = 3

prec["+"] = 2

prec["-"] = 2

prec["("] = 1

opStack = Stack()

postfixList = []

tokenList = infixexpr.split()



for token in tokenList:

    if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in  "0123456789":

        postfixList.append(token)

    elif token == '(':

        opStack.push(token)

    elif token == ')':

        topToken = opStack.pop()

        while topToken != '(':

            postfixList.append(topToken)

            topToken = opStack.pop()

    else:

        while (not opStack.isEmpty()) and \
            (prec[opStack.peek()] >= prec[token]):

                postfixList.append(opStack.pop())

        opStack.push(token)


    while not opStack.isEmpty():

        postfixList.append(opStack.pop())

    return "".join(postfixList)

print(infixToPostfix("A * B + C * D"))
print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))

print(infixToPostfix("A * B + C * D"))
print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))
print(infixToPostfix("( A + B ) * ( C + D )"))
print(infixToPostfix("( A + B ) * C"))
print(infixToPostfix("A + B * C"))
运行结果

E:\ScienceSoft\Python\project\alien_invasion>python test.py
A
(
A
(
(
(
A
程序有错

from pythonds.basic.stack import Stack

def infixToPostfix(infixexpr):
    prec = {}
    prec["*"] = 3
    prec["/"] = 3
    prec["+"] = 2
    prec["-"] = 2
    prec["("] = 1
    opStack = Stack()
    postfixList = []
    tokenList = infixexpr.split()

    for token in tokenList:
        if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":
            postfixList.append(token)
        elif token == '(':
            opStack.push(token)
        elif token == ')':
            topToken = opStack.pop()
            while topToken != '(':
                postfixList.append(topToken)
                topToken = opStack.pop()
        else:
            while (not opStack.isEmpty()) and \
               (prec[opStack.peek()] >= prec[token]):
                  postfixList.append(opStack.pop())
            opStack.push(token)

    while not opStack.isEmpty():
        postfixList.append(opStack.pop())
    return " ".join(postfixList)

print(infixToPostfix("A * B + C * D"))
print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))
print(infixToPostfix("( A + B ) * ( C + D )"))
print(infixToPostfix("( A + B ) * C"))
print(infixToPostfix("A + B * C"))
A B * C D * +
A B + C * D E - F G + * -
A B + C D + *
A B + C *
A B C * +

附录：
https://facert.gitbooks.io/python-data-structure-cn

《problem-solving-with-algorithms

A 如何编写一个算法，能够从左到右读取一串符号，并决定符号是否平衡。

如果栈不空

不明白：二进制字符串= 二进制字符串 + 栈中弹出的字符串？？？

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读