AlgorithmsByPython/Stack.py at master · DouTong/AlgorithmsByPython · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
# Python3.5
# 定义一个栈类
classStack():
# 栈的初始化
def__init__(self):
self.items= []
# 判断栈是否为空,为空返回True
defisEmpty(self):
returnself.items==[]
# 向栈内压入一个元素
defpush(self, item):
self.items.append(item)
# 从栈内推出最后一个元素
defpop(self):
returnself.items.pop()
# 返回栈顶元素
defpeek(self):
returnself.items[len(self.items)-1]
# 判断栈的大小
defsize(self):
returnlen(self.items)

# 栈属性测试
# 测试数据
# s = Stack()
# print(s.isEmpty())
# s.push(4)
# s.push('dog')
# print(s.peek())
# s.push(True)
# print(s.isEmpty())
# s.push(8.4)
# print(s.pop())
# print(s.pop())
# print(s.size())

# 利用栈将字串的字符反转
defrevstring(mystr):
# your code here
s=Stack()
outputStr=''
forcinmystr:
s.push(c)
whilenots.isEmpty():
outputStr+=s.pop()
returnoutputStr

# print(revstring('apple'))
# print(revstring('x'))
# print(revstring('1234567890'))

# 利用栈判断括号平衡Balanced parentheses
defparChecker(symbolString):
s=Stack()
balanced=True
index=0
whileindex<len(symbolString) andbalanced:
symbol=symbolString[index]
ifsymbolin'([{':
s.push(symbol)
else:
ifs.isEmpty():
balanced=False
else:
top=s.pop()
ifnotmatches(top, symbol):
balanced=False
index+=1

ifbalancedands.isEmpty():
returnTrue
else:
returnFalse

defmatches(open, close):
opens='([{'
closers=')]}'
returnopens.index(open) ==closers.index(close)

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

# 利用栈将十进制整数转化为二进制整数
defDec2Bin(decNumber):
s=Stack()

whiledecNumber>0:
temp=decNumber%2
s.push(temp)
decNumber=decNumber//2
binString=''
whilenots.isEmpty():
binString+=str(s.pop())
returnbinString

# print(Dec2Bin(42))

# 利用栈实现多进制转换
defbaseConverter(decNumber, base):
digits='0123456789ABCDEF'

s=Stack()

whiledecNumber>0:
temp=decNumber%base
s.push(temp)
decNumber=decNumber//base

newString=''
whilenots.isEmpty():
newString=newString+digits[s.pop()]

returnnewString

# print(baseConverter(59, 16))

# 利用栈实现普通多项式的后缀表达式
definfixToPostfix(infixexpr):
prec= {}
prec['*'] =3
prec['/'] =3
prec['+'] =2
prec['-'] =2
prec['('] =1
opStack=Stack()
postfixList= []
tokenList=infixexpr.split()

fortokenintokenList:
iftokenin'ABCDEFGHIJKLMNOPQRSTUVWXYZ'ortokenin'0123456789':
postfixList.append(token)
eliftoken=='(':
opStack.push(token)
eliftoken==')':
topToken=opStack.pop()
whiletopToken!='(':
postfixList.append(topToken)
topToken=opStack.pop()
else:
while (notopStack.isEmpty()) and (prec[opStack.peek()] >=prec[token]):
postfixList.append(opStack.pop())
opStack.push(token)

whilenotopStack.isEmpty():
postfixList.append(opStack.pop())

return''.join(postfixList)

# print(infixToPostfix("A * B + C * D"))
# print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
# Python3.5
# 定义一个栈类
classStack():
# 栈的初始化
def__init__(self):
self.items= []
# 判断栈是否为空,为空返回True
defisEmpty(self):
returnself.items==[]
# 向栈内压入一个元素
defpush(self, item):
self.items.append(item)
# 从栈内推出最后一个元素
defpop(self):
returnself.items.pop()
# 返回栈顶元素
defpeek(self):
returnself.items[len(self.items)-1]
# 判断栈的大小
defsize(self):
returnlen(self.items)

