数据结构06——栈及栈的应用——后缀表达式

1. 栈的定义

1.1 文字定义

:限定仅在表尾进行插入和删除操作的线性表。

允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。栈又被称为后进先出(Last In First Out)的线性表,简称LIFO结构

理解栈的定义需要注意:

  • 栈是一个线性表,也就是说栈元素具有线性关系,即前驱后继关系。定义中说是在线性表的表尾进行插入和删除操作,这里的尾是指栈顶,而不是栈底。
  • 栈的特殊之处就在于限制了这个线性表的插入和删除位置,它始终只在栈顶进行。这使得栈底是固定的,最先进栈的只能在栈顶。

栈的插入操作,叫做进栈,也称压栈、入栈。

栈的删除操作,叫做出栈,有的也叫作弹栈。

数据结构06——栈及栈的应用——后缀表达式

1.2 代码定义

插入和删除操作改名为push和pop

伪代码定义:

ADT 栈(stack)
DATA
同线性表。元素具有相同的类型,相邻元素具有前驱和后继关系。
Operation
InitStack(*S):初始化操作,建立一个空栈S
DestoryStack(*S):若栈存在,则销毁它。
ClearStack(*S):将栈清空
StackEmpty(S):若栈为空,返回true,否则返回false
GetTop(S,*e):若栈存在且非空,用e返回S的栈顶元素
Push(*S,e):若栈S存在,插入新元素e到栈S中并成为栈顶元素
Pop(*S,*e):删除栈S中栈顶元素,并用e返回其值
StackLength(S):返回栈S的元素个数
endADT

2 栈的顺序存储结构

栈的结构定义:

typedef int SElemType;  // SElemType类型根据实际情况而定,这里假设为int

// 顺序栈结构
typedef struct{
SElemType data[MAXSIZE];
int top; // 用于栈顶指针
}SqStack;

2.1 进栈操作(插入操作)

对于栈的插入,即进栈操作,其实就是做了如下处理:

数据结构06——栈及栈的应用——后缀表达式

代码如下:

Status Push(SqStack *S.SElemType e){
if(S -> top == MAXSIZE -1){ // 栈满
return ERROR;
}
S->top++; // 栈顶指针加一
S->data[S->top] = e; // 将新插入元素复制给栈顶空间
return OK;
}

2.2 出栈操作(删除操作)

出栈操作pop,代码如下:

Status Pop(SqStack *S,SElemType *e){
if(S->top==-1){ // 栈为空
return ERROR;
}
*e = S->data[S->top]; // 将要删除的栈顶元素复制给e
S->top--; // 栈顶指针减一
return OK;
}

3 共享栈

栈的顺序存储还是很方便的,因为它只准栈顶进出元素,所以不存在线性表插入和删除时需要移动元素的问题。不过它有一个很大的缺陷,就是必须事先确定数组存储空间大小,万—不够用了,就需要用编程手段来扩展数组的容量,非常麻烦。

共享栈就可以很好的解决这个问题。如果我们有两个相同类型的栈,我们为它们各自开辟了数组空间,极有可能是第—个栈已经满了,再进栈就溢出了,而另一个栈还有很多存储空间空闲,我们完全可以用—个数组来存储两个栈,充分利用这个数组占用的内存空间。

设置数组有两个端点,两个栈有两个栈底,让一个栈的栈底为数组的始端,即下标为0处,另—个栈为数组的末端,即下标为数组长度n-1处。这样两个栈如果增加元素,就是两端点向中间延伸。

数据结构06——栈及栈的应用——后缀表达式

当​​top1+1=top2​​​时为栈满,​​top1​​​ 和​​top2​​是栈1和栈2的栈顶指针。

共享栈的结构代码如下:

typedef struct{
SElemType data[MAXSIZE];
int top1; // 栈1栈顶指针
int top2; // 栈2栈顶指针
}SqDoubleStack;

3.1 共享栈进栈

对于共享栈的push方法,除了要插入元素值参数外,还需要有一个参数判断是栈1还是栈2的栈号参数StackNumber。

