数据结构：第3章 栈和队列

第3章栈和队列本章的基本内容是：两种特殊的线性表——栈和队列从数据结构角度看，栈和队列是操作受限的线性表，他们的逻辑结构相同。从抽象数据类型角度看，栈和队列是两种重要的抽象数据类型。

3.1栈栈的逻辑结构（a1,a2,……,an）栈：限定仅在表的一端进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底。空栈：不含任何数据元素的栈。

栈顶栈底a1a2a3入栈出栈栈底栈顶插入：入栈、进栈、压栈删除：出栈、弹栈栈顶栈顶

3.1栈栈的逻辑结构栈的操作特性：后进先出a1a2a3入栈出栈栈底栈顶插入：入栈、进栈、压栈删除：出栈、弹栈栈顶

3.1栈栈的逻辑结构例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈底栈顶ab栈顶c栈顶情况1：栈的逻辑结构

3.1栈栈底栈顶ab栈顶c栈顶出栈序列：c出栈序列：c、b出栈序列：c、b、a例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构情况1：

3.1栈栈底栈顶ab栈顶出栈序列：b情况2：例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构

3.1栈栈底a出栈序列：b出栈序列：b、c出栈序列：b、c、ac栈顶栈顶注意：栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构情况2：

3.1栈栈的抽象数据类型定义ADTStackData

栈中元素具有相同类型及后进先出特性，相邻元素具有前驱和后继关系Operation

InitStack

前置条件：栈不存在输入：无功能：栈的初始化输出：无后置条件：构造一个空栈

3.1栈DestroyStack

前置条件：栈已存在输入：无功能：销毁栈输出：无后置条件：释放栈所占用的存储空间Push

前置条件：栈已存在输入：元素值x

功能：在栈顶插入一个元素x

输出：如果插入不成功，抛出异常后置条件：如果插入成功，栈顶增加了一个元素栈的抽象数据类型定义

3.1栈Pop

前置条件：栈已存在输入：无功能：删除栈顶元素输出：如果删除成功，返回被删元素值，否则，抛出异常后置条件：如果删除成功，栈减少了一个元素GetTop

前置条件：栈已存在输入：无功能：读取当前的栈顶元素输出：若栈不空，返回当前的栈顶元素值后置条件：栈不变栈的抽象数据类型定义

3.1栈Empty

前置条件：栈已存在输入：无功能：判断栈是否为空输出：如果栈为空，返回1，否则，返回0

后置条件：栈不变endADT栈的抽象数据类型定义

3.1栈栈的顺序存储结构及实现顺序栈——栈的顺序存储结构如何改造数组实现栈的顺序存储？

012345678a1确定用数组的哪一端表示栈底。附设指针top指示栈顶元素在数组中的位置。

top

3.1栈出栈：top减1进栈：top加1栈空：top=-1

012345678a1topa2topa3top栈满：top=MAX_SIZE-1栈的顺序存储结构及实现

3.1栈顺序栈类的声明constintMAX_SIZE=100;template<classDataType>class

seqStack{public:seqStack();~seqStack();voidPush(DataTypex);DataTypePop();DataTypeGetTop();boolEmpty();private:DataTypedata[MAX_SIZE];inttop;}

3.1栈顺序栈的实现——入栈template<classDataType>voidseqStack<DataType>::Push(DataTypex){if(top==MAX_SIZE-1)throw“溢出”;

top++;data[top]=x;}操作接口：

voidPush(DataTypex);时间复杂度？data[++top]=x

3.1栈顺序栈的实现——出栈template<classDataType>DataTypeseqStack<DataType>::Pop(){if(top==-1)throw“溢出”;

x=data[top--];

returnx;}操作接口：

DataTypePop();时间复杂度？

3.1栈两栈共享空间解决方案1：直接解决：为每个栈开辟一个数组空间。解决方案2：

顺序栈单向延伸——使用一个数组来存储两个栈在一个程序中需要同时使用具有相同数据类型的两个栈，如何顺序存储这两个栈？会出现什么问题？如何解决？

3.1栈两栈共享空间：使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，两个栈从各自的端点向中间延伸。两栈共享空间

3.1栈栈1的底固定在下标为0的一端；栈2的底固定在下标为StackSize-1的一端。

top1和top2分别为栈1和栈2的栈顶指针；Stack_Size为整个数组空间的大小（图中用S表示）；a1

a2…aitop1012…

…S-1两栈共享空间top2bj

……b2