# 栈属性测试
# 测试数据
# s = Stack()
# print(s.isEmpty())
# s.push(4)
# s.push('dog')
# print(s.peek())
# s.push(True)
# print(s.isEmpty())
# s.push(8.4)
# print(s.pop())
# print(s.pop())
# print(s.size())

# 利用栈将字串的字符反转
defrevstring(mystr):
# your code here
s=Stack()
outputStr=''
forcinmystr:
s.push(c)
whilenots.isEmpty():
outputStr+=s.pop()
returnoutputStr

# print(revstring('apple'))
# print(revstring('x'))
# print(revstring('1234567890'))

# 利用栈判断括号平衡Balanced parentheses
defparChecker(symbolString):
s=Stack()
balanced=True
index=0
whileindex<len(symbolString) andbalanced:
symbol=symbolString[index]
ifsymbolin'([{':
s.push(symbol)
else:
ifs.isEmpty():
balanced=False
else:
top=s.pop()
ifnotmatches(top, symbol):
balanced=False
index+=1

ifbalancedands.isEmpty():
returnTrue
else:
returnFalse

defmatches(open, close):
opens='([{'
closers=')]}'
returnopens.index(open) ==closers.index(close)

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

# 利用栈将十进制整数转化为二进制整数
defDec2Bin(decNumber):
s=Stack()

whiledecNumber>0:
temp=decNumber%2
s.push(temp)
decNumber=decNumber//2
binString=''
whilenots.isEmpty():
binString+=str(s.pop())
returnbinString

# print(Dec2Bin(42))

# 利用栈实现多进制转换
defbaseConverter(decNumber, base):
digits='0123456789ABCDEF'

s=Stack()

whiledecNumber>0:
temp=decNumber%base
s.push(temp)
decNumber=decNumber//base

newString=''
whilenots.isEmpty():
newString=newString+digits[s.pop()]

returnnewString

# print(baseConverter(59, 16))

# 利用栈实现普通多项式的后缀表达式
definfixToPostfix(infixexpr):
prec= {}
prec['*'] =3
prec['/'] =3
prec['+'] =2
prec['-'] =2
prec['('] =1
opStack=Stack()
postfixList= []
tokenList=infixexpr.split()

fortokenintokenList:
iftokenin'ABCDEFGHIJKLMNOPQRSTUVWXYZ'ortokenin'0123456789':
postfixList.append(token)
eliftoken=='(':
opStack.push(token)
eliftoken==')':
topToken=opStack.pop()
whiletopToken!='(':
postfixList.append(topToken)
topToken=opStack.pop()
else:
while (notopStack.isEmpty()) and (prec[opStack.peek()] >=prec[token]):
postfixList.append(opStack.pop())
opStack.push(token)

whilenotopStack.isEmpty():
postfixList.append(opStack.pop())

return''.join(postfixList)

# print(infixToPostfix("A * B + C * D"))
# print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
# Python3.5
# 定义一个栈类
classStack():
# 栈的初始化
def__init__(self):
self.items= []
# 判断栈是否为空,为空返回True
defisEmpty(self):
returnself.items==[]
# 向栈内压入一个元素
defpush(self, item):
self.items.append(item)
# 从栈内推出最后一个元素
defpop(self):
returnself.items.pop()
# 返回栈顶元素
defpeek(self):
returnself.items[len(self.items)-1]
# 判断栈的大小
defsize(self):
returnlen(self.items)

# 栈属性测试
# 测试数据
# s = Stack()
# print(s.isEmpty())
# s.push(4)
# s.push('dog')
# print(s.peek())
# s.push(True)
# print(s.isEmpty())
# s.push(8.4)
# print(s.pop())
# print(s.pop())
# print(s.size())