Status Push(SqDoubleStack *S,SElemType e,int stackNumber){
if(S->top1+1=S->top2){ // 栈满
return ERROR;
}
if(stackNumber==1){ // 栈1元素进栈
S->data[++S->top1]=e; // 若是栈1则先top1+1后给数组元素赋值
}else if(stackNumber==2){ // 栈2元素进栈
S->data[--S->top2]=e; // 若是栈2则先top2-1后给数组元素赋值
}
}

3.2 共享栈出栈

对于共享栈的pop方法,参数就只是判断栈1栈2的参数stackNumber,代码如下:

Status Pop(SqDoubleStack *S,SElemType *e.int stackNumber){
if(stackNumber==1){
if(S->top1==-1){ // 栈1是空栈
return ERROR;
}
*e = S->data[S->top--]; // 将栈1的栈顶元素出栈
}else if(stackNumber==2){
if(S->top2==MAXSIZE){ // 栈2是空栈
return ERROR;
}
*e = S->data[S->top2++] // 将栈2的栈顶元素出栈
}
}

4 栈的链式存储(链栈)

链栈栈顶放在单链表的头部,基本不存在栈满的情况,不用担心链栈溢出的问题,对于空栈来说,链表原定义是头指针指向空,链栈的空其实就是​​top=NULL​​的时候。

数据结构06——栈及栈的应用——后缀表达式

链栈的结构代码如下:

typedef struct StackNode{
SELemType data;
struct StackNode *next;
}StackNode,*LinkStackPtr;

typedef struct{
LinkStackPtr top;
int count;
}LinkStack;

4.1 进栈操作

对于链栈的进栈push操作,假设元素值为e的新结点是s,top为栈顶指针,示意图如图所示:

数据结构06——栈及栈的应用——后缀表达式

Status Push(LinkStack *S,SElemType e){
LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode)); // 初始化一个结点
s->data = e; // 给新结点赋值
s->next = S->top; // 新结点下一元素链上指针,步骤1
S->top = s; // 将新结点s赋值给栈顶指针,步骤2
s->count++; // 链栈结点个数长度
return OK;
}

4.2 出栈操作

对于链栈的出栈pop操作,假设变量p用来存储要删除的栈顶结点,将栈顶指针下移一位,最后释放p即可。

数据结构06——栈及栈的应用——后缀表达式

Status Pop(LinkStack *S,SElemType *e){
LinkStackPtr p;
if(StackEmpty(*S)){ // 栈空
return ERROR;
}
*e = S->top->data;
p = S->top; // 将栈顶结点赋值给p,步骤3
S->top = S->top->next; // 使栈顶指针下移一位,指向后一结点,步骤4
free(p); // 释放结点p
S->count--;
return OK;
}

5 栈的应用——四则运算表达式求值

5.1 后缀(逆波兰 Reverse Polish Notation RPN)表达式定义

9+(3-1)*3+10/2的困难就在于乘除在加减后面,却要先运算,而加入括号后,会更加复杂。

但仔细观察后发现,括号都是成对出现的,有左括号就—定会有右括号,对于多重括号,最终也是完全嵌套匹配的。

这用栈结构正好合适,只要碰到左括号,就将此左括号进栈,不管表达式有多少重括号,反正遇到左括号就进栈,而后面出现右括号时,就让栈顶的左括号出栈,期间让数字运算。

这样,最终有括号的表达式从左到右巡查—遍,栈应该是由空到有元素,最终再因全部匹配成功后成为空栈

对于“9+(3+1)×3+10÷2” ,用后缀表示法应该的样子: 正常数学表达式:9+(3+1)×3+10÷2 后缀表达式:9 3 1 - 3*+10 2 / + “9 3 1 - 3*+10 2 / +”,这样的表达式称为后缀表达式,叫后缀的原因在于所有的符号都是在要运算数字的后面出现。

5.2 后缀表达式计算方法

后缀表达式:9 3 1 - 3*+10 2 / +

  1. 初始化空栈,此栈用来对要运算的数字进出使用。