b1栈1底栈2底

3.1栈top1=-1什么时候栈1为空？a1

a2…aitop1012…

…S-1两栈共享空间top2bj

……b2

b1top1

3.1栈top1=-1什么时候栈1为空？a1

a2…aitop1012…

…S-1两栈共享空间top2bj

……b2

b1什么时候栈2为空？top2top2=Stack_Size

3.1栈top1=-1什么时候栈1为空？a1

a2……aitop1012…

…S-1两栈共享空间top2bj

……b2

b1什么时候栈2为空？top2=Stack_Size什么时候栈满？top2=top1+1

3.1栈constintStack_Size=100;template<classDataType>class

BothStack

{

public:BothStack();~BothStack();voidPush(inti,DataTypex);DataTypePop(inti);

DataTypeGetTop(inti);

boolEmpty(inti);

private:DataTypedata[Stack_Size];

inttop1,top2;};两栈共享空间类的声明

3.1栈1.如果栈满，则抛出上溢异常；2.判断是插在栈1还是栈2；2.1若在栈1插入，则2.1.1top1加1;

2.1.2在top1处填入x；2.2若在栈2插入，则2.2.1top2减1;

2.2.2在top2处填入x；两栈共享空间的实现——插入操作接口：voidPush(inti,DataTypex);

3.1栈1.若是在栈1删除，则

1.1若栈1为空栈，抛出下溢异常；

1.2删除并返回栈1的栈顶元素；2.若是在栈2删除，则

2.1若栈2为空栈，抛出下溢异常；

2.2删除并返回栈2的栈顶元素；两栈共享空间的实现——删除操作接口：DataTypePop(inti);

3.1栈栈的链接存储结构及实现链栈：栈的链接存储结构firsta1a2an∧ai链栈需要加头结点吗？如何改造链表实现栈的链接存储？将哪一端作为栈顶？将链头作为栈顶，方便操作。链栈不需要附设头结点。

3.1栈栈的链接存储结构及实现栈顶栈底链栈：栈的链接存储结构topanan-1a1∧firsta1a2an∧ai两种示意图在内存中对应同一种状态，启示？topa1an-1an∧栈顶栈底

3.1栈链栈的类声明template<classDataType>classLinkStack{

public:LinkStack();

~LinkStack();

voidPush(DataTypex);DataTypePop();DataTypeGetTop();boolEmpty();private:Node<DataType>*top;}

3.1栈template<classDataType>voidLinkStack<DataType>

::Push(DataTypex){s=newNode<DataType>;s->data=x;s->next=top;top=s;}topanan-1a1∧链栈的实现——插入xstop操作接口：voidPush(DataTypex);

为什么没有判断栈满？

3.1栈template<classDataType>DataTypeLinkStack<DataType>::Pop(){if(top==NULL)

throw"下溢";

x=top->data;p=top;top=top->next;

deletep;returnx;}链栈的实现——操作接口：DataTypePop();

topanan-1a1∧topp

top++可以吗？

3.1栈顺序栈和链栈的比较时间性能：相同，都是常数时间O(1)。空间性能：顺序栈：有元素个数的限制和空间浪费的问题。链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。

总之，当栈的使用过程中元素个数变化较大时，用链栈是适宜的，反之，应该采用顺序栈。

3.1栈3.2队列队列的逻辑结构队列：只允许在一端进行插入操作，而另一端进行删除操作的线性表。允许插入（也称入队、进队）的一端称为队尾，允许删除（也称出队）的一端称为队头。空队列：不含任何数据元素的队列。（a1,a2,……,an）队尾队头队列的操作特性：先进先出a1a2a3入队队尾队头出队队头队列的逻辑结构3.2队列队列的抽象数据类型定义ADTQueueData

队列中元素具有相同类型及先进先出特性，相邻元素具有前驱和后继关系Operation

InitQueue

前置条件：队列不存在输入：无功能：初始化队列输出：无后置条件：创建一个空队列3.2队列

DestroyQueue

前置条件：队列已存在输入：无功能：销毁队列输出：无后置条件：释放队列所占用的存储空间

EnQueue

前置条件：队列已存在输入：元素值x

功能：在队尾插入一个元素输出：如果插入不成功，抛出异常后置条件：如果插入成功，队尾增加了一个元素队列的抽象数据类型定义3.2队列

DeQueue

前置条件：队列已存在输入：无功能：删除队头元素输出：如果删除成功，返回被删元素值后置条件：如果删除成功，队头减少了一个元素

