首页 > 代码库 > 基础算法（一）——栈

基础算法（一）——栈

2024-11-24 13:33:02   203人阅读

栈(stack)是简单的数据结构，但在计算机中使用广泛。它是有序的元素集合。栈最显著的特征是LIFO (Last In, First Out, 后进先出)。

通常对栈的操作分为：进栈（push），出栈（pop）。
在对栈的处理中，需要有一个栈顶指针（top），如图1-1所示。
技术分享
(图1-1)
几个对于栈的重要的操作（伪代码）（对于待处理数据x的处理过程）
【一般初始化】
//pascal
Stack:array[1..10000]of longint;
Top:longint;
【进栈操作】
a[top+1]:=x;
top→top+1;
【出栈操作】
outp:=a[top];
top→top-1; //其实对于出栈的操作，只需要将栈顶指针自减1即可。
【重点】所有的递归操作都可以用栈来实现
 
【例题】括弧匹配检验：假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，如（［ ］（））或［（［ ］［ ］）］等为正确的匹配，［（ ]）或（［ ］（ ）或 ( ( ) ) ）均为错误的匹配。请编写一个程序检验一个给定表达式中的括弧是否正确匹配？若匹配，则返回“OK”，否则返回“Wrong”。假设表达式长度小于1000000。
参考程序：
var a:array[1..100]of char; 
  top:integer; 
  s:set of char; 
  ch:char; b:boolean; 
begin 
 s:=[‘(‘,‘[‘]; 
 b:=true; 
 while not eoln do 
   begin 
     read(ch); 
     if ch in s then 
       begin   //进栈开始
         inc(top); 
         a[top]:=ch; 
       end //进栈结束
       else if top=0 then b:=false   //判断
           else 
             case a[top] of  
                ‘(‘:if ch=‘)‘ then dec(top) else b:=false; 
                ‘[‘:if ch=‘]‘ then dec(top) else b:=false; 
             end; 
   end; 
 if b then writeln(‘OK‘) else writeln(‘Wrong‘);   //结果输出
end.
【例题】表达式求值
若Exp=a×b＋(c－d/e)×f 则
前缀式为：＋×ab ×－c /def
中缀式为：3×1＋(4－6/2)×9=12
后缀式为：31×462/－9×＋=12
因为表达式是递归定义的，则它的转换也是递归的。
后缀式的运算规则为：
运算符在式中出现的顺序恰为表达式的运算顺序；
每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式；
给出后缀表示法能否计算出结果？
给出中缀表示法能否计算出结果？
【重点】学会后缀表达式、中缀表达式、前缀表达式（这个不太用得到）相互的转换方法。
参考程序：
//中缀表达式转换为后缀表达式
//【本参考程序由gzh提供】
Var
  s,ans:string;
Function switch(s:string):string;
  var
    i,j,len:longint;
    s1,s2:string;
    top:longint;
    flog:boolean;
  begin
    len:=length(s);
    if len=1 then exit(s);
    top:=0; flog:=false;
    for i:=1 to len do
    begin
      if s[i]=‘(‘ then inc(top);
      if s[i]=‘)‘ then dec(top);
      if(top=0)and(i<len)then flog:=true;
    end;
    if not flog then
    begin
      delete(s,1,1); delete(s,len-1,1);
      exit(switch(s));
    end;
    for i:=1 to len do
    begin
      if s[i]=‘(‘ then inc(top);
      if s[i]=‘)‘ then dec(top);
      if(top=0)and(s[i]=‘+‘)then
      begin
        s1:=‘‘; s2:=‘‘;
        for j:=1 to i-1 do s1:=s1+s[j];
        for j:=i+1 to len do s2:=s2+s[j];
        s1:=switch(s1); s2:=switch(s2);
        exit(s1+s2+‘+‘);
      end;
      if(top=0)and(s[i]=‘-‘)then
      begin
        s1:=‘‘; s2:=‘‘;
        for j:=1 to i-1 do s1:=s1+s[j];
        for j:=i+1 to len do s2:=s2+s[j];
        s1:=switch(s1); s2:=switch(s2);
        exit(s1+s2+‘-‘);
      end;
    end;
    for i:=1 to len do
    begin
      if s[i]=‘(‘ then inc(top);
      if s[i]=‘)‘ then dec(top);
      if(top=0)and(s[i]=‘*‘)then
      begin
        s1:=‘‘; s2:=‘‘;
        for j:=1 to i-1 do s1:=s1+s[j];
        for j:=i+1 to len do s2:=s2+s[j];
        s1:=switch(s1); s2:=switch(s2);
        exit(s1+s2+‘*‘);
      end;
      if(top=0)and(s[i]=‘/‘)then
      begin
        s1:=‘‘; s2:=‘‘;
        for j:=1 to i-1 do s1:=s1+s[j];
        for j:=i+1 to len do s2:=s2+s[j];
        s1:=switch(s1); s2:=switch(s2);
        exit(s1+s2+‘/‘);
      end;
    end;
  end;
Begin
  readln(s);
  ans:=switch(s);
  writeln(ans);
End.

基础算法（一）——栈


联系
我们