一、棧

棧（stack）又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。 棧(Stack)是限制插入和刪除操作只能在一個位置進行的表，該位置是表的末端，稱為棧的頂(top)。棧的基本操作有PUSH(入棧)和POP(出棧)。棧又被稱為LIFO(后入先出)表。

二、棧的實現

class Stack(object):
  """
  棧的模擬實現
  """
  def __init__(self):
    self.stack=[]

  def isEmpty(self):
    return self.stack==[]

  def push(self,item):
    self.stack.Append(item)

  def pop(self):
    if self.isEmpty():
      raise IndexError,'pop from empty stack'
    return self.stack.pop()

  def peek(self):
    return self.stack[-1]

  def size(self):
    return len(self.stack)

三、棧的應用

1、檢查程序中成對的符號

程序的語法錯誤經常是由缺少一個符號造成的。可用棧來檢查符號是否成對。做一個空棧，如果字符是開放符號('({[')則將其push棧中。如果符號是個閉合符號(')]}'),則當棧空時報錯，對應'()}'的錯誤。否則，將棧pop，如果彈出的符號不是對應的開放符號，則報錯，對應'(}'的錯誤。文件末尾，如果棧為空，則報錯，對應'({}'的錯誤。

def match(i,j):
  opens='([{'
  closes=')]}'
  return opens.index(i)==closes.index(j)

def syntaxChecker(string):
  stack=Stack()
  balanced=True
  for i in string:
    if i in '([{':
      stack.push(i)
    elif i in ')]}':
      if stack.isEmpty():
        balanced=False
        break
      else:
        j=stack.pop()
        if not match(j,i):
          balanced=False
          break
  if not stack.isEmpty():
    balanced=False
  return balanced

2、進制轉換

十進制轉換二進制：把十進制轉成二進制一直分解至商數為0。從最底左邊數字開始讀，之后讀右邊的數字，從下讀到上。

進制轉化

def decimal_to_bin(dec):
  stack=Stack()
  cur=dec
  while cur>0:
    a=cur%2
    cur=cur/2
    stack.push(a)
  binstr=''
  while not stack.isEmpty():
    binstr+=str(stack.pop())
  return binstr

3、后綴記法
后綴記法(postfix)，使用一個棧，見到一個數時入棧，遇到一個運算符時就作用于從棧彈出的兩個元素，將結果彈入棧中。
(7+8)/(3+2)可以寫作7 8 + 3 2 + /

后綴記法

def infixtoPostfix(infix):
  a={}
  a['*']=3
  a['/']=3
  a['+']=2
  a['-']=2
  a['(']=1
  stack=Stack()
  post=''
  for i in infix:
    if i not in a and i!=')':
      post+=i
    elif i=='(':
      stack.push(i)
    elif i==')':
      top=stack.pop()
      while top!='(':
        post+=top
        top=stack.pop()
    else:     
      while not stack.isEmpty() and a[i]<=a[stack.peek()]:
        post+=stack.pop()
      stack.push(i)
  while not stack.isEmpty():
    post+=stack.pop()
  return post
           
def postfixExp(postfix):
  stack=Stack()
  postlist=postfix.split()
  for i in postlist:
    if i not in '+-*/':
      stack.push(i)
    else:
      a=stack.pop()
      b=stack.pop()
      result=math(i,b,a)
      stack.push(result)
  return stack.pop()

def math(x,y,z):
  if x=='+':
    return float(y)+float(z)
  if x=='-':
    return float(y)-float(z)
  if x=='*':
    return float(y)*float(z)
  if x=='/':
    return float(y)/float(z)