GetQueue

前置条件：队列已存在输入：无功能：读取队头元素输出：若队列不空，返回队头元素后置条件：队列不变队列的抽象数据类型定义3.2队列Empty

前置条件：队列已存在输入：无功能：判断队列是否为空输出：如果队列为空，返回1，否则，返回0

后置条件：队列不变endADT队列的抽象数据类型定义3.2队列01234入队出队队列的顺序存储结构及实现顺序队列——队列的顺序存储结构如何改造数组实现队列的顺序存储？例：a1a2a3a4依次入队a1a2a3a4rearrearrearrear入队操作时间性能为O(1)3.2队列如何改造数组实现队列的顺序存储？例：a1a2依次出队队列的顺序存储结构及实现01234入队出队a1a2a3a4rear3.2队列如何改造数组实现队列的顺序存储？例：a1a2依次出队队列的顺序存储结构及实现01234入队出队a2a3a4rear3.2队列如何改造数组实现队列的顺序存储？例：a1a2依次出队队列的顺序存储结构及实现01234入队出队a3a4rear出队操作时间性能为O(n)3.2队列队列的顺序存储结构及实现如何改进出队的时间性能？放宽队列的所有元素必须存储在数组的前n个单元这一条件，只要求队列的元素存储在数组中连续的位置。设置队头、队尾两个指针

3.2队列队列的顺序存储结构及实现01234入队出队例：a1a2a3a4依次入队a1a2a3a4rearrearrearrear入队操作时间性能仍为O(1)frontrear3.2队列约定：队头指针front指向队头元素的前一个位置，队尾指针rear指向队尾元素。例：a1a2依次出队队列的顺序存储结构及实现01234入队出队a1a2a3a4rearfrontfrontfront出队操作时间性能提高为O(1)3.2队列例：a1a2依次出队队列的顺序存储结构及实现01234入队出队a3a4rearfront队列的移动有什么特点？3.2队列例：a1a2依次出队队列的顺序存储结构及实现01234入队出队a3a4rearfront整个队列向数组下标较大方向移动单向移动性3.2队列假溢出：当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做假溢出。队列的顺序存储结构及实现继续入队会出现什么情况？01234入队出队a3a4rearfronta5rear3.2队列循环队列：将存储队列的数组头尾相接。队列的顺序存储结构及实现如何解决假溢出？01234入队出队a3a4fronta5rearreara63.2队列不存在物理的循环结构，用软件方法实现。求模：（4＋1）mod5＝0队列的顺序存储结构及实现如何实现循环队列？01234入队出队a3a4frontreara63.2队列如何判断循环队列队空？队空的临界状态队列的顺序存储结构及实现01234入队出队a3rearfront3.2队列如何判断循环队列队空？执行出队操作队空：front==rear队列的顺序存储结构及实现01234入队出队a3frontrearfront3.2队列如何判断循环队列队满？队满的临界状态队列的顺序存储结构及实现01234入队出队a3a4fronta5reara63.2队列如何判断循环队列队满？执行入队操作队满：front==rear队列的顺序存储结构及实现01234入队出队a3a4fronta5reara6reara73.2队列方法一：修改队满条件，浪费一个元素空间，队满时数组中只有一个空闲单元；方法二：附设一个存储队列中元素个数的变量num，当num=0时队空，当num=QueueSize时为队满；方法三：设置标志flag，当front=rear且flag=0时为队空，当front=rear且flag=1时为队满。如何确定不同的队空、队满的判定条件？为什么要将队空和队满的判定条件分开？队列的顺序存储结构及实现3.2队列队满的条件：(rear+1)modQueueSize=front队列的顺序存储结构及实现(队满用方法一判断)01234入队rear<fronta3a4fronta5reara6出队01234入队rear>fronta3a4fronta5reara6出队3.2队列循环队列类的声明constintQueueSize=100;template<classDataType>classCirQueue{public:CirQueue()；~CirQueue()；

voidEnQueue(DataTypex);DataTypeDeQueue();

DataTypeGetQueue();

boolEmpty()；private:DataTypedata[QueueSize];

intfront,rear;};3.2队列template<classDataType>voidCirQueue<DataType>::EnQueue(DataTypex){if((rear+1)%QueueSize==front)throw"上溢";

rear=(rear+1)%QueueSize;

data[rear]=x;}循环队列的实现——入队01234入队出队a3a4rearfronta5rear3.2队列01234入队a4a5a6出队template<classDataType>DataTypeCirQueue<DataType>

