最近想学习python 脚本与爬虫的编写，先学点数据结构打点基础，看能不能进一步的了解算法思想。
其实我原来对算法还有点排斥，不知道怎么的就想不开想去学了。
就
目录
场景描述：在实际计算中 ，我们经常遇见
例子1:?? ?(5+8)*(7+8)/(1+2)
我们通过(?? )来改变计算顺序，那么计算机怎么识别这些括号正好能相对呢？
假如 不小心多打了一个（ 该怎么识别呢？，上述例子只有三个括号，正常来说不会打错。
例子2：
在Lisp的编程语言有如下语法结构
?? ?（defun square(n)
?? ??? ?(*n n))
它定义了一个名为square的函数，该函数会返回参数n的平方值。如果我们在一次运行中调用了多次
这个函数，那么存在的括号数量非常多，该怎么判断我们所有的括号都正常匹配呢？算法： 从左到右读取一个括号串，然后判断其中的括号是否匹配。
例如（（（（）））） √
?????? （（（））（）??? ×
?那么该如何设计一个算法呢，想我这样的小白基本上就无所适从了
不过，当意识到使用栈结构可以很好的解决这个问题，其实问题就应刃而解了。可以不急着理解思想，先顺着读一遍代码就行，
括号匹配问题
from pythonds.basic import Stack
def parChecker(symbolString): #定义匹配函数
s=Stack() #定义栈结构
balanced=True #平衡为Ture
index=0
while index<len(symbolString) and balanced: #进行循环，且循环中，栈平衡为Ture
symbol=symbolString[index]
if symbol=="(": #匹配到（ 就进行进栈操作
s.push(symbol)
else:
if s.isEmpty(): #如果栈为空的情况下，匹配到右括号就报错
balanced=False
else:
s.pop() #栈不为空，也就是存在左括号的情况下一旦
index+=1 #匹配到右括号 就让出栈
if balanced and s.isEmpty(): #如果匹配完成后，栈为空且平衡就返回Ture
return True
else:
return False #否则False
print(parChecker('(())()'))
print(parChecker('((()))'))进阶版，可匹配不同的括号（添加了一个matches函数）
from pythonds.basic import Stack
def matches(open, close):
opens = "([{"
closers = ")]}"
return opens.index(open) == closers.index(close)
def parChecker(symbolString):
s = Stack() #建栈
balanced = True #平衡 首先定义为Ture
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 #返回Ture
else:
return False #返回False
print(parChecker('((()())'))
print(parChecker('((([[))))'))
print(parChecker('((){})'))
多读两遍其实不难理解
- 先建立一个栈结构
- 栈里只存左括号
- 如果匹配到右括号就进行出栈操作(符合栈先进后出，后进先出的栈特性)
所以，理解栈的这种先进后出，后进先出的反转概念，对以后用栈结构解决实际问题时很有帮助。
以前我一直在想学习数据结构与算法有什么作用，甚至对搞算法有点排斥，不过静下来学之后，发现 数据结构与算法还是作用很大的，其实它是我们解决复杂问题的一个很好的工具。
有兴趣的可以看下面一个例子。
十进制转二进制
十进制转二进制问题
正整数的十进制转换二进制：
要点：除二取余，倒序排列
解释：将一个十进制数除以二，得到的商再除以二，依此类推直到商等于一或零时为止，倒取将除得的余数，即换算为二进制数的结果??例如把52换算成二进制数，计算结果如图：
52除以2得到的余数依次为：0、0、1、0、1、1，倒序排列，所以52对应的二进制数就是110100。?
可以看出我们首先得到的余数反而是放在最后面的，这就符合栈的反转特性，
from pythonds.basic import Stack
def divideBy2(decNumber):
remstack=Stack() #建立空栈
while decNumber >0: #如果大于0
rem=decNumber %2 #求余
remstack.push(rem) #将余数压入栈
decNumber=decNumber //2 #将数字除2 继续进入下一轮循环
binString=""
while not remstack.isEmpty(): #上述栈不为空的情况下
binString =binString+str(remstack.pop()) #将得到的余数压出
return binString
print(divideBy2(251))?
10进制转其他进制
from pythonds.basic 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(2534,5))
参考资料：
python数据结构与算法分析 Bradley N.Miller&David L.Ranum