# 利用栈将字串的字符反转
defrevstring(mystr):
# your code here
s=Stack()
outputStr=''
forcinmystr:
s.push(c)
whilenots.isEmpty():
outputStr+=s.pop()
returnoutputStr

# print(revstring('apple'))
# print(revstring('x'))
# print(revstring('1234567890'))

# 利用栈判断括号平衡Balanced parentheses
defparChecker(symbolString):
s=Stack()
balanced=True
index=0
whileindex<len(symbolString) andbalanced:
symbol=symbolString[index]
ifsymbolin'([{':
s.push(symbol)
else:
ifs.isEmpty():
balanced=False
else:
top=s.pop()
ifnotmatches(top, symbol):
balanced=False
index+=1

ifbalancedands.isEmpty():
returnTrue
else:
returnFalse

defmatches(open, close):
opens='([{'
closers=')]}'
returnopens.index(open) ==closers.index(close)

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

# 利用栈将十进制整数转化为二进制整数
defDec2Bin(decNumber):
s=Stack()

whiledecNumber>0:
temp=decNumber%2
s.push(temp)
decNumber=decNumber//2
binString=''
whilenots.isEmpty():
binString+=str(s.pop())
returnbinString

# print(Dec2Bin(42))

# 利用栈实现多进制转换
defbaseConverter(decNumber, base):
digits='0123456789ABCDEF'

s=Stack()

whiledecNumber>0:
temp=decNumber%base
s.push(temp)
decNumber=decNumber//base

newString=''
whilenots.isEmpty():
newString=newString+digits[s.pop()]

returnnewString

# print(baseConverter(59, 16))

# 利用栈实现普通多项式的后缀表达式
definfixToPostfix(infixexpr):
prec= {}
prec['*'] =3
prec['/'] =3
prec['+'] =2
prec['-'] =2
prec['('] =1
opStack=Stack()
postfixList= []
tokenList=infixexpr.split()

fortokenintokenList:
iftokenin'ABCDEFGHIJKLMNOPQRSTUVWXYZ'ortokenin'0123456789':
postfixList.append(token)
eliftoken=='(':
opStack.push(token)
eliftoken==')':
topToken=opStack.pop()
whiletopToken!='(':
postfixList.append(topToken)
topToken=opStack.pop()
else:
while (notopStack.isEmpty()) and (prec[opStack.peek()] >=prec[token]):
postfixList.append(opStack.pop())
opStack.push(token)

whilenotopStack.isEmpty():
postfixList.append(opStack.pop())

return''.join(postfixList)

# print(infixToPostfix("A * B + C * D"))
# print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
# Python3.5
# 定义一个栈类
classStack():
# 栈的初始化
def__init__(self):
self.items= []
# 判断栈是否为空,为空返回True
defisEmpty(self):
returnself.items==[]
# 向栈内压入一个元素
defpush(self, item):
self.items.append(item)
# 从栈内推出最后一个元素
defpop(self):
returnself.items.pop()
# 返回栈顶元素
defpeek(self):
returnself.items[len(self.items)-1]
# 判断栈的大小
defsize(self):
returnlen(self.items)

# 栈属性测试
# 测试数据
# s = Stack()
# print(s.isEmpty())
# s.push(4)
# s.push('dog')
# print(s.peek())
# s.push(True)
# print(s.isEmpty())
# s.push(8.4)
# print(s.pop())
# print(s.pop())
# print(s.size())

# 利用栈将字串的字符反转
defrevstring(mystr):
# your code here
s=Stack()
outputStr=''
forcinmystr:
s.push(c)
whilenots.isEmpty():
outputStr+=s.pop()
returnoutputStr

# print(revstring('apple'))
# print(revstring('x'))
# print(revstring('1234567890'))

# 利用栈判断括号平衡Balanced parentheses
defparChecker(symbolString):
s=Stack()
balanced=True
index=0
whileindex<len(symbolString) andbalanced:
symbol=symbolString[index]
ifsymbolin'([{':
s.push(symbol)
else:
ifs.isEmpty():
balanced=False
else:
top=s.pop()
ifnotmatches(top, symbol):
balanced=False
index+=1