::DeQueue(){if(rear==front)throw"下溢";

front=(front+1)%QueueSize;returndata[front];}循环队列的实现——出队frontrearfronta33.2队列template<classDataType>DataTypeCirQueue<DataType>

::GetQueue(){if(rear==front)throw"下溢";

i=(front+1)%QueueSize;

returndata[i];}循环队列的实现——读队头元素01234入队a4a5a6出队frontreara3i3.2队列队列的链接存储结构及实现链队列：队列的链接存储结构队头指针即为链表的头指针firsta1a2an∧如何改造单链表实现队列的链接存储？rearfront3.2队列队列的链接存储结构及实现非空链队列fronta1a2an∧rear空链队列front∧rear3.2队列链队列类的声明template<classDataType>classLinkQueue{public:LinkQueue();~LinkQueue();voidEnQueue(DataTypex);DataTypeDeQueue();

DataTypeGetQueue()；boolEmpty()；private:Node<DataType>*front,*rear;};3.2队列操作接口：

LinkQueue();

算法描述：template<classDataType>LinkQueue<DataType>

::LinkQueue(){front=newNode<DataType>;front->next=NULL;rear=front;}链队列的实现——构造函数front∧rear3.2队列xs链队列的实现——入队操作接口：

voidEnQueue(DataTypex);fronta1an∧rear∧rearfrontxs∧∧rearrear算法描述：s->next=NULL;rear->next=s;rear=s;如何没有头结点会怎样？3.2队列xs链队列的实现——入队操作接口：

voidEnQueue(DataTypex);fronta2an∧rear∧rear算法描述：s->next=NULL;rear->next=s;rear=s;如何没有头结点会怎样？a13.2队列链队列的实现——入队操作接口：

voidEnQueue(DataTypex);front=rear=NULLxs∧rear算法描述：s->next=NULL;rear=s;front=s;如何没有头结点会怎样？front算法描述：s->next=NULL;rear->next=s;rear=s;3.2队列链队列的实现——入队template<classDataType>voidLinkQueue<DataType>

::EnQueue(DataTypex){s=newNode<DataType>;s->data=x;s->next=NULL;rear->next=s;rear=s;}3.2队列链队列的实现——出队fronta1a2an∧rearp算法描述：p=front->next;front->next=p->next;3.2队列链队列的实现——出队fronta1a2an∧rearp考虑边界情况：队列中只有一个元素？fronta1p∧rear∧rear算法描述：if(p->next==NULL)rear=front;如何判断边界情况？3.2队列template<classDataType>DataTypeLinkQueue<DataType>

::DeQueue(){if(rear==front)throw"下溢";p=front->next;x=p->data;front->next=p->next;if(p->next==NULL)rear=front;deletep;returnx;}链队列的实现——出队3.2队列循环队列和链队列的比较时间性能:循环队列和链队列的基本操作都需要常数时间O(1)。空间性能:循环队列：必须预先确定一个固定的长度，所以有存储元素个数的限制和空间浪费的问题。链队列：没有队列满的问题，只有当内存没有可用空间时才会出现队列满，但是每个元素都需要一个指针域，从而产生了结构性开销。3.2队列3.3应用举例3.3.1栈应用的典型例子

——表达式求值的实现

递归

迷宫求解3.3.2队列的应用

——打印杨辉三角形733.3.1表达式求值算法表达式都是由操作数（operand）、运算符（operator）和界限符（delimiter）组成的。讨论简单算术表达式的求值问题——只含加、减、乘、除四则运算，所有的运算对象均为数，并以“#”为结束符。常用算法——“算符优先法”算符优先法就是根据运算符和界限符的优先次序的规定来实现表达式求值的。算术四则运算规则——运算符的优先次序规定：

1)先乘除，后加减；

2)从左算到右；

3)先括号内，后括号外。算术表达式的三种表示算术表达式有三种表示：中缀(infix)表示

<操作数><操作符><操作数>，如A+B；前缀(prefix)表示——波兰式表示

<操作符><操作数><操作数>，如+AB；后缀(postfix)表示——逆波兰式表示

<操作数><操作数><操作符>，如AB+；中缀表达式和后缀表达式中缀表达式：运算符在两个运算数中间的表达式。如：

1)X-Y2)

5+(6-4/2)*3

（字母表示运算数）

后缀表达式：运算符紧跟在两个运算数后面的表达式。如：

