栈的数据结构是队列，数据结构-第三章

威哥 2023-01-13 11:49:40 189

栈的数据结构是队列，数据结构-第三章在解决表达式求值的问题我们通常要将中缀表达式转成前缀表达式或者转成后缀表达式，不过最常用的还是转成后缀表达式。常常用后缀表达式计算表达式的值。例如：A B C-E-F 像这种简单的表达式求值我们通过遍历，加上if 判断就可以解决，但是[(A B)*C]-(E-F)这种比较复杂的表达式这就有一些复杂的优先级了。这就需要栈来解决了，下面介绍几种表达式的分类。不匹配序列下面是一个正确匹配的序列，我们给每一个标上号，一次输入到栈中，判断阔号是否匹配。算法思想：

第三章：栈和队列

下面讲解栈的应用主要内容有：栈的应用、括号匹配、中后前缀表达式转换

1.栈的应用

1.1括号匹配

我们在数学运算中 [(A b)*c] - (E-F) 往往都会有[ ] 和 ( ) 来表示运算的优先级，我们把这样的[ ] 和 ( ) 提取出来组成的序列叫做括号匹配序列。

匹配序列

( [ ( ) ] )
[ ] [ ] ( )
( ) [ ( ) ]

上面是正确的可以匹配的序列，每一个( 或者[都有与之对应的)或者]。

不匹配序列

( [ ( ) ]
] [ ] ( )
( ] [ ( ) ]

下面是一个正确匹配的序列，我们给每一个标上号，一次输入到栈中，判断阔号是否匹配。

栈的数据结构是队列，数据结构-第三章(1)

算法思想：

1.初始化一个空栈，顺序读入阔号
2.若是右阔号，则与栈顶元素进行匹配

若匹配，则弹出栈顶元素进行下一个元素

若不匹配，则该序列不合法

3.若是左阔号，则压入栈中
4.如果全部元素遍历完毕，栈中非空则序列不合法

1.2表达式求值

例如：A B C-E-F 像这种简单的表达式求值我们通过遍历，加上if 判断就可以解决，但是[(A B)*C]-(E-F)这种比较复杂的表达式这就有一些复杂的优先级了。这就需要栈来解决了，下面介绍几种表达式的分类。

栈的数据结构是队列，数据结构-第三章(2)

在解决表达式求值的问题我们通常要将中缀表达式转成前缀表达式或者转成后缀表达式，不过最常用的还是转成后缀表达式。常常用后缀表达式计算表达式的值。

1.3中缀表达式转前&后缀

中缀转前缀&后缀

[(A B)*C]-(E-F)

我们按照运算的优先级首先计算(A B)将它转成前缀： AB，[ AB*C]-(E-F) 接着乘以C转成前缀为：* ABC，这样第一个方括号的转换完毕，接着按照运算优先级，将[E-F]转成前缀：-EF，现在表达式为：* ABC-(-EF)，接着将中间的-提到最前面的：-* ABC-EF

前缀表达式：- * A B C - E F

过程和上面的过程相同，只不过将运算符号号放后面就行。

后缀表达式：A B C * E F - -

使用栈将中缀转后缀的算法思想：

( ( A B ) * C ) - ( E - F )

数字直接加入后缀表达式
运算符时:
a.若为( 入栈;.b
b.若为') 则依次把栈中的运算符加入后缀表达式直到出现( 并从栈中删除（
c.若为 - * /

1.栈空入栈;

2.栈顶元素为( 入栈;

3.高于栈顶元素优先级入栈;·

4.否则依次弹出栈顶运算符直到一个优先级比它低的运算符或(为止;`

d.遍历完成若栈非空依次弹出所有元素。

使用此思想执行一遍将表达式装成后缀：

为了方便文字描述，定义一个H作为后缀表达式，定义一个Z栈。首先( (依次入栈(规则：a)，此时Z=( (，接着数字A，直接加入后缀表达式中此时H=A接着入栈(规则：c 2)，此时Z=*(( 接着B直接加入后缀表达式中：H=AB 接着)入栈符合规则b，则此时Z=( H=AB 接着*入栈，Z=(*，接着)入栈符合规则b，则此时Z=空，H=AB C*，接着-(依次入栈，此时Z=-(，接着E 直接加入后缀表达式：H=AB C*E，接着-入栈，此时Z=-(-接着F直接加入后缀表达式中，H=AB C*EF，接着)入栈符合规则b，则此时z=- H=AB C*EF-，然后符合规则d，此时z=空，H=AB C*EF- -。