现在的位置: 首页 > 综合 > 正文

栈的简单应用 栈的简单应用（数制转换、括号匹配检验、行编辑、迷宫求解）栈的应用——表达式求值

2017年09月30日 ⁄ 综合 ⁄ 共 14306字 ⁄ 字号 小 中 大 ⁄ 评论关闭

栈的简单应用（数制转换、括号匹配检验、行编辑、迷宫求解）

2010-03-27 11:52 660人阅读 评论(0) 收藏 举报

栈的一些简单应用：
（1）数制转换：

Code:
  1. #include <stdio.h>   
  2. #include "stack.h"   
  3.   
  4. void conversion(int num, int base)
      
  5. {
      
  6.     struct stack *s = init_stack();
      
  7.     while (num) {
      
  8.         push(s, num % base);
      
  9.         num /= base;
      
  10.     }
      
  11.     while(!stack_empty(s)) {
      
  12.         printf("%d", top(s));
      
  13.         pop(s);
      
  14.     }
      
  15.     destory_stack(s);
      
  16. }
      
  17. int main()
      
  18. {
      
  19.     int num, base;
      
  20.     scanf("%d %d", &num, &base);
      
  21.     conversion(num, base);
      
  22.     return 0;
      
  23. }  

（2）括号匹配检验：

Code:
  1. #include <stdio.h>   
  2. #include "stack.h"   
  3.   
  4. void match(char *str)
      
  5. {
      
  6.     struct stack *s = init_stack();
      
  7.     char ch, *p;
      
  8.     bool flag = true;
      
  9.     for (p = str; *p != NULL && flag; p++) {
      
  10.         switch(*p) {
      
  11.         case '(':
      
  12.         case '[':
      
  13.             push(s, *p);
      
  14.             break;
      
  15.         case ')':
      
  16.             if ((ch = top(s)) == '(')
      
  17.                 pop(s);
      
  18.             else  
  19.                 flag = false;
      
  20.             break;
      
  21.         case ']':
      
  22.             if ((ch = top(s)) == '[')
      
  23.                 pop(s);
      
  24.             else  
  25.                 flag = false;
      
  26.             break;
      
  27.         default:
      
  28.             break;
      
  29.         }
      
  30.     }
      
  31.     if (stack_empty(s))
      
  32.         printf("brackets match right!/n");
      
  33.     else  
  34.         printf("brackets not match!/n");
      
  35.     destory_stack(s);
      
  36. }
      
  37.   
  38. int main()
      
  39. {
      
  40.     char s[20] = "[3+2)*5]*(2+5)";
      
  41.     match(s);
      
  42.     return 0;
      
  43. }  

（3）行编辑：用户输入#表示前一个字符无效，输入一个@表示当前行中@前的字符都无效

Code:
  1. #include <stdio.h>   
  2. #include "stack.h"   
  3. #define MAXVAL 100   
  4.   
  5. void lineedit(int *count, char num[])
      
  6. {
      
  7.     struct stack *s = init_stack();
      
  8.     *count = 0;
      
  9.     char tmp[MAXVAL], ch;
      
  10.   
  11.     ch = getchar();
      
  12.     while (ch != EOF) {
      
  13.         while (ch != EOF && ch != '/n') {
      
  14.             switch (ch) {
      
  15.             case '#':
      
  16.                 pop(s);
      
  17.                 break;
      
  18.             case '@':
      
  19.                 clear_stack(s);
      
  20.                 break;
      
  21.             default:
      
  22.                 push(s, ch);
      
  23.                 break;
      
  24.             }
      
  25.             ch = getchar();
      
  26.         }
      
  27.         
      
  28.         int i, j;
      
  29.         bool empty;
      
  30.         
      
  31.         i = 0;
      
  32.         if (ch != EOF) {/*put the character '/n' in tmp array*/  
  33.             tmp[i++] = ch;
      
  34.             ch = getchar();
      
  35.         }
      
  36.         /*also put characters of every line in tmp array*/  
  37.         for (; !(empty = stack_empty(s)); i++) {
      
  38.             tmp[i] = top(s);
      
  39.             pop(s);
      
  40.         }       
      
  41.         for(j = i - 1; j >= 0; j--, (*count)++)
      
  42.             num[*count] = tmp[j];
      
  43.     }
      
  44.     destory_stack(s);
      
  45. }
      
  46.   
  47. int main()
      
  48. {
      
  49.     char num[MAXVAL];
      
  50.     int count, i;
      
  51.     
      
  52.     lineedit(&count, num);
      
  53.     for (i = 0; i < count; i++)
      
  54.         putchar(num[i]);
      
  55.     return 0;
      
  56. }  