1)XY-2)5642/-3*+中缀到后缀中缀

5+(6-4/2)*3

到后缀5642/-3*+的转变

5

(6-4/2)*3

+→5(6-4/2)

3*+

→56

4/2

-3*+→564

2

/-3*+后缀表达式的作用去掉中缀表达式的括号隐含中缀表达式的运算次序运算符左边向右的计算，运算数则是按其右边最接近运算符的先算的次序，运算结果放回原处：计算过程5642/-3*+562–3*+

543*+512+

17

←最后结果应用后缀表示计算表达式的值从左向右顺序地扫描表达式，并用一个栈暂存扫描到的操作数或计算结果。在后缀表达式的计算顺序中已隐含了加括号的优先次序，括号在后缀表达式中不出现。计算例利用栈的计算后缀表达式的过程栈

5642/-3*+

5/265-45345*125+

voidClear();//清空计算器

private:voidAddOperand(doublevalue);

//操作数入栈

BooleanGet2Operands(double&left,double&right);//从栈中退出两个操作数

voidDoOperator(charop);//根据运算符计算，结果入栈

Stack<double>s;//存放运算数的工作栈};后缀表达式计算器的实现voidCalculator::AddOperand(doublevalue){s.Push(value);//操作数入栈

}BooleanCalculator::Get2Operands(double&left,double&right){

//从栈中退出两个操作数

if(s.Empty()){cerr<<"MissingOperand!"<<endl;returnFalse;}right=s.Pop();if(s.Empty()){cerr<<"MissingOperand!"<<endl;returnFalse;}left=s.Pop();returnTrue;}

voidCalculator::DoOperator(charop){

//根据运算符计算，结果入栈

doubleleft,right;Booleanresult;result=Get2Operands(left,right);if(result==True)switch(op){ case'+':s.Push(left+right);break; case'-':s.Push(left-right);break; case'*':s.Push(left*right);break; case'/':if(right==0.0){ cerr<<"Dividedby0!"<<endl; s.MakeEmpty(); exit(0);}elses.Push(left/right);break; case'^':s.Push(pow(left,right));break; } elses.MakeEmpty();};voidCalculator::Run(){charch;doublenewoperand;while(cin>>ch,ch!='='){switch(ch){ case'+':case'-':case'*':case'/‘:case'^':DoOperator(ch);break; default:cin.putback(ch);cin>>newoperand; AddOperand(newoperand);break;}}

assert(!s.Empty());//若栈底无数，错误！终止

cout<<"Theresultis:"<<s.Pop()<<endl;

//输出结果（栈底元素）

}voidCalculator::Clear(){s.MakeEmpty();}voidmain(){Calculatorcal(10);cal.Run();}中缀表达式转换为后缀表达式建立运算符栈,并向栈底压入#(若表达式以#结束)从左向右依次读入表达式如果是运算数,则输出如果是操作符则按下面操作如果栈外运算符优先级高于栈顶元素优先级,栈外运算符入栈如果栈外运算符优先级低于栈顶元素优先级,则栈顶运算符出栈输出,直至栈顶运算符优先级低于栈外运算符,栈外运算符如栈.当栈外为),栈内运算符退至(为止当栈外为#,栈内运算符退至#为止算符优先关系算符——运算符和界限符的统称，它们构成的集合命名为OP。根据前述算术四则运算三条规则，在运算的每一步中，任意两个相继出现的算符op1和op2之间的优先关系至多是下面三种关系之一:op1<op2op1的优先权低于op2op1=op2op1的优先权等于op2op1>op2op1的优先权高于op2+－*/()#+>><<<>>－>><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=θ1θ2算符间的优先级关系算符θ1在算符θ2前面。在算法中，相对应于θ1在栈内，θ2在栈外*+##*+#+##)/-(+#/-(+#(+#+#利用栈的转换过程5+(6–4/2)*3#5642/-3*+

输出栈外

-(+#中缀表达式求值算法将前面中缀表达式转后缀表达式，及后缀表达式计算两过程结合起来，利用所给的+、-、*、/、（、）、和#的算术运算符间的优先级的关系，可计算中缀表达式。设置两个栈：（1）操作数栈（OPRD）存放处理表达式过程中的操作数。（2）运算符栈（OPTR）存放处理表达式过程中的运算符。首先在运算符栈中先在栈底压入一个表达式的结束符“#”。运算符栈（OPTR）操作数栈（OPRD）toptop#表达式求值算法计算表达式:5+(6-4/2)*3#的过程。↑首先在运算符栈中先在栈底压入一个表达式的结束符“#”。算符栈（OPTR）运算数栈（OPRD）toptop#

top表达式求值算法计算表达式:5+(6-4/2)*3#的过程。↑读取表达式第一个字符，是数，压入运算数栈算符栈（OPTR）运算数栈（OPRD）top#5top表达式求值算法计算表达式:5+(6-4/2)*3#的过程。↑读取表达式第2个字符“+”，优先级：“+”>“#”，压入算符栈算符栈（OPTR）运算数栈（OPRD）top#5+top表达式求值算法计算表达式:5+(6–4/2)*3#的过程。↑读取表达式第3个字符“(”优先级：在栈外“(”>“+”，压入算符栈算符栈（OPTR）运算数栈（OPRD）toptop#5+(表达式求值算法计算表达式:5+(6–4/2)*3#的过程。↑读取表达式第4个字符“6”压入运算数栈算符栈（OPTR）运算数栈（OPRD）toptop#5+6(表达式求值算法计算表达式:5+(6–4/2)*3#的过程。↑读取表达式第5个字符“–”优先级：在栈外“–”>栈内“(”，压入算符栈算符栈（OPTR）运算数栈（OPRD）toptop#5+6—(表达式求值算法计算表达式:5+(6–4/2)*3#的过程。↑读取表达式第6个字符“4”压入运算数栈算符栈（OPTR）运算数栈（OPRD）toptop#5+46—(表达式求值算法计算表达式:5+(6–

4

/2)*3#的过程。↑读取表达式第7个字符“/”优先级：在栈外“/”>栈内“–”，压入算符栈算符栈（OPTR）运算数栈（OPRD）toptop#5+46/—(表达式求值算法计算表达式:5+(6–

4

/2)*3#的过程。↑读取表达式第8个字符“2”压入运算数栈算符栈（OPTR）运算数栈（OPRD）toptop#5+426/—(表达式求值算法计算表达式:5+(6–

4

/

2)*3#的过程。

