系列文章参考资料为《大话数据结构》，源码为个人私有，未经允许不得转载

技术交流群或资料添加微信号：CoderAllen，回复关键字即可

主要用后缀（逆波兰）表达式做栈的现实
0.前言
我们都知道四则运算是很简单，尤其还可以使用计算器，不过对于涉及算式中带有大中小括号的四则运算，这时候简单的计算器就不好用了
比如：



这里边的困难在于乘除在加减的后面，却要先运算，加了括号就变得更复杂了
原理：

不过仔细观察的话，这里边括号都是成对出现的，所以可以利用栈来实现，只要碰到左括号，就将此左括号进栈，不管表达式有多少重括号，反正遇到左括号就进栈，而后面的出现右括号的时候，就让栈顶的左括号出栈，期间让数字运算，这样，最好有括号的表达式从左到右巡查一遍，栈应该是由空到有元素，最后在因全部匹配成功后成为空栈的结果
但是对于四则运算，括号也只是其中的一部分，先乘除后加减使得问题依然复杂，这时候就引出了逆波兰表达式 - 一种不需要括号的后缀表达法


要用后缀表达式应该是



叫后缀的原因是所有的符号都是要在运算数字的后边出现
1.如何获得后缀表达式
我们平时的标准四则远算表达式，叫做中缀表达式
下边就看下



规则：

从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；

若是符号，则判断其与栈顶符号的优先级，是右括号或者优先级低于栈顶符号，则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止
1.初始化一个空栈，用来对符号进行出栈使用








2.利用栈计算后缀表达式
下边看看计算式是如何计算逆波兰表达式的

1.初始化空栈

2.后缀表达式中前三都是数字，所以 9 3 1 进栈



3.下边的“-”，所以栈中的1 出栈做减数，3出栈做被减数，运算得到2，再把2进栈

4.接着是3进栈



5.后边的乘号“*”，就是栈中的3和2出栈相乘，得到6，在进栈

6.下边的“+”，则6和9出栈相加得到15，在把15进栈



7.然后是10和2两个数字进栈

8.再然后是符号“/”，栈顶的2和10出栈相除得到5，然后5进栈



9.最后一个符号“+”，所以15和5出栈相加，得到20在入栈

10.结果是20出栈，栈变空



从上述推导可以发现，要想计算机具有处理我们通常的标准（中缀）表达式的能力，最重要的就是两步

1.将中缀表达式转化为后缀表达式（栈用来进出运算的符号）

2.将后缀表达式进行运算得出结果（栈用来进出运算的数字）
整个过程都充分利用了栈的先进后出的特性，可以非常好的理解栈这个数据结构

元组 tuple


列表数是可变序列，可以任意修改列表中的元素。


元组数是不可变序列，不能修改元组中的元素。


因此，元组没有增加元素、修改元素、删除元素相关的方法。


只需要元组的创建和删除，元组中元素的访问和计数即可。


元组支持操作：

1，索引访问

2，切片操作

3，连接操作

4，成员关系操作

5，比较运算操作

6，计数



元组的创建
通过（）创建元组，小括号可以省略

如果只有一个元素，则必须后面加逗号。


>>> a = (1,2,3)
>>> type(a)
<class 'tuple'>
>>> a = 1,2,3
>>> type(a)
<class 'tuple'>
>>> 


通过tuple（）创建元组

tuple（可迭代的对象）
tuple（）可以接收列表、字符串、其他序列类型、迭代器等生成元组。
list（）可以接受元组、字符串、其他序列类型、迭代器等生成列表。


>>> a = tuple()
>>> a
()
>>> a = tuple("abcd")
>>> a
('a', 'b', 'c', 'd')
>>> a = tuple(range(3))
>>> a
(0, 1, 2)
>>> 



zip

将多个列表对应位置的元素组合成元组，并返回元组对象


>>> a = [1,2,3]
>>> b = [4,5,6]
>>> c = [7,8,9]
>>> d = zip(a,b,c)
>>> d
<zip object at 0x000001AB3B2763C0>
>>> list(d)
[(1, 4, 7), (2, 5, 8), (3, 6, 9)]
>>> 



生成器推导式创建元组

从形式上看，生成器推导式和列表推导式类似，只是生成器推导式使用小括号。
生成器推导式生成的不是元组，是一个生成器对象。


>>> a = (x*2 for x in range(4))
>>> a
<generator object <genexpr> at 0x000001AB3B277F90>
>>> tuple(a)
(0, 2, 4, 6)
>>> tuple(a)
()
>>> 



只能访问一次生成器对象，第二次就为空了。


>>> a = (x*2 for x in range(4))
>>> a.__next__()
0
>>> a.__next__ ()
2
>>> a.__next__ ()
4
>>> 



元组的元素访问和计数

元组的元素不能修改


>>> a = (1,2,3,4,5)
>>> a[0]
1
>>> a [0] = 6
Traceback (most recent call last):
  File "<pyshell#76>", line 1, in <module>
    a [0] = 6
TypeError: 'tuple' object does not support item assignment
>>> 



元组的元素访问和列表一样，只不过返回的仍是元组对象
列表关于排序的方法list.sorted()时修改原列表对象，元组没有该方法。
如果要对元组排序，只能使用内置函数sorted（tupleObj），并生成新的对象。


>>> a = (1,2,3,4)
>>> sorted(a)
[1, 2, 3, 4]
>>> 



元组总结

