1 Status InitStack()//构造一个空栈S2 Status DestroyStack()//销毁栈S，S不再存在3 Status ClearStack()//把S置为空栈4 Status StackEmpty()//若S为空栈，则返回true，否则返回false5 int StackLength()//返回S的元素个数，即栈的长度6 Status GetTop(SElemType &e)//若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR7 Status Push(SElemType e)//插入元素e为新的栈顶元素8 Status Pop(SElemType &e)//若栈不空，则删除S的栈顶元素，并用e返回其值，并返回OK，否则返回ERROR9 Status StackTraverse(int p)//从栈底到栈顶依次对栈中每个元素调用函数visit().一旦visit()失败则操作失败

1 CheckStackCode();//测试Stack代码正确性2 Conversion();//数制转换3 BracketsMatching();//括号匹配的检验4 LineEdit();//行编辑程序

  1 //  2 //by coolxxx  3 //#include<bits/stdc++.h>  4 #include<iostream>  5 #include<algorithm>  6 #include<string>  7 #include<iomanip>  8 #include<map>  9 #include<stack> 10 #include<queue> 11 #include<set> 12 #include<bitset> 13 #include<memory.h> 14 #include<time.h> 15 #include<stdio.h> 16 #include<stdlib.h> 17 #include<string.h> 18 //#include<stdbool.h> 19 #include<math.h> 20 #define min(a,b) ((a)<(b)?(a):(b)) 21 #define max(a,b) ((a)>(b)?(a):(b)) 22 #define abs(a) ((a)>0?(a):(-(a))) 23 #define lowbit(a) (a&(-a)) 24 #define sqr(a) ((a)*(a)) 25 #define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b)) 26 #define mem(a,b) memset(a,b,sizeof(a)) 27 #define eps (1e-10) 28 #define J 10000 29 #define mod 1000000007 30 #define MAX 0x7f7f7f7f 31 #define PI 3.14159265358979323 32 #pragma comment(linker,"/STACK:1024000000,1024000000") 33 #define N 104 34  35 using namespace std; 36 typedef long long LL; 37 /* 38 double anss; 39 LL aans,sum; 40 int cas,cass; 41 int n,m,lll,ans; 42 */ 43  44  45 const int OK=1; 46 const int ERROR=0; 47 const int INFEASIBLE=-1; 48 const int STACK_INIT_SIZE=100;//存储空间初始分配量 49 const int STACKINCREMENT=10;//存储空间分配增量 50 typedef int Status; 51 typedef int SElemType; 52  53 Status OutputInt(SElemType e); 54 Status OutputChar(SElemType e); 55 typedef struct 56 { 57     SElemType *base;//栈构造之前和销毁之后，base的值为NULL 58     SElemType *top;//栈顶指针 59     int stacksize;//当前已分配的存储空间，以元素为单位 60      61     Status InitStack()//构造一个空栈S 62     { 63         base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); 64         if(!base)exit(OVERFLOW);//存储分配失败 65         top=base; 66         stacksize=STACK_INIT_SIZE; 67         return OK; 68     }//InitStack 69      70     Status DestroyStack()//销毁栈S，S不再存在 71     { 72         free(base); 73         base=NULL; 74         top=NULL; 75         stacksize=0; 76         return OK; 77     }//DestroyStack 78      79     Status ClearStack()//把S置为空栈 80     { 81         top=base; 82         return OK; 83     }//ClearStack 84      85     Status StackEmpty()//若S为空栈，则返回true，否则返回false 86     { 87         if(top==base)return true; 88         return false; 89     }//StackEmpty 90      91     int StackLength()//返回S的元素个数，即栈的长度 92     { 93         return top-base; 94     }//StackLength 95      96     Status GetTop(SElemType &e)//若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR 97     { 98         if(top==base)return ERROR; 99         e=*(top-1);100         return OK;101     }//GetTop102     103     Status Push(SElemType e)//插入元素e为新的栈顶元素104     {105         if(top-base>=stacksize)//栈满，追加存储空间106         {107             base=(SElemType *)realloc(base,(stacksize+STACKINCREMENT)*sizeof(SElemType));108             if(!base)exit(OVERFLOW);//存储分配失败109             top=base+stacksize;110             stacksize+=STACKINCREMENT;111         }112         (*top++)=e;113         return OK;114     }//Push115     116     Status Pop(SElemType &e)//若栈不空，则删除S的栈顶元素，并用e返回其值，并返回OK，否则返回ERROR117     {118         if(top==base)return ERROR;119         e=(*--top);120         return OK;121     }//Pop122     123     Status StackTraverse(int p)//从栈底到栈顶依次对栈中每个元素调用函数visit().一旦visit()失败则操作失败124     {125         SElemType *i=base;126         Status (*visit)(SElemType);127         if(p==1)visit=OutputInt;128         else if(p==0)visit=OutputChar;129         while(top>i)130             visit(*i++);131         puts("");132         return OK;133     }//StackTraverse134 }SqStack;135 136 Status OutputInt(SElemType e)137 {138     printf("%d ",e);139     return OK;140 }141 Status OutputChar(SElemType e)142 {143     printf("%c",e);144     return OK;145 }146 147 148 void CheckStackCode()149 {150     typedef int SElemType;151     int i;152     SqStack S;153     SElemType e;154     if(S.InitStack()==OK)155     {156         for(i=1;i<=12;i++)157             S.Push(i);158     }159     printf("栈中元素依次为：");160     S.StackTraverse(1);161     S.Pop(e);162     printf("弹出的栈顶元素 e=%d\n",e);163     printf("栈空否：%d(1：空 0：否)\n",S.StackEmpty());164     S.GetTop(e);165     printf("栈顶元素 e=%d 栈的长度为%d\n",e,S.StackLength());166     S.Push(13);167     printf("栈中元素依次为：");168     S.StackTraverse(1);169     S.GetTop(e);170     printf("栈顶元素 e=%d 栈的长度为%d\n",e,S.StackLength());171     S.DestroyStack();172     printf("销毁栈后，S.top=%d  S.base=%d  S.stacksize=%d\n",S.top,S.base,S.stacksize);173 }174 175 void Conversion()//对于输入的任意一个非负十进制整数n，打印输出与其等值的八进制数176 {177     typedef int SElemType;178     int n;179     SqStack S;180     SElemType e;181     182     S.InitStack();//构造空栈183     scanf("%d",&n);184     while(n)185     {186         S.Push(n%8);187         n/=8;188     }189     while(!S.StackEmpty())190     {191         S.Pop(e);192         printf("%d",e);193     }194     puts("");195     196     S.DestroyStack();197 }198 199 void BracketsMatching()//三种括号()[]{}，检验是否合法200 {201     202     char s[N];203     SqStack S;204     SElemType e;205     int i;206     S.InitStack();207     scanf("%s",s);208     209     for(i=0;i<strlen(s);i++)210     {211         if(s[i]==‘(‘ || s[i]==‘{‘ || s[i]==‘[‘)212             S.Push(s[i]);213         else if(s[i]==‘)‘ || s[i]==‘}‘ || s[i]==‘]‘)214         {215             if(S.GetTop(e) && ((e==‘(‘ && s[i]==‘)‘) || (e==‘[‘ && s[i]==‘]‘) || (e==‘{‘ && s[i]==‘}‘)))216                 S.Pop(e);217             else218             {219                 puts("NO");220                 S.DestroyStack();221                 return;222             }223         }224     }225     if(S.StackEmpty())puts("YES");226     else puts("NO");227     S.DestroyStack();228 }229 230 void LineEdit()//从终端接收一行并传送至调用过程的数据区，#为退格符，@为退行符231 {232     int i;233     char ch;234     SqStack S;235     SElemType e;236     S.InitStack();237     while(ch!=EOF)238     {239         for(ch=getchar();ch!=EOF && ch!=‘\n‘;ch=getchar())240         {241             if(ch==‘#‘)S.Pop(e);242             else if(ch==‘@‘)S.ClearStack();243             else S.Push(ch);244         }245         S.StackTraverse(0);246         S.ClearStack();247     }248     S.DestroyStack();249 }250 251 252 int main()253 {254     #ifndef ONLINE_JUDGEW255     freopen("1.txt","r",stdin);256 //    freopen("2.txt","w",stdout);257     #endif258     int i,j,k;259 //    init();260 //    for(scanf("%d",&cass);cass;cass--)261 //    for(scanf("%d",&cas),cass=1;cass<=cas;cass++)262 //    while(~scanf("%s",s))263 /*264     while(~scanf("%d%d",&n,&m))265     {266         267     }268     */269     270     CheckStackCode();//测试Stack代码正确性271     272     Conversion();//数制转换273     274     BracketsMatching();//括号匹配的检验275     276     LineEdit();//行编辑程序277     278     return 0;279 }280 /*281 //282 283 //284 */