ifbalancedands.isEmpty():
returnTrue
else:
returnFalse

defmatches(open, close):
opens='([{'
closers=')]}'
returnopens.index(open) ==closers.index(close)

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

# 利用栈将十进制整数转化为二进制整数
defDec2Bin(decNumber):
s=Stack()

whiledecNumber>0:
temp=decNumber%2
s.push(temp)
decNumber=decNumber//2
binString=''
whilenots.isEmpty():
binString+=str(s.pop())
returnbinString

# print(Dec2Bin(42))

# 利用栈实现多进制转换
defbaseConverter(decNumber, base):
digits='0123456789ABCDEF'

s=Stack()

whiledecNumber>0:
temp=decNumber%base
s.push(temp)
decNumber=decNumber//base

newString=''
whilenots.isEmpty():
newString=newString+digits[s.pop()]

returnnewString

# print(baseConverter(59, 16))

# 利用栈实现普通多项式的后缀表达式
definfixToPostfix(infixexpr):
prec= {}
prec['*'] =3
prec['/'] =3
prec['+'] =2
prec['-'] =2
prec['('] =1
opStack=Stack()
postfixList= []
tokenList=infixexpr.split()

fortokenintokenList:
iftokenin'ABCDEFGHIJKLMNOPQRSTUVWXYZ'ortokenin'0123456789':
postfixList.append(token)
eliftoken=='(':
opStack.push(token)
eliftoken==')':
topToken=opStack.pop()
whiletopToken!='(':
postfixList.append(topToken)
topToken=opStack.pop()
else:
while (notopStack.isEmpty()) and (prec[opStack.peek()] >=prec[token]):
postfixList.append(opStack.pop())
opStack.push(token)

whilenotopStack.isEmpty():
postfixList.append(opStack.pop())

return''.join(postfixList)

# print(infixToPostfix("A * B + C * D"))
# print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
# Python3.5
# 定义一个栈类
classStack():
# 栈的初始化
def__init__(self):
self.items= []
# 判断栈是否为空,为空返回True
defisEmpty(self):
returnself.items==[]
# 向栈内压入一个元素
defpush(self, item):
self.items.append(item)
# 从栈内推出最后一个元素
defpop(self):
returnself.items.pop()
# 返回栈顶元素
defpeek(self):
returnself.items[len(self.items)-1]
# 判断栈的大小
defsize(self):
returnlen(self.items)

# 栈属性测试
# 测试数据
# s = Stack()
# print(s.isEmpty())
# s.push(4)
# s.push('dog')
# print(s.peek())
# s.push(True)
# print(s.isEmpty())
# s.push(8.4)
# print(s.pop())
# print(s.pop())
# print(s.size())

# 利用栈将字串的字符反转
defrevstring(mystr):
# your code here
s=Stack()
outputStr=''
forcinmystr:
s.push(c)
whilenots.isEmpty():
outputStr+=s.pop()
returnoutputStr

# print(revstring('apple'))
# print(revstring('x'))
# print(revstring('1234567890'))

# 利用栈判断括号平衡Balanced parentheses
defparChecker(symbolString):
s=Stack()
balanced=True
index=0
whileindex<len(symbolString) andbalanced:
symbol=symbolString[index]
ifsymbolin'([{':
s.push(symbol)
else:
ifs.isEmpty():
balanced=False
else:
top=s.pop()
ifnotmatches(top, symbol):
balanced=False
index+=1

ifbalancedands.isEmpty():
returnTrue
else:
returnFalse

defmatches(open, close):
opens='([{'
closers=')]}'
returnopens.index(open) ==closers.index(close)

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

# 利用栈将十进制整数转化为二进制整数
defDec2Bin(decNumber):
s=Stack()

