《数据结构-栈及其应用.ppt》由会员分享，可在线阅读，更多相关《数据结构-栈及其应用.ppt（48页珍藏版）》请在金锄头文库上搜索。
1、数据结构-栈对于程序设计来说：v 编程语言是工具；v 数据结构是基础；v 算法设计是方法。程序=数据结构+算法数据结构数据结构u数据结构（数据结构（datastructure）是相互之间存在一种或多种特定关系的数据元素的集合。 数据结构的内涵数据结构的内涵n“操作”的对象：数据。n数据与数据间的关系。n针对数据的基本操作。数据结构的形式定义数据结构的形式定义 data _ structure=(D,S)D:数据元素的有限集；S:上关系的有限集；数据结构相关概念u数据数据(data) 计算机科学中指所有能输入到计算机中并被程序处理的符号总称。例如数值、字符、图像、声音都属于数据的范畴。u数据元素
2、数据元素(data element) 是数据的基本单位 ，在程序中作为一个整体进行考虑。有时一个数据元素有若干数据项。u数据对象数据对象(data object)是性质相同的数据元素的集合，是数据的一个子集。逻辑结构图例数据元素间的关系结构名特性数据元素属于或不属于集合集合结构松散；用其他结构代替数据元素一个对一个线性结构结构简单数据元素一个对多个树形结构结构复杂数据元素多个对多个图结构结构复杂前述“关系”即结构(sructure)，指数据之间的逻辑关系，又称逻辑结构。物理结构1顺序结构：顺序结构：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 逻辑上关联的数据元素，物理存储结构中
3、相邻。 2链式结构链式结构 ：借助元素存储地址的指针指针(pointer）表示数据元素之间的逻辑关系 。 逻辑上关联的数据元素，物理存储结构中不一定相邻。 o用高级语言中的数据类型(数组、动态变量)来描述o逻辑结构、物理结构密切相关o算法的设计取决于所选定的数据（逻辑）结构，而算法的实现依赖于所采用的存储结构。 线性结构线性表、栈、队列线性表、栈、队列、串、数组、广义表非线性结构树、图n由由n个数据元素的有限序列个数据元素的有限序列n除头元素外，每个元素都有一个前趋除头元素外，每个元素都有一个前趋n除尾元素外，每个元素都有一个后继除尾元素外，每个元素都有一个后继线性结构线性表线线性性表表是是最
4、最常常用用且且最最简简单单的的一一种种数数据据结结构构，它是由有限个数据元素组成的有序集合。它是由有限个数据元素组成的有序集合。每每个个数数据据元元素素有有一一个个数数据据项项或或者者含含多多个个数数据项。据项。线性表的两种存储方式1、顺序存储结构、顺序存储结构顺序存储结构是指用一组地址连续的存贮单元依次存储线性表的顺序存储结构是指用一组地址连续的存贮单元依次存储线性表的元素，通常用数组实现。数组的物理实现是一块连续的存储元素，通常用数组实现。数组的物理实现是一块连续的存储空间，它是按首址（表中第空间，它是按首址（表中第1个元素的地址）十位移来访问每个元素的地址）十位移来访问每一个元素。一个元
5、素。2、链式存储结构、链式存储结构在链式存储结构的线性表中，逻辑上相邻的两元素，其物理在链式存储结构的线性表中，逻辑上相邻的两元素，其物理位置不要求相邻。采用动态指针。数组元素和动态变量的类型一位置不要求相邻。采用动态指针。数组元素和动态变量的类型一般采用记录类型，数据域存储结点的值，指针域存储后件的数组般采用记录类型，数据域存储结点的值，指针域存储后件的数组下标或地址。最后一个结点的指针域的值为下标或地址。最后一个结点的指针域的值为0或或nil。数组的插入与删除123456789 10 11 126.5数组的插入与删除均需要移动后面的元素数组的插入与删除均需要移动后面的元素插入：插入：删除：
6、删除：123456789 10 11 121234567891011121234567891011 12链表的插入与删除无需移动任何元素无需移动任何元素线性表的具体实现u顺序存储结构顺序存储结构用数组类型：用数组类型：list:array1.maxlenofelemtp;u链式存储结构链式存储结构用指针类型用指针类型和和动态变量：动态变量：pointer=nodetype;nodetype=recorddata:elemtp; next:pointer;end;顺序存储与顺序存储与链式存储操作的对比链式存储操作的对比顺序存储顺序存储链式存储链式存储特点逻辑相邻的元素其物理位置也相邻逻辑相邻的元
7、素其物理位置不一定相邻特点优点随机存取i 元素 o(1)查找X 和 第i元素需遍历整个链表 o(n)缺点缺点插入、删除需移动大量元素 o( n)插入、删除不需移动大量元素 o(1)优点缺点预先分配大空间不需预先分配空间优点缺点表容量难以扩充表容量扩充灵活优点优点操作简单操作较复杂缺点 限定仅在表尾进行插入和删除操作的线性表,又称为后进先出(last in first out )线性表 (LIFO结构) 栈顶表尾 栈底表头栈通常栈可以用顺序的方式存储通常栈可以用顺序的方式存储(数组数组)，分配一块连续的，分配一块连续的存储区域存放栈中的表目，并用一个变量存储区域存放栈中的表目，并用一个变量t指向
8、当前栈顶指向当前栈顶（如下图）。（如下图）。栈的实现（一）Constm=栈表目数的上限；栈表目数的上限；Typestack=array1.mofstype；栈类型栈类型Vars：stack；栈栈top：integer；栈顶指针栈顶指针栈sm1top栈的实现（二）const m=栈表目数的上限；栈表目数的上限； type stack=record elem: array1.m of elemtp; top:0.m; 栈顶指针 end;Vars：stack；栈栈TOP=0表示栈空表示栈空Top=m表示栈满表示栈满栈的基本操作栈的基本操作栈的基本操作包括四种栈的基本操作包括四种q初始化（初始化（in
9、it）、）、q进栈（进栈（push）、）、q出栈（出栈（pop）、）、q读取栈顶元素（读取栈顶元素（top）。）。1）过程过程init(s,t)初始化初始化procedureinit;begint:=0;end;2)、过程过程push(x)往栈往栈s中压入一个值为中压入一个值为x的数据：的数据：procedurepush(vars：stack；x：stype；vart：integer)；beginift=mthenwriteln(overflow)上溢上溢elsebegintt+1；stx；end；elsex入栈入栈end；Push3）函数）函数pop(s，t)从栈中弹出一个表目从栈中弹出一个
10、表目 function pop (var s：stack； var t：integer)：stype； begin if t=0 then writeln (underflow) 下溢 else begin popst； tt-1； end；else 栈顶元素出栈 end；pop4）函数函数top(s，t)读栈顶元素读栈顶元素 function top (s：stack； t：integer)：stype； begin if t=0 then writeln (stack empty) else topst； 返回栈顶元素 end；top栈的应用栈的应用1、（1998） 栈栈S初始状态为空，现
11、有初始状态为空，现有5个元素组个元素组成的序列成的序列1，2，3，4，5，对该序列在栈，对该序列在栈S上上一次进行如下操作（从序列中的一次进行如下操作（从序列中的1开始，出栈开始，出栈后不再进栈）：进栈、进栈、进栈、出栈、进后不再进栈）：进栈、进栈、进栈、出栈、进栈、出栈、进栈。问出栈的元素序列是栈、出栈、进栈。问出栈的元素序列是_(A)5,4,3,2,1(B)2,1(C)2,3(D)3,4【样例样例3输入：输入：】【样例样例3输出：输出：】no【样例样例4输入：输入：】【样例样例4输出：输出：】no2、括号匹配、括号匹配【问题描述：问题描述：】判断包含有括号判断包含有括号，的字符串是否是合法
12、匹配。的字符串是否是合法匹配。例如以下是合法的括号匹配：例如以下是合法的括号匹配：(),(),(),(),()()以下是不合法括号匹配的：以下是不合法括号匹配的：(,)(,(,()，()【输入：输入：】一行，字符串（长度范围：一行，字符串（长度范围：1，200）。）。【输出：输出：】如果字符串中括号匹配是合法的输出如果字符串中括号匹配是合法的输出“yes”，不合法的输出，不合法的输出“no”。【样例样例1输入：输入：】【样例样例1输出：输出：】yes【样例样例2输入：输入：】【样例样例2输出：输出：】noi:=1; t:=0;tt:+0; while i=n do begin case si
13、of (,:push(si); ):if pop( then begin tt:=1;break;end; :if pop then tt:=1;break;end; :if pop then tt:=1;break;end; :if pop then tt:=1;break;end; end; inc(i); end; if (t0) or (tt0) then writeln(No) else writeln(Yes);end.var s:string; a:array0.200 of char; n,i,t,tt:integer; procedure push(k:char); begi
14、n inc(t); at:=k; end; function pop:char; begin pop:=at; dec(t); end;begin readln(s); a0:= ; n:=length(s);算法算法1 1：varvar f:arraycharf:arraychar of char; of char; a:array0.200 of char; a:array0.200 of char; s:strings:string; ; ch:charch:char; ; p,i,n:longintp,i,n:longint; ; function function pop:charp
15、op:char; ; begin pop:= begin pop:=ap;dec(pap;dec(p); end;); end; procedure procedure push(x:charpush(x:char);); begin begin inc(pinc(p); ); apap:=x; end;:=x; end; procedure procedure print(k:integerprint(k:integer);); begin begin writeln(kwriteln(k); ); halt;endhalt;end; ;beginbegin f:=; f:=; f(:=);
16、 f(:=); f:=; f:=; f; f;算法算法2 2： readln(sreadln(s);); p:=0; i:=1; n:= p:=0; i:=1; n:=length(slength(s);); while i=n do while i=n do begin begin if if ord(fsiord(fsi)0 then )0 then push(sipush(si) /) /左括号进栈左括号进栈 else /else /右括号判断右括号判断 beginbegin if p=0 then print(0); / if p=0 then print(0); /有多余的右括号有多
17、余的右括号 if if fpopfpopsisi then print(0); / then print(0); /和前面的不匹配和前面的不匹配 end;end; inc(iinc(i);); end; end; if p=0 then print(1) else print(0); if p=0 then print(1) else print(0);end.end.栈的应用栈的应用3表达式求值表达式求值输入一个表达式，该表达式含有输入一个表达式，该表达式含有“+”、“-”、“*”、“/”、“（”、“）”和操作数和操作数输入以输入以结束结束。输出该表达式的值。输出该表达式的值。分析：分析：由
18、由于于一一个个表表达达式式含含操操作作数数、运运算算符符和和括括号号，因因此此只只能能采采用用字字符符串串类类型型输输入入，而而字字符符是是不不能能进进行行数数值值计计算算的的。在在这这种种情情况况下下，计算机又如何计算表达式的值呢。一般方法是：计算机又如何计算表达式的值呢。一般方法是：中缀表达式中缀表达式等价的后缀表达式等价的后缀表达式计算后计算后缀表达式的值缀表达式的值中缀表达式和后缀表达式的特征中缀表达式和后缀表达式的特征中中缀缀表表达达式式：中缀表达式与通常的表达式一样，运算符位于两个操作之间，计算规则为先括号内、后括号外；无括号或同层括号内先*、/、后+、-；同级运算按由左至右顺序进
19、行。为了计算方便，输入的中缀表达式串常以为结束标志。例如3*(52)+7后后缀缀表表达达式式：后缀表达式中不再引入括号，运算符放在两个运算对象之后。所有计算按运算符出现的顺序，严格地由左而右进行（不再考虑运算符的优先规则）。为了计算方便，以.为操作数的结束标志，以为后缀表达式的结束标志。例如3*（5-2）+7 对应的后缀表达式为 352-*7+。后缀表达式是简化运算顺序的一种表达式。 中缀表达式的运算规则比较多，包括优先级、左右次序和括号；尤其是括号可以改变优先顺序，这就只能在计算的每一步，用肉眼去扫描、观察和比较整个表达式中谁的优先级高，就先计算那部分。但用计算机去做就很麻烦，而且效率不高。
20、所以，计算机科学中是把中缀表达式先转换成后缀表达式，在利用计算机来计算后缀表达式的值。后缀表达式又称“逆波兰式”，在后缀表达式中，不存在括号，也不存在优先级的差别，计算过程完全按照运算符出现的先后顺序进行，整个计算过程仅需一遍扫描即可完成。中缀表达式转化成后缀表达式的规则是：只要将每个运算符移到它的两个运算对象的后面，再删去所有括号，便得到与之等价的后缀表达式栈的应用栈的应用-中缀转后缀中缀转后缀输入一个中缀表达式，编程输出其后缀表达式，要求输出的后缀表达式的运算次序与输入的中缀表达式的运算次序相一致。为简单起见，假设输入的中缀表达式由（加）、（减）、（乘）、（除）四个运算符号以及左右圆括号和
21、大写英文字母组成，其中算术运算符遵守先乘除后加减的运算规则。假设输入的中缀表达式长度不超过80个字符，且都是正确的，即没有语法错误，并且凡出现括号其内部一定有表达式，即内部至少有一个运算符号。以下是一个运行实例。输入：X+A*（Y-B）-Z/F输出：XAYB-*+ZF/-设置两个栈：操作数栈（ovs）和运算符栈（ops），用来分别存放表达式中的操作数和运算符。开始时操作数栈为空，运算符栈中放入一个特殊的标志运算符号#号，并在表达式的末尾加上一个#号，并规定#号的优先级最低，然后从左向右扫描表达式，凡遇操作数便一律进栈；若遇运算符，则判断其优先级是否大于运算符栈栈顶元素的优先级。若小，则栈顶运算
22、符退栈，并从操作数栈中弹出两个操作数（操作数为后缀表达式）进行后缀变换处理，处理结果进操作数栈，重复刚才的比较，直到栈顶运算符的优先级小于等于当前运算符的优先级，此时，若当前运算符的优先级大于栈顶运算符的优先级，则当前运算符进栈，继续扫描；若当前运算符的优先级等于栈顶运算符的优先级，则弹出栈顶运算符，继续扫描。扫描完该表达式后运算符栈为空，操作数栈中只有一个元素，该元素就是所要求的后缀表达式。X+A*（Y-B）-Z/F以下程序中的数组f用来存放运算符之间的优先级关系，1()表示前面的运算符优先于后面的运算符，-1( - - * * / / ( ( = =ERRORERROR) )ERRORER
23、RORERRORERRORERRORERRORERRORERROR# # ERRORERROR= =P2P1X+A*（Y-B）-Z/F上述算法还可用于求一个表达式的值和判断一个表达式是否有错等等。program ex2;const max=100; op_set:set of char=+,-,*,/;运算符集合 letter:set of char=A.Z;运算数集合var expression,result:string;中缀表达式，后缀表达式，字符串procedure scan(expression:string);本过程完成中缀的扫描及到后缀的转换 var i,top1,top2:in
24、teger;操作数栈和操作符栈的栈顶指针 ovs:array 1.max of stringmax;操作数栈 ops:array 1.max of char;操作符栈 f:array#./,#./ of shortint;数组f用来存放运算符之间的优先级关系 begin f+,+:=1; f+,-:=1; f+,*:=-1; f+,/:=-1; f+,(:=-1; f+,):=1; f+,#:=1; f-,+:=1; f-,-:=1; f-,*:=-1; f-,/:=-1; f-,(:=-1; f-,):=1; f-,#:=1; f*,+:=1; f*,-:=1; f*,*:=1; f*,/:
25、=1; f*,(:=-1; f*,):=1; f*,#:=1; f/,+:=1; f/,-:=1; f/,*:=1; f/,/:=1; f/,(:=-1; f/,):=1; f/,#:=1; f(,+:=-1;f(,-:=-1;f(,*:=-1; f(,/:=-1; f(,(:=-1; f(,):=0; f(,#:=2; f),+:=2; f),-:=2; f),*:=2; f),/:=2; f),(:=2; f),):=2; f),#):=2;f#,+:=-1;f#,-:=-1;f#,*:=-1; f#,/:=-1; f#,():=-1; f#,:=2; f#,#:=0;expression
26、:=expression+#;表达式的末尾放一个“#” ops1:=#; 操作符栈先放入一个“#” top1:=0;初始化操作数栈 top2:=1; 操作符栈中放入一个“#”for i:=1 to length(expression) do在中缀表达式的长度范围内执行循环 begin if expressioni in letter 如果扫描到的中缀表达式的内容是操作数 then begin top1:=top1+1; ovstop1:=expressioni 操作数进栈 end else begin while fopstop2,expressioni=1 dobegin ovstop1-1
27、:=ovstop1-1+ovstop1+opstop2; top1:=top1-1; top2:=top2-1 end; 若遇运算符，则判断其优先级是否大于运算符栈栈顶元素的优先级。若小，则栈顶运算符退栈，并从操作数栈中弹出两个操作数（操作数为后缀表达式）进行后缀变换处理，处理结果进操作数栈重复刚才的比较，直到栈顶运算符的优先级大于等于当前运算符的优先级。if fopstop2,expressioni=0 then top2:=top2-1 else begin top2:=top2+1; opstop2:=expressioni end;若当前运算符的优先级大于栈顶运算符的优先级，则当前运算
28、符进栈，继续扫描；若当前运算符的优先级等于栈顶运算符的优先级，则弹出栈顶运算符，继续扫描。end end; result:=ovs1 扫描完该表达式后运算符栈为空，操作数栈中只有一个元素，该元素就是所要求的后缀表达式。end;beginmain write(Input a expression:); readln(expression); scan(expression); writeln(The result is: ,result)end.测试输入：A*(X+Y)/(B-Z)输出：AXY+*BZ-/将中缀表达式转换为等价的后缀表达式将中缀表达式转换为等价的后缀表达式(方法方法2)在中缀表达
29、式中，运算符出现次序与计算顺序不一致，实际计算顺序不仅要看它的出现次序，还要受运算符的优先级和括号的影响。如果把一个中缀表达式中所有的计算顺序都按计算规则用嵌套括号的形式表示出来，其转换过程就要清楚的多。例如中缀表达式3*(52)+7可以改写成（(3*(52)+7）。这时可以看出，只要将每对括号中的运算符移到相应括号的后面，再删去所有括号，便得到与之等价的后缀表达式352*7+ 。为了将中缀表达式转换为等价的后缀表达式，需要从左至右扫描中缀表达式，并使用一个栈s2来存放中缀表达式中的开括号（和暂时不能参与计算的运算符，显然s2栈的元素类型为char。为了方便表达式值的计算，在转换后的后缀表达式
30、中，每一个操作数尾添加一个.。例如计算3*(52)+7constconst m=1000; m=1000;type stack=array1.mof char;type stack=array1.mof char;varvar a,e:stringa,e:string; ; 后缀表达式和中缀表达式 s:stacks:stack; ; 栈，存放暂不参与计算的运算符 t,i:integert,i:integer; ; 栈顶指针、中缀表达式的字符指针 w:charw:char; ; fi,fo:textfi,fo:text; ;procedure procedure push(x:charpush(
31、x:char););beginbegin t:=t+1; t:=t+1; stst:=x;:=x;end;end;function function pop:charpop:char; ;beginbegin pop:= pop:=stst; t:=t-1; t:=t-1;end;end;function function top(s:stack;t:integer):chartop(s:stack;t:integer):char; ;beginbegin top:= top:=stst;end;end;beginbegin assign(fi,zzh.inassign(fi,zzh.in);
32、); reset(fireset(fi);); assign(fo,zzh.outassign(fo,zzh.out);); rewrite(forewrite(fo);); read(fi,eread(fi,e);); a:=;i:=1;t:=0; a:=;i:=1;t:=0; 后缀表达式初始化为空 从中缀表达式的第一个字符开始分析，栈空 while while eiei do begin do begin 由左而右扫描处理中缀表达式的每一个字符 case case eiofeiof 0.9:begin 0.9:begin 操作数进入后缀表达式 while while eiei. do be
33、gin. do begin a:= a:=a+eia+ei; i:=i+1; i:=i+1; end; end; a:=a+.; a:=a+.; 添加操作数的结尾标志 end; end; (:push(); (:push(); （入栈 ):begin ):begin s栈中栈顶至(间的所有运算符相继出栈，进入后缀表达式 w:=pop; w:=pop; while w( do begin while w( do begin a:= a:=a+wa+w; ; w:=pop; w:=pop; end; end; end; end; +,-:begin+,-:begin s栈中，栈顶至(前的所有运算符
34、相继出栈，进入后缀表达式，ei进入s栈 if t0 then begin if t0 then begin w:= w:=top(s,ttop(s,t);); while w( do begin while w( do begin a:= a:=a+wa+w; w:=pop; w:=pop; if t=0 then break else w:= if t=0 then break else w:=top(s,ttop(s,t);); end; end; end; end; push ( push (eiei);); end; end; *,/:begin *,/:begin s栈中栈顶至第1个
35、+或-前的所有运算符相继出栈，进入后缀表达式，ei进入s栈 if t0 then begin if t0 then begin w:= w:=top(s,ttop(s,t);); while (w=*) while (w=*)or(wor(w=/)do begin=/)do begin a:= a:=a+wa+w; w:=pop; w:=pop; if t=0 then break if t=0 then break else w:= else w:=top(s,ttop(s,t);); end; end; end; end; push(eipush(ei);); end; end; end;
36、 end; i:=i+1; i:=i+1; 准备扫描处理中缀表达式的下一个字符 end; end; whilet0doa:=a+pop;s栈中的运算符相继出栈，进入后缀表达式a:=a+;writeln(fo,a);close(fi);close(fo);end.栈的应用栈的应用4-计算后缀表达式计算后缀表达式所谓后缀表达式是指这样的一种表达式：式中不再引入括号，运算符放在两个运算对象之后。所有计算按运算符出现的顺序，严格地由左而右进行（不再考虑运算符的优先规则）。例如 3*（5-2）+7 对应的后缀表达式为 352-*7+ 其中为后缀表达式的结束标记，为操作数的结束符。 352-*7+ =33
37、*7+ =97+ =16 输入：输入： 后缀表达式A（假定A合乎文法，不需判错）； 输出：输出： 表达式的值。后缀表达式求值后缀表达式求值【问题描述：问题描述：】 所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。新进行（不用考虑运算符的优先级）。 1) 1) 运算符号：运算符号：+ +、- -、* *、/ /。/ / 运算只取整数部分。采用运算只取整数部分
38、。采用 div div 即可即可 2) 2) 一个完整的运算数以一个完整的运算数以”. .”作为结束符号。作为结束符号。 3) 3) 运算的中间结果与最后的结果数据范围：运算的中间结果与最后的结果数据范围：-1000000000-1000000000，10000000001000000000。 如：如：3*(53*(52)+72 2)+72 对应的后缀表达式为：对应的后缀表达式为：3 35 52 2-*72-*72+ + 运算过程：运算过程：3 35 52 2-*72-*72+ =3+ =33 3* *7272+=9+=97272+=81+=81【输入：输入：】一行：一行： 后缀表达式（长度不
39、超过后缀表达式（长度不超过100100）。）。【输出：输出：】 表达式的值。表达式的值。【样例输入：样例输入：】3 35 52 2-*72-*72+ +【样例输出：样例输出：】8181方法：利用栈结构方法：利用栈结构算法分析：算法分析：假假设设后后缀缀的的表表达达式式为为A A，操操作作数数和和计计算算结结果果存存放放在在栈栈S S中中，s s的的类类型型为为integerinteger。从左向右处理从左向右处理A A中的每一个字符：中的每一个字符：如果遇到一个操作数，就送入栈如果遇到一个操作数，就送入栈s s中；中；如如果果遇遇到到一一个个运运算算符符，就就从从栈栈s s中中取取出出栈栈顶顶
40、的的两两个个操操作作数数进进行行计计算算，然后将计算结果重新压栈。然后将计算结果重新压栈。直到最后一个运算符处理结束，这时栈直到最后一个运算符处理结束，这时栈s s顶的元素即是计算结果。顶的元素即是计算结果。例如计算后缀表达式例如计算后缀表达式3 35 52 2-*7-*7+ +的值的值352-*7+constm=100;typestack=array1.mofinteger;定义栈类型定义栈类型vars:stack;栈栈a:string;后缀表达式，字符串后缀表达式，字符串t,i,j,k,len:integer;t栈顶指针；栈顶指针；i后缀表达式的字符指针；后缀表达式的字符指针；k、j操作数
41、值操作数值procedurepush(x:integer);进栈进栈begint:=t+1;st:=x;end;functionpop:integer;出栈出栈beginpop:=st;t:=t-1;end;beginbegin readln(areadln(a); ); 读入后缀表达式读入后缀表达式 lenlen:=length(a); :=length(a); 后缀表达式的长度后缀表达式的长度 i:=1; i:=1; 后缀表达式字符指针初始化后缀表达式字符指针初始化 t:=0; t:=0; 栈初始化栈初始化 while i= while i=lenlen do do 处理后缀表达式，循环直
42、至结束处理后缀表达式，循环直至结束 begin begin case ai of case ai of 0.9:begin0.9:begin k:=0; k:=0; while ai. do while ai. do begin begin 从从s中取出一个完整的操作数中取出一个完整的操作数k k:=10*k+ord(ai)-48; k:=10*k+ord(ai)-48; ord(0)=48 i:=i+1; i:=i+1; end; end; push(k); push(k);把把操作数操作数k压栈压栈 end; end; +:push(pop+pop); +:push(pop+pop); 从
43、栈从栈s中取出栈顶的两个数进行加法运算，然后将结果在压栈中取出栈顶的两个数进行加法运算，然后将结果在压栈 -:begin -:begin 从栈从栈s s中取出栈顶的两个数进行减法运算，然后将结果在压栈中取出栈顶的两个数进行减法运算，然后将结果在压栈 j:=pop; j:=pop; push(pop-j); push(pop-j); end; end; *:push(pop*pop); *:push(pop*pop); 从栈从栈s s中取出栈顶的两个数进行乘法运算，然后将结果在压栈中取出栈顶的两个数进行乘法运算，然后将结果在压栈 /:begin /:begin 从栈从栈s s中取出栈顶的两个数进行除法运算，然后将结果在压栈中取出栈顶的两个数进行除法运算，然后将结果在压栈 j:=pop; j:=pop; push(pop div j); push(pop div j); end; end;end;caseend;case i:=i+1;i:=i+1; end;while end;while writeln(popwriteln(pop); ); 取出栈顶元素，即时表达式的最后结果取出栈顶元素，即时表达式的最后结果 end.end.