↑读取表达式第9个字符“)”优先级：在栈外“)”<栈内任何算法，算符出栈计算,直至“(”算符栈（OPTR）运算数栈（OPRD）toptop#5+426/—(表达式求值算法计算表达式:5+(6–

4

/

2)*3#的过程。

↑读取表达式第9个字符“)”优先级：在栈外“)”<栈内任何算法，算符出栈计算,直至“(”算符栈（OPTR）运算数栈（OPRD）toptop#5+426/—(表达式求值算法计算表达式:5+(6–

4

/

2)*3#的过程。↑读取表达式第9个字符“)”优先级：在栈外“)”<栈内任何算法，算符出栈计算,直至“(”算符栈（OPTR）运算数栈（OPRD）toptop#5+426/—(22=表达式求值算法计算表达式:5+(6–

4

/

2)*3#的过程。↑读取表达式第9个字符“)”优先级：在栈外“)”<栈内任何算法，算符出栈计算,直至“(”算符栈（OPTR）运算数栈（OPRD）toptop#5+62—(表达式求值算法计算表达式:5+(6–

4

/

2)*3#的过程。↑读取表达式第9个字符“)”优先级：在栈外“)”<栈内任何算法，算符出栈计算,直至“(”算符栈（OPTR）运算数栈（OPRD）toptop#5+62－(44=表达式求值算法计算表达式:5+(6–

4

/

2)*3#的过程。↑读取表达式第9个字符“)”优先级：在栈外“)”<栈内任何算法，算符出栈计算,直至“(”算符栈（OPTR）运算数栈（OPRD）toptop#5+4(表达式求值算法计算表达式:5+(6–

4

/

2

)*3#的过程。↑读取表达式第10个字符“*”优先级：在栈外“*”>栈内“+”，算符“*”入栈算符栈（OPTR）运算数栈（OPRD）toptop#5+4*表达式求值算法计算表达式:5+(6–

4

/

2

)

*3#的过程。↑读取表达式第11个字符“3”运算数“3”入数栈算符栈（OPTR）运算数栈（OPRD）toptop#5+4*3表达式求值算法计算表达式:5+(6–

4

/

2

)*3#的过程。↑读取表达式第12个字符“#”优先级：在栈外“#”<栈内“*”，“*”出栈计算算符栈（OPTR）运算数栈（OPRD）toptop#5+4*3表达式求值算法计算表达式:5+(6–

4

/

2

)*3#的过程。