whiledecNumber>0:
temp=decNumber%2
s.push(temp)
decNumber=decNumber//2
binString=''
whilenots.isEmpty():
binString+=str(s.pop())
returnbinString

# print(Dec2Bin(42))

# 利用栈实现多进制转换
defbaseConverter(decNumber, base):
digits='0123456789ABCDEF'

s=Stack()

whiledecNumber>0:
temp=decNumber%base
s.push(temp)
decNumber=decNumber//base

newString=''
whilenots.isEmpty():
newString=newString+digits[s.pop()]

returnnewString

# print(baseConverter(59, 16))

# 利用栈实现普通多项式的后缀表达式
definfixToPostfix(infixexpr):
prec= {}
prec['*'] =3
prec['/'] =3
prec['+'] =2
prec['-'] =2
prec['('] =1
opStack=Stack()
postfixList= []
tokenList=infixexpr.split()

fortokenintokenList:
iftokenin'ABCDEFGHIJKLMNOPQRSTUVWXYZ'ortokenin'0123456789':
postfixList.append(token)
eliftoken=='(':
opStack.push(token)
eliftoken==')':
topToken=opStack.pop()
whiletopToken!='(':
postfixList.append(topToken)
topToken=opStack.pop()
else:
while (notopStack.isEmpty()) and (prec[opStack.peek()] >=prec[token]):
postfixList.append(opStack.pop())
opStack.push(token)

whilenotopStack.isEmpty():
postfixList.append(opStack.pop())

return''.join(postfixList)

# print(infixToPostfix("A * B + C * D"))
# print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
# Python3.5
# 定义一个栈类
classStack():
# 栈的初始化
def__init__(self):
self.items= []
# 判断栈是否为空,为空返回True
defisEmpty(self):
returnself.items==[]
# 向栈内压入一个元素
defpush(self, item):
self.items.append(item)
# 从栈内推出最后一个元素
defpop(self):
returnself.items.pop()
# 返回栈顶元素
defpeek(self):
returnself.items[len(self.items)-1]
# 判断栈的大小
defsize(self):
returnlen(self.items)

# 栈属性测试
# 测试数据
# s = Stack()
# print(s.isEmpty())
# s.push(4)
# s.push('dog')
# print(s.peek())
# s.push(True)
# print(s.isEmpty())
# s.push(8.4)
# print(s.pop())
# print(s.pop())
# print(s.size())

# 利用栈将字串的字符反转
defrevstring(mystr):
# your code here
s=Stack()
outputStr=''
forcinmystr:
s.push(c)
whilenots.isEmpty():
outputStr+=s.pop()
returnoutputStr

# print(revstring('apple'))
# print(revstring('x'))
# print(revstring('1234567890'))

# 利用栈判断括号平衡Balanced parentheses
defparChecker(symbolString):
s=Stack()
balanced=True
index=0
whileindex<len(symbolString) andbalanced:
symbol=symbolString[index]
ifsymbolin'([{':
s.push(symbol)
else:
ifs.isEmpty():
balanced=False
else:
top=s.pop()
ifnotmatches(top, symbol):
balanced=False
index+=1

ifbalancedands.isEmpty():
returnTrue
else:
returnFalse

defmatches(open, close):
opens='([{'
closers=')]}'
returnopens.index(open) ==closers.index(close)

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

# 利用栈将十进制整数转化为二进制整数
defDec2Bin(decNumber):
s=Stack()

whiledecNumber>0:
temp=decNumber%2
s.push(temp)
decNumber=decNumber//2
binString=''
whilenots.isEmpty():
binString+=str(s.pop())
returnbinString

# print(Dec2Bin(42))

# 利用栈实现多进制转换
defbaseConverter(decNumber, base):
digits='0123456789ABCDEF'

s=Stack()

whiledecNumber>0:
temp=decNumber%base
s.push(temp)
decNumber=decNumber//base

newString=''
whilenots.isEmpty():
newString=newString+digits[s.pop()]