（4）迷宫求解

思路：
do{
    若 当前位置可通，// 可通只未曾走过的通道块。
    则 {
       将当前位置插入栈顶；//纳入路径
       若该位置是出口位置,则结束；//求得的路径放在栈中
       否则切换当前位置的东邻块（从东开始，顺时针方向）为新的当前位置；
    }
    否则，
        若 栈不空但栈顶位置的四周均不可通，
        则 {
           删去栈顶位置；
           若栈不空，则重新测试新的栈顶位置，
           直到找到一个可通的的相邻块或出栈至栈空；
         }
        若 栈不空且栈顶位置尚有其他方向未经探索，
        则 设定新的当前位置为顺时针方向旋转找到的栈顶位置的下一块相邻块；
}
数据结构：
这里用的栈的数据结构：

Code:
  1. /*stack.h*/  
  2. #ifndef _STACK_H   
  3. #define _STACK_H   
  4. #define Type struct stack_elem*   
  5. #define MAXVAL 100/*the max depth of stack*/   
  6.   
  7. #ifdef _MSC_VER   
  8.   
  9. #define bool int   
  10. #define true 1   
  11. #define false 0   
  12.   
  13. #else   
  14.   
  15. #include <stdbool.h>   
  16. #include <stdint.h>   
  17.   
  18. #endif   
  19.   
  20. struct stack_elem;
      
  21. struct stack;
      
  22.   
  23. struct stack *init_stack();
      
  24. void destory_stack(struct stack *s);
      
  25.   
  26. void push(struct stack *s, Type data);
      
  27. void pop(struct stack *s);
      
  28. Type top(struct stack *s);
      
  29.   
  30. int stack_size(struct stack *s);
      
  31. bool stack_empty(struct stack *s);
      
  32.   
  33. void clear_stack(struct stack *s);
      
  34.   
  35. #endif  
Code:
  1. /*stack.c*/  
  2. #include <stdio.h>   
  3. #include <stdlib.h>   
  4. #include <assert.h>   
  5. #include "stack.h"   
  6.   
  7. struct stack {
      
  8.     int sp;/*the next free pos*/  
  9.     Type val[MAXVAL];
      
  10. };
      
  11.   
  12. struct stack *init_stack() 
      
  13. {
      
  14.     struct stack *s = (struct stack*)malloc(sizeof(struct stack));
      
  15.     if (s != NULL)
      
  16.         s->sp = 0;
      
  17.     return s;
      
  18. }
      
  19.   
  20. void destory_stack(struct stack *s)
      
  21. {
      
  22.     assert(s != NULL);
      
  23.     clear_stack(s);
      
  24.     free(s);
      
  25. }
      
  26.   
  27. void push(struct stack *s, Type data)
      
  28. {
      
  29.     assert(s != NULL);
      
  30.     if (s->sp < MAXVAL) 
      
  31.         s->val[s->sp++] = data;
      
  32.     else 
      
  33.         printf("error: stack full, can't push %p/n", data);
      
  34. }
      
  35.   
  36. void pop(struct stack *s)
      
  37. {
      
  38.     assert(s != NULL);
      
  39.     if (s->sp > 0) {
      
  40.         free(s->val[--s->sp]);
      
  41.      } else  
  42.         printf("error: stack empty!/n");
      
  43. }
      
  44.   
  45. Type top(struct stack *s)
      
  46. {
      
  47.     assert(s != NULL);
      
  48.     if (s->sp > 0)
      
  49.         return s->val[s->sp - 1];
      
  50.     else {
      
  51.         printf("error: stack empty!/n");
      
  52.         return 0;       
      
  53.     }
      
  54. }
      
  55.   
  56. void clear_stack(struct stack *s)
      
  57. {
      
  58.     assert(s != NULL);
      
  59.     while (! stack_empty(s))
      
  60.         pop (s);
      
  61. }
      
  62.   
  63. bool stack_empty(struct stack *s)
      
  64. {
      
  65.     assert(s != NULL);
      
  66.     if (s->sp > 0)
      
  67.         return false;
      
  68.     else  
  69.         return true;
      
  70. }
      
  71.   
  72. int stack_size(struct stack *s)
      
  73. {
      
  74.     if (s == NULL)
      
  75.         return 0;
      
  76.     else  
  77.         return s->sp;
      
  78. }
      