数据结构06——栈及栈的应用——后缀表达式

  1. 后缀表达式前三个都是数字,所以9、3、1进栈,如图所示。

数据结构06——栈及栈的应用——后缀表达式

  1. 接下来是“-”,所以将栈中的1出栈作为减数,3出栈被减数,并运算3-1得到2,再将2进栈,如图所示。

数据结构06——栈及栈的应用——后缀表达式

  1. 接着是数字3进栈,如图所示.

数据结构06——栈及栈的应用——后缀表达式

  1. 后面是“*”,也就意味着栈中的3和2出栈,2与3相乘得到6,并将6进栈。

数据结构06——栈及栈的应用——后缀表达式

  1. 下面是‘‘+” ,所以栈中6和9出栈,9与6相加,得到15,将15进栈。

数据结构06——栈及栈的应用——后缀表达式

  1. 接着是10与2两数字进栈。

数据结构06——栈及栈的应用——后缀表达式

  1. 接下来是符号‘‘/”,因此,栈顶的2与10出栈,10与2相除,得到5,将5进栈。

数据结构06——栈及栈的应用——后缀表达式

  1. 最后—个是符号“+”,所以15与5出栈,并相加,得到20,将20进栈 。

数据结构06——栈及栈的应用——后缀表达式

  1. 结果是20出栈,栈变为空。

数据结构06——栈及栈的应用——后缀表达式

5.3 中缀表达式转后缀表达式

中缀表达式“9+(3+1)×3+10÷2”转化为后缀表达式“9 3 1 - 3*+10 2 / +”

方法:从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即成为后缀表达式的—部分;若是符号,则判断其与栈顶符号的优先级,是右括号或优先级不高于栈顶符号(乘除优先加减)则栈顶元素依次出栈并输出,并将当前符号进栈,一直到最终输出后缀表达式为止。

思路:

  1. 初始化一空栈,用来对符号进出栈使用。

数据结构06——栈及栈的应用——后缀表达式

  1. 第—个字符是数字9,输出9,后面是符号‘‘+’’ ,进栈。

数据结构06——栈及栈的应用——后缀表达式

  1. 第三个字符是”( “ ,依然是符号,因其只是左括号,还未配对,故进栈。

数据结构06——栈及栈的应用——后缀表达式

  1. 第四个字符是数字3,输出,总表达式为9 3,接着是“-”,进栈。

数据结构06——栈及栈的应用——后缀表达式

  1. 接下来是数字1,输出,总表达式为9 3 1,后面是符号“)” ,此时,我们需要去匹配此前的“( ”,所以栈顶依次出栈,并输出,直到“( ”出栈为止。此时左括号上方只有“-’’,因此输出“-”。总的输出表达式为9 3 1 -。

数据结构06——栈及栈的应用——后缀表达式

  1. 紧接着是符号”ד,因为此时的栈顶符号为“+”,优先级低于“×”, 因此不输出,“*”进栈。接着是数字3,输出,总的表达式为9 3 1 - 3。

数据结构06——栈及栈的应用——后缀表达式

  1. 之后是符号“+”,此时当前栈元素“*”,比这个“+”的优先级高,因此栈中元素出栈并输出(没有比“+”更低的优先级,所以全部出栈),总输出表达式为9 3 1 - 3 * +。

数据结构06——栈及栈的应用——后缀表达式

  1. 紧接着数字10,输出,总表达式变为9 3 1 - 3 * + 10 2。后是符号“÷“,所以“/”进栈。

数据结构06——栈及栈的应用——后缀表达式

  1. 最后一个数字2,输出,总的表达式为9 3 1 - 3 *+10 2。

数据结构06——栈及栈的应用——后缀表达式

  1. 因为巳经到最后,所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为9 3 1 - 3 *+10 2 / +。

数据结构06——栈及栈的应用——后缀表达式

5.4 后缀表达式总结

使用计算机处理通常的标准(中缀表达式),最重要的是以下两步:

  1. 将中缀表达式转化为后缀表达式(栈用来进出运算的符号)。
  2. 将后缀表达式进行运算得出结果(栈用来进出运算的数字)。
发表评论

相关文章