returnnewString

# print(baseConverter(59, 16))

# 利用栈实现普通多项式的后缀表达式
definfixToPostfix(infixexpr):
prec= {}
prec['*'] =3
prec['/'] =3
prec['+'] =2
prec['-'] =2
prec['('] =1
opStack=Stack()
postfixList= []
tokenList=infixexpr.split()

fortokenintokenList:
iftokenin'ABCDEFGHIJKLMNOPQRSTUVWXYZ'ortokenin'0123456789':
postfixList.append(token)
eliftoken=='(':
opStack.push(token)
eliftoken==')':
topToken=opStack.pop()
whiletopToken!='(':
postfixList.append(topToken)
topToken=opStack.pop()
else:
while (notopStack.isEmpty()) and (prec[opStack.peek()] >=prec[token]):
postfixList.append(opStack.pop())
opStack.push(token)

whilenotopStack.isEmpty():
postfixList.append(opStack.pop())

return''.join(postfixList)

# print(infixToPostfix("A * B + C * D"))
# print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
# Python3.5
# 定义一个栈类
classStack():
# 栈的初始化
def__init__(self):
self.items= []
# 判断栈是否为空,为空返回True
defisEmpty(self):
returnself.items==[]
# 向栈内压入一个元素
defpush(self, item):
self.items.append(item)
# 从栈内推出最后一个元素
defpop(self):
returnself.items.pop()
# 返回栈顶元素
defpeek(self):
returnself.items[len(self.items)-1]
# 判断栈的大小
defsize(self):
returnlen(self.items)

# 栈属性测试
# 测试数据
# s = Stack()
# print(s.isEmpty())
# s.push(4)
# s.push('dog')
# print(s.peek())
# s.push(True)
# print(s.isEmpty())
# s.push(8.4)
# print(s.pop())
# print(s.pop())
# print(s.size())

# 利用栈将字串的字符反转
defrevstring(mystr):
# your code here
s=Stack()
outputStr=''
forcinmystr:
s.push(c)
whilenots.isEmpty():
outputStr+=s.pop()
returnoutputStr

# print(revstring('apple'))
# print(revstring('x'))
# print(revstring('1234567890'))

# 利用栈判断括号平衡Balanced parentheses
defparChecker(symbolString):
s=Stack()
balanced=True
index=0
whileindex<len(symbolString) andbalanced:
symbol=symbolString[index]
ifsymbolin'([{':
s.push(symbol)
else:
ifs.isEmpty():
balanced=False
else:
top=s.pop()
ifnotmatches(top, symbol):
balanced=False
index+=1

ifbalancedands.isEmpty():
returnTrue
else:
returnFalse

defmatches(open, close):
opens='([{'
closers=')]}'
returnopens.index(open) ==closers.index(close)

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

# 利用栈将十进制整数转化为二进制整数
defDec2Bin(decNumber):
s=Stack()

whiledecNumber>0:
temp=decNumber%2
s.push(temp)
decNumber=decNumber//2
binString=''
whilenots.isEmpty():
binString+=str(s.pop())
returnbinString

# print(Dec2Bin(42))

# 利用栈实现多进制转换
defbaseConverter(decNumber, base):
digits='0123456789ABCDEF'

s=Stack()

whiledecNumber>0:
temp=decNumber%base
s.push(temp)
decNumber=decNumber//base

newString=''
whilenots.isEmpty():
newString=newString+digits[s.pop()]

returnnewString

# print(baseConverter(59, 16))

# 利用栈实现普通多项式的后缀表达式
definfixToPostfix(infixexpr):
prec= {}
prec['*'] =3
prec['/'] =3
prec['+'] =2
prec['-'] =2
prec['('] =1
opStack=Stack()
postfixList= []
tokenList=infixexpr.split()