元组的核心特点：不可变序列。
元组的访问和处理速度比列表快。
与整数和字符串一样，元组元素可以作为字典的键，列表永远不能作为字典的键使用。

Python打卡（七）
元组讲解
（1）概述
列表属于可变序列，可以任意修改列表中的元素。元组tuple属于不可变序列，不能修改元组中的元素。因此，元组没有增加元素、删除元素、修改元素相关方法。

元组支持以下几种操作：

索引访问、切片操作、连接操作、成员关系操作、比较运算操作、计数（元组长度len、最大值max、最小值min、求和sum等）。
（2）元组的创建
1、通过()创建元组，小括号可以省略。
a = (10,20,30)  或者 a = 10,20,30

如果元组中只有一个元素，则必须后面加括号。这是因为解释器会把(1)解释为整数1，而将（1，）解释为元组。

例如：
>>>a = (1)
>>>type(a)
<class = 'int'>
>>>a = (1,)           #或者a = 1,
>>>type(a)
<class = 'tuple'>

2、通过tuple()创建元组
tuple(可迭代的对象)

例如：
>>>b = tuple()        #创建一个空元组对象
>>>b
()
>>>b = tuple("abc")
>>>b
('a','b','c')
>>>b = tuple(range(3))
>>>b
(0,1,2)
>>>b = tuple([2,3,4])
>>>b
(2,3,4)

总结：

tuple()可以接收列表、字符串、其他序列类型、迭代器等生成元组。

list()可以接收元组、字符串、其他序列类型、迭代器等生成列表。
（3）元组对象的删除
del b则元组对象b就被删除了
（4）元组的访问计数等
1、元组元素不能修改，即a为元组且a = (20,10,30,9,8)，则a[3] = 33是无法编译通过的。

2、元组的元素访问和列表一样，只不过返回的仍然是元组对象。
#元组的访问方式
>>>a = (20,10,30,9,8)
>>>a[1]
10
>>>a[1:3]
(10.30)
>>>a[:4]
(20,10,30,9)

3、元组中关于排序的方法只能使用内置函数sorted(tupleObj),并生成新的列表对象。注意是生成新的列表对象。
>>>b = (30,20,40)
>>>sorted(b)
[20,30,40]

4、元组的拼接，采用“+”号，生成一个新的元组对象。
>>>a = 10,20
>>>b = 30,40
>>>a+b
(10,20,30,40)
>>>a
(10,20)

5、len()操作、sum()操作、max()操作、min()操作
>>>a = 10,20
>>>len(a)
2
>>>sum(a)
30
>>>max(a)
20
>>>min(a)
10

6、zip可以将多个列表对应位置的元素组合成为元组，并返回这个zip对象。
>>>a = [10,20,30]
>>>b = [40,50,60]
>>>c = [70,80,90]
>>>d = zip(a,b,c)
>>>d
<zip object at 0x0015CCDB>
>>>list(d)
[(10,40,70),(20,50,80),(30,60,90)]

（5）生成器推导式创建元组

从形式上看，生成器推导式与列表推导式类似，只是生成器推导式使用小括号。列表推导式直接生成列表对象，生成器推导式生成的不是列表也不是元组，而是一个生成器对象。我们可以通过生成器对象，转化成列表或者元组。也可以使用生成器对象的__next__()方法进行遍历，或者直接作为迭代器对象来使用。不管什么方式使用，元素访问结束后，如果需要重新访问其中的元素，必须重新创建该生成器对象。

生成器的使用测试：
>>>s = (x*2 for x in range(5))
>>>s
<generator object <genexpr> at 0x0000000002BDEB48>
>>>tuple(s)
(0,2,4,6,8)
>>>list(s)          #只能访问一次元素，第二次就为空了。需要在生成一次
[]
>>>s
<generator object <genexpr> at 0x0000000002BDEB48>
>>>tuple(s)
()
>>>s = (x*2 for x in range(5))
>>>s.__next__()
0
>>>s.__next__()
2
>>>s.__next__()
4

总结：

1）元组的核心特点是：不可变序列

2）元组的访问和处理速度比列表快

3）与整数和字符串一样，元组可以作为字典的键，列表则永远不能作为字典的键使用（因为整数、字符串和元组都是不可变的）

列表属于可变序列，可任意修改列表中的元素，而元组属于不可变序列，不能改变元组中的元素，因此没有增删改元素的相关的方法

只需学习元组的创建和删除，元组中元素的访问和计数即可
元组支持：

索引访问：用[]和列表一样

切片操作（slice）

连接操作（+）

成员关系操作（in）

比较运算操作

计数：元组长度len()，max()，min()，sum()等
一.元组的创建

通过()创建元组，小括号可省略

如:a=(10,20,30)或者a=10,20,30

注：如果元组只有一个元素，则后面必须加逗号，因为解释器会把（1）解释为整数，而把（1,）解释为元组
通过tuple(可迭代的对象)创建元组

a=tuple()创建空元组

a=tuple(range(3))转成元组

a=tuple(‘abc’)转成元组

a=tuple([2,3,4])转成元组

二.元组的访问

三.元组排序

四.zip
zip(列表 1，列表 2，…)将多个列表对应位置的元素组合成为元组，并返回这个 zip 对象。



a = [10,20,30]

b = [40,50,60]

c = [70,80,90]

d = zip(a,b,c)

list(d)

[(10, 40, 70), (20, 50, 80), (30, 60, 90)]