0 1 2 3 4 5 6 7 8 9 ch A B A C D next1 5 2 3 4 8 6 7 8 9 0 next2 5 2 1 4 8 2 7 8 9 0 ______________________________________ (A*B+AC)D 6 7 /--A----C----\ 5 / \ --o--\ \ 9 \ D--* 1 \2 3 4 | A---o-------B---o-- |___| ______________________________________ a = "AAABD" ______________________________________ dq int match(char *a) 1: scan =-1, N=strlen(a)=5, j = 0, state=next1[0]=5, Deque dq; start while (state) { -1 ch[state=5]=' ' n1=next1[state=5]=6 ________________ n2=next2[state=5]=2 2 dq.push(n1) 6 dq.push(n2) -1 state=dq.pop()=2 ________________ 1 2: 3 ch[state=2]=' ' 6 n1=next1[state=2]=3 -1 n2=next2[state=2]=1 push(n1), push(n2) state=dq.pop()=1 ________________ 3: 3 ch[state=1]='A'=a[j=0] 6 dq.put(next1[state=1]=2) -1 state=dq.pop()=3 2 ________________ 4: 6 ch[state=3]='B' != a[j=0]='A' -1 state=dq.pop()=6 2 ________________ 5: -1 ch[state=6]='A'=a[j=0] 2 dq.put(next1[state=6]=7) 7 state=dq.pop()=-1 ________________ 6: 2 state == scan 7 j++=1 -1 dq.put(scan=-1) ________________ state=dq.pop()=2 1 7: 3 ch[state=2]=' ' 7 n1=next1[state=2]=3 -1 n2=next2[state=2]=1 push(n1), push(n2) ________________ state=dq.pop()=1 3 7 8: -1 ch[state=1]='A'=a[j=1] 2 dq.put(next1[state=1]=2) ________________ state=dq.pop()=3 7 9: -1 ch[state=3]='B' != a[j=1]='A' 2 state=dq.pop()=7 ________________ 10: -1 ch[state=7]='C' != a[j=1]='A' 2 state=dq.pop()=-1 ________________ 11: state == scan 2 j++=2 -1 dq.put(scan=-1) ________________ state = dq.pop()=2 12: 1 ch[state=2]=' ' 3 n1=next1[state=2]=3 -1 n2=next2[state=2]=1 ________________ push(n1),push(n2) state=dq.pop()=1 3 13: -1 ch[state=1]='A'=a[j=2] 2 dq.put(next1[state=1]=2) ________________ state=dq.pop()=3 14: -1 ch[state=3]='B' != a[j=2]='A' 2 state=dq.pop()=-1 ________________ 15: 2 state == scan -1 j++=3 ________________ dq.put(scan=-1) state=dq.pop()=2 16: 1 ch[state=2]=' ' 3 n1=next1[state=2]=3 -1 n2=next2[state=2]=1 ________________ push(n1),push(n2) state=dq.pop()=1 3 17: -1 ch[state=1]='A' != a[j=3]='B' ________________ state=dq.pop()=3 18: -1 ch[state=3]='B' = a[j=3] 4 dq.put(next1[state=3]=4) ________________ state=dq.pop()=-1 4 19: -1 state == scan j++=4 dq.put(scan=-1) ________________ state=dq.pop()=4 20: ch[state=4]=' ' 8 n1=next1[state=4]=8 -1 n2=next2[state=4]=8 push(n1) ________________ state=dq.pop()=8 -1 21: 9 ch[state=8]='D' = a[j=4] dq.put(next1[state=8]=9) ________________ state=dq.pop()=-1 22: state == scan j++=5 9 dq.put(scan=-1) -1 state=dq.pop()=9 ________________ 23: ch[state=9]=' ' -1 n1=next1[state=9]=0 0 n2=next2[state=9]=0 push(n1) ________________ state=dq.pop()=-1 24: state == scan 0 j++=6 -1 dq.put(scan=-1) state=dq.pop()=0 ________________ } end while (state)