Skip to content

Commit 73384fb

Browse files
ZZJwniZZJwni
committed
upload code
1 parent b22ffb5 commit 73384fb

File tree

3 files changed

+577
-5
lines changed

3 files changed

+577
-5
lines changed

‎Python-DataStructures/.ipynb_checkpoints/Stack-checkpoint.ipynb‎

Lines changed: 241 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,245 @@
11
{
2-
"cells": [],
3-
"metadata": {},
2+
"cells": [
3+
{
4+
"cell_type": "markdown",
5+
"metadata": {
6+
"toc": true
7+
},
8+
"source": [
9+
"<h1>Table of Contents<span class=\"tocSkip\"></span></h1>\n",
10+
"<div class=\"toc\"><ul class=\"toc-item\"><li><span><a href=\"#应用:-括号匹配\" data-toc-modified-id=\"应用:-括号匹配-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>应用: 括号匹配</a></span></li><li><span><a href=\"#算数表达式\" data-toc-modified-id=\"算数表达式-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>算数表达式</a></span></li></ul></div>"
11+
]
12+
},
13+
{
14+
"cell_type": "code",
15+
"execution_count": 48,
16+
"metadata": {
17+
"ExecuteTime": {
18+
"end_time": "2019-07-31T13:38:00.983192Z",
19+
"start_time": "2019-07-31T13:38:00.973532Z"
20+
}
21+
},
22+
"outputs": [
23+
{
24+
"ename": "IndentationError",
25+
"evalue": "expected an indented block (<ipython-input-48-748202a546cf>, line 6)",
26+
"output_type": "error",
27+
"traceback": [
28+
"\u001b[0;36m File \u001b[0;32m\"<ipython-input-48-748202a546cf>\"\u001b[0;36m, line \u001b[0;32m6\u001b[0m\n\u001b[0;31m else:\u001b[0m\n\u001b[0m ^\u001b[0m\n\u001b[0;31mIndentationError\u001b[0m\u001b[0;31m:\u001b[0m expected an indented block\n"
29+
]
30+
}
31+
],
32+
"source": [
33+
"class LinkedStack(object):\n",
34+
" def __init__(self, items=None):\n",
35+
" if items_ is None:\n",
36+
" self._list = []\n",
37+
" elif isinstance(items_, LinkedStack):\n",
38+
" self._list = \n",
39+
" else:\n",
40+
" self._list = list(list_)\n",
41+
"\n",
42+
" def __len__(self):\n",
43+
" return len(self._list)\n",
44+
"\n",
45+
" def isEmpty(self):\n",
46+
" if self.__len__() == 0:\n",
47+
" return True\n",
48+
" else:\n",
49+
" return False\n",
50+
"\n",
51+
" def __str__(self):\n",
52+
" return str(self._list)\n",
53+
"\n",
54+
" def __iter__(self):\n",
55+
" return (s for s in self._list)\n",
56+
"\n",
57+
" def __contains__(self, item):\n",
58+
" return item in self._list\n",
59+
"\n",
60+
" def __add__(self, s):\n",
61+
" if isinstance(s, LinkedStack):\n",
62+
" return LinkedStack(self._list + s._list)\n",
63+
"\n",
64+
" def __eq__(self, s):\n",
65+
" if not isinstance(s, LinkedStack):\n",
66+
" return False\n",
67+
" if not self.__len__() == len(s):\n",
68+
" return False\n",
69+
" for e1, e2 in zip(self, s):\n",
70+
" if e1 != e2:\n",
71+
" return False\n",
72+
" return True\n",
73+
"\n",
74+
" def clear(self):\n",
75+
" self._list = []\n",
76+
"\n",
77+
" def peek(self):\n",
78+
" if self.isEmpty():\n",
79+
" raise KeyError\n",
80+
" return self._list[-1]\n",
81+
"\n",
82+
" def push(self, item):\n",
83+
" self._list.append(item)\n",
84+
"\n",
85+
" def pop(self):\n",
86+
" if self.isEmpty():\n",
87+
" raise KeyError\n",
88+
" return self._list.pop()"
89+
]
90+
},
91+
{
92+
"cell_type": "code",
93+
"execution_count": null,
94+
"metadata": {},
95+
"outputs": [],
96+
"source": [
97+
"def test(stackType): # Test any implementation with the same code \n",
98+
" s = stackType() \n",
99+
" print(\"Length:\", len(s)) \n",
100+
" print(\"Empty:\", s.isEmpty()) \n",
101+
" print(\"Push 1-10\") \n",
102+
" for i in range(10): \n",
103+
" s.push(i + 1) \n",
104+
" print(\"Peeking:\", s.peek()) \n",
105+
" print(\"Items (bottom to top):\", s) \n",
106+
" print(\"Length:\", len(s)) \n",
107+
" print(\"Empty:\", s.isEmpty()) \n",
108+
" theClone = stackType(s) \n",
109+
" print(\"Items in clone (bottom to top):\", theClone) theClone.clear() print(\"Length of clone after clear:\", len(theClone)) print(\"Push 11\") s.push(11) print(\"Popping items (top to bottom):\", end=\"\") while not s.isEmpty(): print(s.pop(), end=\" \") print(\"\\nLength:\", len(s)) print(\"Empty:\", s.isEmpty())"
110+
]
111+
},
112+
{
113+
"cell_type": "code",
114+
"execution_count": 22,
115+
"metadata": {
116+
"ExecuteTime": {
117+
"end_time": "2019-07-31T13:02:58.012394Z",
118+
"start_time": "2019-07-31T13:02:58.010123Z"
119+
}
120+
},
121+
"outputs": [],
122+
"source": [
123+
"# 使用:\n",
124+
"\n",
125+
"# s = LinkedStack()\n",
126+
"# s.push(1)\n",
127+
"# s.push(2)\n",
128+
"# s.push(3)\n",
129+
"# s.isEmpty()\n",
130+
"# len(s)\n",
131+
"# s.peek()\n",
132+
"# s.pop()\n",
133+
"# s.pop()\n",
134+
"# s.pop()\n",
135+
"# s.peek()\n",
136+
"# s.pop()\n",
137+
"# s.push(4)\n",
138+
"# str(s)"
139+
]
140+
},
141+
{
142+
"cell_type": "markdown",
143+
"metadata": {},
144+
"source": [
145+
"###### 应用: 括号匹配"
146+
]
147+
},
148+
{
149+
"cell_type": "code",
150+
"execution_count": 47,
151+
"metadata": {
152+
"ExecuteTime": {
153+
"end_time": "2019-07-31T13:28:06.852814Z",
154+
"start_time": "2019-07-31T13:28:06.848021Z"
155+
}
156+
},
157+
"outputs": [],
158+
"source": [
159+
"def brackets_balance(exp):\n",
160+
" \"\"\"exp 是字符串, 代表着一个表达式.\n",
161+
" \"\"\"\n",
162+
" stack = LinkedStack()\n",
163+
" if len(exp) == 0: return True\n",
164+
" for e in exp:\n",
165+
" if e in ('(', '['):\n",
166+
" stack.push(e)\n",
167+
" elif e in (')', '}'):\n",
168+
" if stack.isEmpty():\n",
169+
" return False\n",
170+
" elif (stack.peek() != '(' and e == ')') or\\\n",
171+
" (stack.peek() != '[' and e == ']'):\n",
172+
" return False\n",
173+
" else:\n",
174+
" stack.pop()\n",
175+
" return stac.isEmpty()"
176+
]
177+
},
178+
{
179+
"cell_type": "code",
180+
"execution_count": 46,
181+
"metadata": {
182+
"ExecuteTime": {
183+
"end_time": "2019-07-31T13:22:09.769754Z",
184+
"start_time": "2019-07-31T13:22:09.767605Z"
185+
}
186+
},
187+
"outputs": [],
188+
"source": [
189+
"# brackets_balance('(...)...(...)')\n",
190+
"# brackets_balance('(...)...(...')\n",
191+
"# brackets_balance(')...(...(...)')\n",
192+
"# brackets_balance('[...(...)...]')\n",
193+
"# brackets_balance('[...(...]...]')"
194+
]
195+
},
196+
{
197+
"cell_type": "markdown",
198+
"metadata": {},
199+
"source": [
200+
"###### 算数表达式"
201+
]
202+
},
203+
{
204+
"cell_type": "code",
205+
"execution_count": null,
206+
"metadata": {},
207+
"outputs": [],
208+
"source": []
209+
}
210+
],
211+
"metadata": {
212+
"kernelspec": {
213+
"display_name": "Python 3",
214+
"language": "python",
215+
"name": "python3"
216+
},
217+
"language_info": {
218+
"codemirror_mode": {
219+
"name": "ipython",
220+
"version": 3
221+
},
222+
"file_extension": ".py",
223+
"mimetype": "text/x-python",
224+
"name": "python",
225+
"nbconvert_exporter": "python",
226+
"pygments_lexer": "ipython3",
227+
"version": "3.6.7"
228+
},
229+
"toc": {
230+
"base_numbering": 1,
231+
"nav_menu": {},
232+
"number_sections": true,
233+
"sideBar": true,
234+
"skip_h1_title": true,
235+
"title_cell": "Table of Contents",
236+
"title_sidebar": "Contents",
237+
"toc_cell": true,
238+
"toc_position": {},
239+
"toc_section_display": true,
240+
"toc_window_display": true
241+
}
242+
},
4243
"nbformat": 4,
5244
"nbformat_minor": 2
6245
}

0 commit comments

Comments
 (0)