采用了指针数组，其中的指针指向了struct stack_elem结构体
其他数据结构：

Code:
  1. struct stack_elem {
      
  2.     int ord;/*the order of pass object in the way*/  
  3.     struct pos seat;/*the  coordinate of pass object */  
  4.     int di;/*the direction: east--1, south--2, west--3, north--4*/  
  5. };  

主函数：

Code:
  1. #include <stdio.h>   
  2. #include <stdlib.h>   
  3. #include "stack.h"   
  4. #define MAX_M 10   
  5.   
  6. /*record the pass object status: pass--0, block--1, walk--2, back--3*/  
  7. int status[MAX_M][MAX_M];
      
  8.   
  9. struct pos {
      
  10.     int x;
      
  11.     int y;
      
  12. };
      
  13.   
  14. struct stack_elem {
      
  15.     int ord;/*the order of pass object in the way*/  
  16.     struct pos seat;/*the  coordinate of pass object */  
  17.     int di;/*the direction: east--1, south--2, west--3, north--4*/  
  18. };
      
  19.   
  20. void init_status(char maze[][MAX_M])
      
  21. {
      
  22.     int i, j;
      
  23.     
      
  24.     for (i = 0; i < MAX_M; i++) {
      
  25.         for (j = 0; j < MAX_M; j++) {
      
  26.             if (maze[i][j] == 002)
      
  27.                 status[i][j] = 1;
      
  28.             else  
  29.                 status[i][j] = 0;
      
  30.         }
      
  31.     }
      
  32. }
      
  33.   
  34. void print_maze(char maze[][MAX_M])
      
  35. {
      
  36.     int i, j;
      
  37.     for (i = 0; i < MAX_M; i++) {
      
  38.         for (j = 0; j < MAX_M; j++) {
      
  39.             printf("%c ", maze[i][j]);
      
  40.         }
      
  41.         printf("/n");
      
  42.     }
      
  43. }
      
  44.   
  45. void print_status(int status[][MAX_M])
      
  46. {
      
  47.     int i, j;
      
  48.     for (i = 0; i < MAX_M; i++) {
      
  49.         for (j = 0; j < MAX_M; j++) {
      
  50.             printf("%d ", status[i][j]);
      
  51.         }
      
  52.         printf("/n");
      
  53.     }
      
  54. }
      
  55.   
  56. bool is_pass(struct pos *ps)
      
  57. {
      
  58.     if (status[ps->x][ps->y] == 0)
      
  59.         return true;
      
  60.     else  
  61.         return false;
      
  62. }
      
  63.   
  64. void foot_print(struct pos *ps)
      
  65. {
      
  66.     status[ps->x][ps->y] = 2;
      
  67. }
      
  68.   
  69. void make_print(struct pos ps)
      
  70. {
      
  71.     status[ps.x][ps.y] = 3;
      
  72. }   
      
  73.   
  74. void next_pos(struct stack_elem *p, struct pos *p_curpos)
      
  75. {
      
  76.     struct pos temp;
      
  77.     temp.x = p->seat.x;
      
  78.     temp.y = p->seat.y;
      
  79.     
      
  80.     switch (p->di) {
      
  81.     case 1:
      
  82.         temp.y++;
      
  83.         break;
      
  84.     case 2:
      
  85.         temp.x++;
      
  86.         break;
      
  87.     case 3:
      
  88.         temp.y--;
      
  89.         break;
      
  90.     case 4:
      
  91.         temp.x--;
      
  92.         break;
      
  93.     default:
      
  94.         break;
      
  95.     }
      
  96.     
      
  97.     p_curpos->x = temp.x;
      
  98.     p_curpos->y = temp.y;
      
  99. }
      
  100.     
      
  101. struct stack *maze_path(char maze[][MAX_M], struct pos *start, struct pos *end)
      
  102. {
      
  103.     struct stack *s = init_stack();
      
  104.     struct pos curpos;
      
  105.     struct pos *p_curpos = &curpos;
      
  106.     p_curpos->x = start->x;
      
  107.     p_curpos->y = start->y;
      
  108.     int curstep = 1, direction = 1;
      
  109.     
      
  110.     do {
      
  111.         if (is_pass(p_curpos)) {/*the current pos is passable*/  
  112.             foot_print(p_curpos);
      
  113.             
      
  114.             struct stack_elem *p = (struct stack_elem *)malloc(sizeof(struct stack_elem));
      
  115.             p->ord = curstep;
      
  116.             p->seat.x = p_curpos->x;
      
  117.             p->seat.y = p_curpos->y;
      
  118.             p->di = direction;
      
  119.             
      
  120.             push(s, p);
      
  121.             
      
  122.             if (p_curpos->x == end->x && p_curpos->y == end->y)/*find the exit*/  
  123.                 return s;
      
  124.             
      
  125.             next_pos(p, p_curpos);
      
  126.             curstep++;
      
  127.         } else {/*the current pos is not passable*/  
  128.             if (! stack_empty(s)) {
      
  129.                 struct stack_elem *tip = top(s);
      
  130.                 while (tip->di == 4 && !stack_empty(s)) {
      
  131.                     make_print(tip->seat);
      
  132.                     pop(s);
      
  133.                     tip = top(s);
      
  134.                 }
      
  135.                 if (tip->di < 4) {
      
  136.                     tip->di++;
      
  137.                     next_pos(tip, p_curpos);
      
  138.                 }
      
  139.             }
      
  140.             
      
  141.         }
      
  142.     } while (! stack_empty(s));
      
  143.     return s;
      
  144. }
      
  145.   
  146. void mark_maze(char maze[][MAX_M], struct stack *s)
      
  147. {
      
  148.     struct stack_elem *tip;
      
  149.     char ch = 0;
      
  150.     
      
  151.     while (! stack_empty(s)) {
      
  152.         tip = top(s);
      
  153.         switch (tip->di) {
      
  154.         case 1:
      
  155.             ch = 26;
      
  156.             break;
      
  157.         case 2:
      
  158.             ch = 25;
      
  159.             break;
      
  160.         case 3:
      
  161.             ch = 27;
      
  162.             break;
      
  163.         case 4:
      
  164.             ch = 24;
      
  165.             break;
      
  166.         default:
      
  167.             break;
      
  168.         }
      
  169.         maze[tip->seat.x][tip->seat.y] = ch;
      
  170.         pop(s);
      
  171.     }
      
  172. }
      
  173.   
  174. int main()
      
  175. {
      
  176.     char maze[MAX_M][MAX_M] = {
      
  177.         2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
      
  178.         2, 0, 0, 2, 0, 0, 0, 2, 0, 2,
      
  179.         2, 0, 0, 2, 0, 0, 0, 2, 0, 2,
      
  180.         2, 0, 0, 0, 0, 2, 2, 0, 0, 2,
      
  181.         2, 0, 2, 2, 2, 0, 0, 0, 0, 2,
      
  182.         2, 0, 0, 0, 2, 0, 0, 0, 0, 2,
      
  183.         2, 0, 2, 0, 0, 0, 2, 0, 0, 2,
      
  184.         2, 0, 2, 2, 2, 0, 2, 2, 0, 2,
      
  185.         2, 2, 0, 0, 0, 0, 0, 0, 0, 2,
      
  186.         2, 2, 2, 2, 2, 2, 2, 2, 2, 2,       
      
  187.     };  
      
  188.     printf("init status:/nmaze:/n");
      
  189.     print_maze(maze);
      
  190.     printf("/n");
      
  191.     
      
  192.     init_status(maze);  
      
  193.     printf("status array:/n");
      
  194.     print_status(status);
      
  195.     
      
  196.     struct pos start, end;
      
  197.     start.x = start.y = 1;
      
  198.     end.x = end.y = 8;
      
  199.     
      
  200.     struct pos *p_start = &start, *p_end = &end;
      
  201.     struct stack *pass_way = maze_path(maze, p_start, p_end);
      
  202.     
      
  203.     printf("/nfinal status:/nstatus array:/n");
      
  204.     print_status(status);
      
  205.     
      
  206.     mark_maze(maze, pass_way);
      
  207.     printf("/n");
      
  208.     printf("maze:/n");
      
  209.     print_maze(maze);
      
  210.     
      
  211.     destory_stack(pass_way);
      
  212.     return 0;
      
  213. }
      

经purify检测，无内存泄露。运行截图：
 

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