栈->栈的应用

e.g.1 数制转换

十进制数N和其它d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理。

假设编写一个程序：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。由于上述计算过程是从低位到高位顺序产生八进制数的各个数位，而打印输出，一般来说应从高位到低位进行，恰好和计算过程相反。因此，若将计算过程中得到的八进制数的各为顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数。

e.g.2 括号匹配

假设表达式中运行包含两种括号：圆括号和方括号，其嵌套的顺序随意，即([]())或[([])[]]等为正确的格式，[(])或([()]或为不正确的格式。可利用栈来检验括号是否匹配。

e.g.3 行编辑程序

一个简单的行编辑程序的功能:接受用户从终端输入的程序或数据，并存入用户的数据区。由于用户在终端上进行输入时，不能保证不出差错，当用户发现刚刚键入的一个字符是错的时，可补进一个退格符#，表示前一个字符无效；如果发现当前键入的行内差错较多或难以补救，则可以键入一个退格符@，表示当前行中的字符均无效。

e.g.4 表达式求值

可以使用两个工作栈。一个称为OPTR，用来存运算符(+=*/()#)；另一个称为OPND，用来存放操作数或运算结果。算法的基本思想是：

(1) 首先将操作数栈置为空栈，表达式起始符#为运算法栈的栈底元素；

(2) 依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕(即OPTR栈的栈顶元素和当前读入的字符均为#)

e.g.5 迷宫求解

求迷宫中从入口到出口的路径：(如下图)

代码实现

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 
  5 #define STACK_INIT_SIZE 100
  6 #define STACKINVREMENT 10
  7 typedef char SElemType;
  8 typedef struct {
  9     SElemType *base;
 10     SElemType *top;
 11     int stacksize;
 12 }SqStack;
 13 
 14 static int InitStack(SqStack *S);
 15 static int GetTop(SqStack *S, SElemType *e);
 16 static int Push(SqStack *S, SElemType e);
 17 static int Pop(SqStack *S, SElemType *e);
 18 static int StackTraversie(SqStack S);
 19 static int StackEmpty(SqStack S);
 20 static int ClearStack(SqStack *S);
 21 static int DestoryStack(SqStack *S);
 22 
 23 static void conversion()
 24 {
 25     int N = 0;
 26     SElemType E;
 27     SqStack S;
 28     InitStack(&S);
 29     printf("请输入一个十进制数:");
 30     scanf("%d", &N);
 31     while(N){
 32         Push(&S, '0'+N%8);
 33         N=N/8;
 34     }
 35     printf("该数的八进制数为：");
 36     while(StackEmpty(S)<0){
 37         Pop(&S, &E);
 38         printf("%c", E);
 39     }
 40     printf("
");
 41 }
 42 
 43 static int bracketMatch()
 44 {
 45     SElemType e;
 46     SqStack S;
 47     InitStack(&S);
 48 
 49     int err = 0;
 50     char string[100] = {0};
 51     char *c = string;
 52     printf("输入待检验的字符串:");
 53     scanf("%s[^\n]", string);
 54     while(*c){
 55         switch(*c){
 56             case '[':
 57             case '(':
 58                 Push(&S, *c);
 59                 break;
 60             case ']':
 61                 if((!GetTop(&S, &e)) && (e == '[')){
 62                     Pop(&S, &e);
 63                 }else{
 64                     err = -1;
 65                     goto end;
 66                 }
 67                 break;
 68             case ')':
 69                 if((!GetTop(&S, &e)) && (e == '(')){
 70                     Pop(&S, &e);
 71                 }else{
 72                     err = -2;
 73                     goto end;
 74                 }
 75                 break;
 76             default:
 77                 err = -3;
 78                 goto end;
 79         }
 80         c++;
 81     }
 82 end:
 83     if(err<0){
 84         printf("%s 是不匹配的!
", string);
 85     }else{
 86         printf("%s 是匹配的!
", string);
 87     }
 88     return err;
 89 }
 90 
 91 static void lineEdit()
 92 {
 93     SElemType e;
 94     SqStack S;
 95     InitStack(&S);
 96 
 97     char line[100] = {0};
 98     char data[100] = {0};
 99     char *c = line;
100     printf("输入字符串(其中#表示上一个字符无效，@表示此此行该字符前的所有字符无效, end表示结束):");
101     scanf("%s[^\n]", line);
102     if(strncmp(line, "end", strlen("end")) == 0){
103         return ;
104     }
105     while(*c){
106         if(*c == '!'){
107             DestoryStack(&S);
108             break;
109         }
110         switch(*c){
111             case '#':
112                 Pop(&S, &e);
113                 break;
114             case '@':
115                 ClearStack(&S);
116                 break;
117             default:
118                 Push(&S, *c);
119                 break;
120         }
121         c+=1;
122         if(!(*c)){
123             printf("输出字符:%s
", S.base);
124             ClearStack(&S);
125             memset(line, 0, sizeof(line));
126             printf("输入字符串(其中#表示上一个字符无效，@表示此此行该字符前的所有字符无效, end表示结束):");
127             scanf("%s[^\n]", line);
128             if(strncmp(line, "end", strlen("end")) == 0){
129                 return;
130             }
131             c = line;
132         }
133     }
134 }
135 
136 static int IsOPTR(char c, char OP[], int len)
137 {
138     int i = 0;
139     for(i=0; i<len; i++){
140         if(c == OP[i]){
141             return 0;
142         }
143     }
144     return -1;
145 }
146 
147 static char Precede(char c1, char c2)
148 {
149     int I[50] = {0};
150     I['+'] = 0;
151     I['-'] = 1;
152     I['*'] = 2;
153     I['/'] = 3;
154     I['('] = 4;
155     I[')'] = 5;
156     I['#'] = 6;
157     char table[7][7] = {0};
158     table[I['+']][I['+']] = '>';table[I['+']][I['-']] = '>';table[I['+']][I['*']] = '<';table[I['+']][I['/']] = '<';table[I['+']][I['(']] = '<';table[I['+']][I[')']] = '>';table[I['+']][I['#']] = '>';
159     table[I['-']][I['+']] = '>';table[I['-']][I['-']] = '>';table[I['-']][I['*']] = '<';table[I['-']][I['/']] = '<';table[I['-']][I['(']] = '<';table[I['-']][I[')']] = '>';table[I['-']][I['#']] = '>';
160     table[I['*']][I['+']] = '>';table[I['*']][I['-']] = '>';table[I['*']][I['*']] = '>';table[I['*']][I['/']] = '>';table[I['*']][I['(']] = '<';table[I['*']][I[')']] = '>';table[I['*']][I['#']] = '>';
161     table[I['/']][I['+']] = '>';table[I['/']][I['-']] = '>';table[I['/']][I['*']] = '>';table[I['/']][I['/']] = '>';table[I['/']][I['(']] = '<';table[I['/']][I[')']] = '>';table[I['/']][I['#']] = '>';
162     table[I['(']][I['+']] = '<';table[I['(']][I['-']] = '<';table[I['(']][I['*']] = '<';table[I['(']][I['/']] = '<';table[I['(']][I['(']] = '<';table[I['(']][I[')']] = '=';table[I['(']][I['#']] = ' ';
163     table[I[')']][I['+']] = '>';table[I[')']][I['-']] = '>';table[I[')']][I['*']] = '>';table[I[')']][I['/']] = '>';table[I[')']][I['(']] = ' ';table[I[')']][I[')']] = '>';table[I[')']][I['#']] = '>';
164     table[I['#']][I['+']] = '<';table[I['#']][I['-']] = '<';table[I['#']][I['*']] = '<';table[I['#']][I['/']] = '<';table[I['#']][I['(']] = '<';table[I['#']][I[')']] = ' ';table[I['#']][I['#']] = '=';
165     return table[I[c1]][I[c2]];
166 }
167 
168 static char Operate(char a, char theta, char b)
169 {
170     int i = atoi(&a);
171     int j = atoi(&b);
172     int ret = 0;
173     if(theta == '+'){
174         ret =  i+j;
175     }
176     if(theta == '-'){
177         ret =  i-j;
178     }
179     if(theta == '*'){
180         ret =  i*j;
181     }
182     if((theta=='/') && (j!=0)){
183         ret = i/j;
184     }
185     return (char)(ret+'0');
186 }
187 
188 static int EvaluateExpression()
189 {
190     SElemType e;
191     SqStack OPTR;
192     SqStack OPND;
193     InitStack(&OPTR); //操作符
194     InitStack(&OPND); //操作数
195     Push(&OPTR, '#');
196     char line[100] = {0};
197     char *c = line;
198     char OP[10] = "+-*/()#", theta, a, b;
199     printf("输入仅含有运算符+-*/()的表达式,若有#则表示结束输入, 只支持10以内的运算:");
200     scanf("%s[^\n]", line);
201     while(*c){
202         if(IsOPTR(*c, OP, sizeof(OP))<0){
203             Push(&OPND, *c);
204             c+=1;
205         }else{
206             GetTop(&OPTR, &e);
207             switch(Precede(e, *c)){
208                 case '<':
209                     Push(&OPTR, *c);
210                     c+=1;
211                     break;
212                 case '=':
213                     Pop(&OPTR, &e);
214                     c+=1;
215                     break;
216                 case '>':
217                     Pop(&OPTR, &theta);
218                     Pop(&OPND, &b);
219                     Pop(&OPND, &a);
220                     Push(&OPND, Operate(a, theta, b));
221                     break;
222                 default:
223                     break;
224             }
225         }
226     }
227     GetTop(&OPND, &e);
228     printf("结果 %s = %c
", line, e);
229     return 0;
230 }
231 
232 int main(int argc, char *argv[])
233 {
234     printf("e.g.1: 任意一个十进制数转换成八进制树.
");
235     conversion();
236 
237     printf("e.g.2: 检验括号是否匹配.
");
238     bracketMatch();
239     bracketMatch();
240 
241     printf("e.g.3: 行编辑程序.
");
242     lineEdit();
243 
244     printf("e.g.4: 表达式求值.
");
245     EvaluateExpression();
246 
247     return 0;
248 }
249 
250 static int InitStack(SqStack *S)
251 {
252     if((S->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType))) == NULL){
253         printf("failed malloc when initSTack!
");
254         return -1;
255     }
256     S->top = S->base;
257     S->stacksize = STACK_INIT_SIZE;
258     return 0;
259 }
260 
261 static int GetTop(SqStack *S, SElemType *e)
262 {
263     if(S->top == S->base){
264         return -1;
265     }
266     (*e) = *(S->top-1);
267     return 0;
268 }
269 
270 static int Push(SqStack *S, SElemType e)
271 {
272     if((S->top - S->base) >= S->stacksize){
273         if((S->base=(SElemType*)realloc(S->base, (S->stacksize+STACKINVREMENT)*sizeof(SElemType))) == NULL){
274             printf("failed reamalloc when Push!
");
275             return -1;
276         }
277         S->top = S->base+S->stacksize;
278         S->stacksize += STACKINVREMENT;
279     }
280     *(S->top++) = e;
281     return 0;
282 }
283 
284 static int Pop(SqStack *S, SElemType *e)
285 {
286     if(S->top == S->base){
287         return -1;
288     }
289     (*e) = *(--S->top);
290     return 0;
291 }
292 
293 static int StackTraversie(SqStack S)
294 {
295     SElemType *p = S.base;
296     printf("base is 0x%x, top is 0x%x
", S.base, S.top);
297     while(p)
298     {
299         if(p == S.top){
300             break;
301         }
302         printf("0x%x, %c
", p, *p);
303         p++;
304     }
305     return 0;
306 }
307 
308 static int StackEmpty(SqStack S)
309 {
310     if(S.top == S.base){
311         return 0;
312     }else{
313         return -1;
314     }
315 }
316 
317 static int ClearStack(SqStack *S)
318 {
319     if(S==NULL){
320         return -1;
321     }
322     memset(S->base, 0, S->stacksize);
323     S->top = S->base;
324     return 0;
325 }
326 
327 static int DestoryStack(SqStack *S)
328 {
329     if(S == NULL){
330         return -1;
331     }
332     if(S->base){
333         free(S->base);
334         S->base = NULL;
335         S->top = NULL;
336         S->stacksize = 0;
337     }
338     return 0;
339 }

栈的应用1-2-3-4

  1 //
  2 // Created by lady on 19-3-27.
  3 //
  4 
  5 
  6 #include <stdlib.h>
  7 #include <stdio.h>
  8 #include <string.h>
  9 
 10 #define YES 1
 11 #define NO  0
 12 #define MAX_SIZE 10
 13 typedef struct position{
 14     int Xaxis; //横坐标
 15     int Yaxis; //纵坐标
 16 }position;
 17 typedef struct brick{
 18     int type;   //yes: 表示通过;  no: 表示障碍物或墙
 19     int visit;  //no: 表示未曾到过;     yes: 表示已经来过
 20 }brick;
 21 
 22 typedef struct matrix{
 23     int w;  //宽度
 24     int h;  //高度
 25     brick wall[MAX_SIZE][MAX_SIZE];
 26     position in;  // 入口
 27     position out; // 出口
 28 }matrix;
 29 
 30 
 31 /////////////////////////////
 32 #define STACK_INIT_SIZE 100  //栈的初始大小
 33 #define STACK_INVREMENT 10   //栈的增量大小
 34 typedef struct SElemType{
 35     int ord; //序号
 36     position seat; //位置坐标
 37     int di; //方向
 38 }SElemType;
 39 typedef struct {
 40     SElemType *base;
 41     SElemType *top;
 42     int stacksize;
 43 }SqStack;
 44 static int InitStack(SqStack *S); //栈的初始化
 45 static int Push(SqStack *S, SElemType e); //入栈
 46 static int Pop(SqStack *S, SElemType *e); //出栈
 47 static int StackEmpty(SqStack S); //判断栈是否为空
 48 /////////////////////////////
 49 
 50 //创建一个迷宫矩阵
 51 int create_matrix(matrix *array)
 52 {
 53     int i = 0;
 54     int j = 0;
 55     memset(array->wall, 0, sizeof(array->wall));
 56 
 57     array->w = 10;
 58     array->h = 10;
 59 
 60     brick b;
 61     b.type = YES;
 62     b.visit = NO;
 63     array->wall[1][1] = array->wall[1][2] = array->wall[1][4] = array->wall[1][5] = array->wall[1][6] = array->wall[1][8] = b;
 64     array->wall[2][1] = array->wall[2][2] = array->wall[2][4] = array->wall[2][5] = array->wall[2][6] = array->wall[2][8] = b;
 65     array->wall[3][1] = array->wall[3][2] = array->wall[3][3] = array->wall[3][4] = array->wall[3][7] = array->wall[2][8] = b;
 66     array->wall[4][1] = array->wall[4][5] = array->wall[4][6] = array->wall[4][7] = array->wall[4][8] = b;
 67     array->wall[5][1] = array->wall[5][2] = array->wall[5][3] = array->wall[5][5] = array->wall[5][6] = array->wall[5][7] = array->wall[5][8] = b;
 68     array->wall[6][1] = array->wall[6][3] = array->wall[6][4] = array->wall[6][5] = array->wall[6][7] = array->wall[6][8] = b;
 69     array->wall[7][1] = array->wall[7][5] = array->wall[7][8] = b;
 70     array->wall[8][2] = array->wall[8][3] = array->wall[8][4] = array->wall[8][5] = array->wall[8][6] = array->wall[8][7] = array->wall[8][8] = b;
 71     array->in.Xaxis = 1;
 72     array->in.Yaxis = 1;
 73     array->out.Xaxis = 8;
 74     array->out.Yaxis = 8;
 75     return 0;
 76 }
 77 
 78 //打印迷宫矩阵，红色表示墙或者障碍物，绿色表示通道，蓝色表示迷宫中从入口到出口的一条路径
 79 void print_matrix(matrix *array)
 80 {
 81     int i = 0;
 82     int j = 0;
 83     printf("%c	", ' ');
 84     for(i=0; i<array->w; i++){
 85         printf("%d	", i);
 86     }
 87     printf("
");
 88     for(i=0; i<array->h; i++){
 89         printf("%d	", i);
 90         for(j=0; j<array->w; j++){
 91             if(array->wall[i][j].visit){//蓝色
 92                 printf("33[1;30;44m%d	33[0m", array->wall[i][j].visit);
 93             }else if(array->wall[i][j].type == YES){//绿色
 94                 printf("33[1;30;42m%d	33[0m", array->wall[i][j].type);
 95             }else{//红色
 96                 printf("33[1;30;41m%d	33[0m", array->wall[i][j].type);
 97             }
 98         }
 99         printf("
");
100     }
101 }
102 
103 //判断迷宫array中的位置pos是否可以通过，即是通道还是障碍物
104 static int Pass(position pos, matrix *array)
105 {
106     int x = pos.Xaxis;
107     int y = pos.Yaxis;
108     int type = array->wall[x][y].type;
109     int visit = array->wall[x][y].visit;
110     if( type== YES ){
111         if(visit == NO){
112             return 1;
113         }
114     }
115     return 0;
116 }
117 
118 //在迷宫array的位置pos上留下来过的痕迹
119 static int FootPrint(position pos, matrix *array)
120 {
121     int x = pos.Xaxis;
122     int y = pos.Yaxis;
123     array->wall[x][y].visit = YES;
124     return 0;
125 }
126 
127 //在迷宫array的位置pos上留下来过的痕迹
128 static int MarkPrint(position pos, matrix *array)
129 {
130     int x = pos.Xaxis;
131     int y = pos.Yaxis;
132     array->wall[x][y].visit = YES;
133     return 0;
134 }
135 
136 //返回位置pos的下一个探测的"通道"
137 static position NextPos(position pos, int direct)
138 {
139     position p;
140     if(direct == 1){
141         p.Xaxis = pos.Xaxis;
142         p.Yaxis = pos.Yaxis-1;
143     }
144     if(direct == 2){
145         p.Xaxis = pos.Xaxis + 1;
146         p.Yaxis = pos.Yaxis;
147     }
148     if(direct == 3){
149         p.Xaxis = pos.Xaxis;
150         p.Yaxis = pos.Yaxis + 1;
151     }
152     if(direct == 4){
153         p.Xaxis = pos.Xaxis - 1;
154         p.Yaxis = pos.Yaxis;
155     }
156     return p;
157 }
158 
159 //寻找迷宫array中从入口到出口的一条路径
160 static int Find_Path(matrix *array)
161 {
162     SqStack S;
163     position curpos = array->in; //设定当前位置
164     position end = array->out;
165     SElemType e;
166     int curstep = 1; //探索第一步
167     int flag = 0;
168     int x, y;
169     int i, j;
170     InitStack(&S); //初始化栈
171 
172     do{
173         if(Pass(curpos, array)){//当前位置可以通过，即使未来过的通道
174             FootPrint(curpos, array);//留下到过的足迹
175             e.ord = curstep;
176             e.seat = curpos;
177             e.di = 1;
178             Push(&S, e); //加入路径
179             if((curpos.Xaxis == end.Xaxis) && (curpos.Yaxis == end.Yaxis)){//到达终点
180                 flag = 1;
181                 break;
182             }
183             curstep += 1;//探索下一步
184         }else{//当前位置不能通过
185             if(StackEmpty(S)<0){
186                 Pop(&S, &e);
187                 while((e.di == 4) && (StackEmpty(S) < 0)){
188                     MarkPrint(e.seat, array);//留下不能通过的足迹
189                     Pop(&S, &e);
190                 }
191                 if(e.di < 4){
192                     e.di += 1;//换下一个方向探索
193                     Push(&S, e);
194                     curpos = NextPos(e.seat, e.di);//设定当前位置是该块新方向上的相邻块
195                 }
196             }
197         }
198     }while(StackEmpty(S)<0);
199 
200     //清空迷宫中的块的visit标记
201     for(i=0; i<array->w; i++){
202         for(j=0; j<array->h; j++){
203             array->wall[i][j].visit = NO;
204         }
205     }
206 
207     //foreach stack
208     if(flag){//有入口到出口的路径
209         SElemType *p = S.base;
210         while(p){
211             if(p==S.top){
212                 break;
213             }
214             x = p->seat.Xaxis;
215             y = p->seat.Yaxis;
216             //将迷宫中的块的visit标记来表示路径上的序号
217             array->wall[x][y].visit = p->ord;
218             p += 1;
219         }
220         return 0;
221     }else{
222         return -1;
223     }
224 }
225 
226 int main(int argc, char *argv[])
227 {
228     matrix array;
229     if(create_matrix(&array) < 0){
230         return -1;
231     }
232     Find_Path(&array);
233     print_matrix(&array);
234     return 0;
235 }
236 
237 
238 
239 /////////////////////////////
240 static int InitStack(SqStack *S)
241 {
242     if((S->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType))) == NULL){
243         return -1;
244     }
245     S->top = S->base;
246     S->stacksize = STACK_INIT_SIZE;
247     return 0;
248 }
249 
250 static int Push(SqStack *S, SElemType e)
251 {
252     if((S->top - S->base) >= S->stacksize){
253         if((S->base=(SElemType*)realloc(S->base, (S->stacksize+STACK_INVREMENT)*sizeof(SElemType))) == NULL){
254             printf("failed reamalloc when Push!
");
255             return -1;
256         }
257         S->top = S->base+S->stacksize;
258         S->stacksize += STACK_INVREMENT;
259     }
260     *(S->top++) = e;
261     return 0;
262 }
263 
264 static int Pop(SqStack *S, SElemType *e)
265 {
266     if(S->top == S->base){
267         return -1;
268     }
269     (*e) = *(--S->top);
270     return 0;
271 }
272 static int StackEmpty(SqStack S)
273 {
274     if(S.top == S.base){
275         return 0;
276     }else{
277         return -1;
278     }
279 }
280 /////////////////////////////

e.g.5 迷宫求解

代码运行

 1 /home/lady/CLionProjects/untitled/cmake-build-debug/untitled
 2 e.g.1: 任意一个十进制数转换成八进制树.
 3 请输入一个十进制数:123
 4 该数的八进制数为：173
 5 e.g.2: 检验括号是否匹配.
 6 输入待检验的字符串:[([][])]
 7 [([][])] 是匹配的!
 8 输入待检验的字符串:(()]
 9 (()] 是不匹配的!
10 e.g.3: 行编辑程序.
11 输入字符串(其中#表示上一个字符无效，@表示此此行该字符前的所有字符无效, end表示结束):whli##ilr#e(s#*s)
12 输出字符:while(*s)
13 输入字符串(其中#表示上一个字符无效，@表示此此行该字符前的所有字符无效, end表示结束):outchar@putchar(*s=#++)
14 输出字符:putchar(*s++)
15 输入字符串(其中#表示上一个字符无效，@表示此此行该字符前的所有字符无效, end表示结束):end
16 e.g.4: 表达式求值.
17 输入仅含有运算符+-*/()的表达式,若有#则表示结束输入, 只支持10以内的运算:3*(7-5)#
18 结果 3*(7-5)# = 6
19 
20 Process finished with exit code 0