fortokenintokenList:
iftokenin'ABCDEFGHIJKLMNOPQRSTUVWXYZ'ortokenin'0123456789':
postfixList.append(token)
eliftoken=='(':
opStack.push(token)
eliftoken==')':
topToken=opStack.pop()
whiletopToken!='(':
postfixList.append(topToken)
topToken=opStack.pop()
else:
while (notopStack.isEmpty()) and (prec[opStack.peek()] >=prec[token]):
postfixList.append(opStack.pop())
opStack.push(token)

whilenotopStack.isEmpty():
postfixList.append(opStack.pop())

return''.join(postfixList)

# print(infixToPostfix("A * B + C * D"))
# print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
# Python3.5
# 定义一个栈类
classStack():
# 栈的初始化
def__init__(self):
self.items= []
# 判断栈是否为空,为空返回True
defisEmpty(self):
returnself.items==[]
# 向栈内压入一个元素
defpush(self, item):
self.items.append(item)
# 从栈内推出最后一个元素
defpop(self):
returnself.items.pop()
# 返回栈顶元素
defpeek(self):
returnself.items[len(self.items)-1]
# 判断栈的大小
defsize(self):
returnlen(self.items)

# 栈属性测试
# 测试数据
# s = Stack()
# print(s.isEmpty())
# s.push(4)
# s.push('dog')
# print(s.peek())
# s.push(True)
# print(s.isEmpty())
# s.push(8.4)
# print(s.pop())
# print(s.pop())
# print(s.size())

# 利用栈将字串的字符反转
defrevstring(mystr):
# your code here
s=Stack()
outputStr=''
forcinmystr:
s.push(c)
whilenots.isEmpty():
outputStr+=s.pop()
returnoutputStr

# print(revstring('apple'))
# print(revstring('x'))
# print(revstring('1234567890'))

# 利用栈判断括号平衡Balanced parentheses
defparChecker(symbolString):
s=Stack()
balanced=True
index=0
whileindex<len(symbolString) andbalanced:
symbol=symbolString[index]
ifsymbolin'([{':
s.push(symbol)
else:
ifs.isEmpty():
balanced=False
else:
top=s.pop()
ifnotmatches(top, symbol):
balanced=False
index+=1

ifbalancedands.isEmpty():
returnTrue
else:
returnFalse

defmatches(open, close):
opens='([{'
closers=')]}'
returnopens.index(open) ==closers.index(close)

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

# 利用栈将十进制整数转化为二进制整数
defDec2Bin(decNumber):
s=Stack()

whiledecNumber>0:
temp=decNumber%2
s.push(temp)
decNumber=decNumber//2
binString=''
whilenots.isEmpty():
binString+=str(s.pop())
returnbinString

# print(Dec2Bin(42))

# 利用栈实现多进制转换
defbaseConverter(decNumber, base):
digits='0123456789ABCDEF'

s=Stack()

whiledecNumber>0:
temp=decNumber%base
s.push(temp)
decNumber=decNumber//base

newString=''
whilenots.isEmpty():
newString=newString+digits[s.pop()]

returnnewString

# print(baseConverter(59, 16))

# 利用栈实现普通多项式的后缀表达式
definfixToPostfix(infixexpr):
prec= {}
prec['*'] =3
prec['/'] =3
prec['+'] =2
prec['-'] =2
prec['('] =1
opStack=Stack()
postfixList= []
tokenList=infixexpr.split()

fortokenintokenList:
iftokenin'ABCDEFGHIJKLMNOPQRSTUVWXYZ'ortokenin'0123456789':
postfixList.append(token)
eliftoken=='(':
opStack.push(token)
eliftoken==')':
topToken=opStack.pop()
whiletopToken!='(':
postfixList.append(topToken)
topToken=opStack.pop()
else:
while (notopStack.isEmpty()) and (prec[opStack.peek()] >=prec[token]):
postfixList.append(opStack.pop())
opStack.push(token)

whilenotopStack.isEmpty():
postfixList.append(opStack.pop())

return''.join(postfixList)

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