• 栈的运行算法

    一，顺序栈的静态分配

    二，顺序栈的动态分配

    2.1结构体

    1. typedef struct Sqstack{
    2.     int *base;
    3.     int *top;
    4.     int stacksize;
    5. }Sqstack;

    2.2初始化

    1.  
    2. void InitStack(Sqstack *s){
    3.     (*s).base=(int *)malloc(initsize*sizeof(int));
    4.     if(!(*s).base)exit(0);
    5.     (*s).top=(*s).base;
    6.     (*s).stacksize=initsize;
    7. }

    2.3入栈

    1. void Push(Sqstack *s,int e){
    2.     if((*s).top-(*s).base >= (*s).stacksize){
    3.         (*s).base=(int*)realloc((*s).base,((*s).stacksize+incresize)*sizeof(int));
    4.         if(!(*s).base)exit(0);
    5.         (*s).top=(*s).base+(*s).stacksize;
    6.         (*s).stacksize+=incresize;
    7.     }
    8.     *((*s).top)=e;
    9.     (*s).top++;
    10. }

    2.4出栈

    1.  
    2. void Pop(Sqstack *s,int *e){
    3.     if((*s).top==(*s).base) exit(0);
    4.     (*s).top--;
    5.     *e=*((*s).top);
    6. }

    2.5销毁栈

    1.  
    2. void Destroystack(Sqstack *s){
    3.     if(s!=NULL){
    4.         free((*s).base);
    5.         (*s).base=NULL; (*s).top=NULL;
    6.         (*s).stacksize=0;
    7.     }
    8. }
    9.

    2.6栈判空

    1.  
    2. int StackEmpty(Sqstack s){
    3.     return (s.top==s.base);
    4. }

    2.7求栈长

    1.  
    2. int StackLength(Sqstack s){
    3.     return s.top-s.base;
    4. }

      2.8 主函数

    1. #include
    2. #include
    3. #define initsize 5
    4. #define incresize 5
    5.  
    6. int main(){
    7.     Sqstack s;
    8.     InitStack(&s);
    9.     int e,p,x;
    10.     for(int j=0;j
    11.         scanf("%d",&e);
    12.         Push(&s,e);
    13.     }
    14.     GetTop(s,&p);
    15.     printf("栈顶元素是%d ",p);
    16.     if(StackEmpty(s)) printf("\n非空！");
    17.     else ("\n empty!");
    18.     int length=StackLength(s);
    19.     printf("\n 栈长为%d",length);
    20.     Pop(&s,&x);
    21.     printf("\n 出栈元素是 %d",x);
    22.     Destroystack(&s);
    23.     return 0;
    24. }

    三，栈链

    1. #include
    2. #include
    3.  
    4. typedef struct stacknode{
    5.     int data;
    6.     struct stacknode *next;
    7. }stackNode,*Linkstack;
    8.  
    9. void Initstack(Linkstack *s){
    10.     *s=(Linkstack)malloc(sizeof(stackNode));
    11.     (*s)->next=NULL;
    12.     
    13. }
    14. void Push(Linkstack s,int x){
    15.     Linkstack p=(Linkstack)malloc(sizeof(stackNode));
    16.     if(!p)exit(0);
    17.     p->data=x;
    18.     p->next=s->next;
    19.     s->next=p;
    20.     
    21. }
    22. void Gettop(Linkstack s,int *e){
    23.     if(s->next==NULL)exit(0);
    24.     *e=s->next->data;
    25. }
    26. int Empty(Linkstack s){
    27.     return (s->next==NULL);
    28. }
    29.  
    30. void Pop(Linkstack s,int *e){
    31.     if(s->next==NULL){
    32.         printf("空！");exit(0);
    33.     }
    34.     stackNode *p=s->next;
    35.     e=p->data;
    36.     s->next=p->next;
    37.     free(p);
    38. }
    39. void Destroystack(Linkstack s){
    40.     Linkstack p=s->next,q;
    41.     while(p!=NULL){
    42.         q=p->next;
    43.         free(p);
    44.         p=q;
    45.     }
    46.     free(s);
    47. }
    48. int main(){
    49.     Linkstack s;
    50.     Initstack(&s);
    51.     
    52.     int n,x;scanf("%d",&n);
    53.     for(int i=0;i
    54.         scanf("%d",&x);
    55.         Push(&s,x);
    56.     }
    57.     
    58.     Gettop(&s,&x);
    59.     printf("栈顶元素是 %d\n",x);
    60.     
    61.     int flag=Empty(s);
    62.     if(flag==0)printf("空！");
    63.     else printf("非空！");
    64.     
    65.     Pop(&s,&x);
    66.     printf("出栈元素是 %d",x);
    67.     
    68.     Destroystack(&s);
    69.  
    70.     return 0;
    71. }

    四，进制转换

    五，表达式求值

    六，括号的匹配问题

    七，迷宫问题

    八，中缀表达式求值

    题目描述

    编写一个算法，利用栈求解中缀算术表达式的值。运算符包括+、-、*、/、(、)和=，参加运算的数为个位数整数类型且为正数。（要求：直接针对中缀算术表达式进行计算，不能转换为后缀或前缀表达式再进行计算，只考虑二元运算即可。）

    输入

    输入一个需要计算的算术表达式，例如：2+2=。

    输出

    输出为表达式的运算结果。

    样例输入 Copy
    1+1=
    样例输出 Copy
    2

     

    1. #include 
    2. #include 
    3.  
    4. typedef struct Node {
    5.     int data;
    6.     struct Node *next;
    7. } Node;
    8.  
    9. typedef struct {
    10.     Node *top;
    11. } Stack;
    12.  
    13. int is_operator(char ch) {
    14.     return (ch == '+' || ch == '-' || ch == '*' || ch == '/');
    15. }
    16.  
    17. int priority(char op) {
    18.     switch (op) {
    19.         case '+':
    20.         case '-':
    21.             return 1;
    22.         case '*':
    23.         case '/':
    24.             return 2;
    25.         default:
    26.             return 0;
    27.     }
    28. }
    29.  
    30. int calculate(int a, char op, int b) {
    31.     switch (op) {
    32.         case '+':
    33.             return a + b;
    34.         case '-':
    35.             return a - b;
    36.         case '*':
    37.             return a * b;
    38.         case '/':
    39.             return a / b;
    40.         default:
    41.             exit(1);
    42.     }
    43. }
    44.  
    45. Stack *create_stack() {   // 创建空栈
    46.     Stack *stack = (Stack *)malloc(sizeof(Stack));
    47.     stack->top = NULL;
    48.     return stack;
    49. }
    50.  
    51. void push(Stack *stack, int data) {   // 入栈操作
    52.     Node *node = (Node *)malloc(sizeof(Node));
    53.     node->data = data;
    54.     node->next = stack->top;
    55.     stack->top = node;
    56. }
    57.  
    58. int pop(Stack *stack) {   // 出栈操作
    59.     if (stack->top == NULL) {
    60.         return -1;   // 如果栈为空，则返回-1
    61.     }
    62.     Node *node = stack->top;
    63.     int data = node->data;
    64.     stack->top = node->next;
    65.     free(node);
    66.     return data;
    67. }
    68.  
    69. int top(Stack *stack) {   // 返回栈顶元素
    70.     if (stack->top == NULL) {
    71.         return -1;   // 如果栈为空，则返回-1
    72.     }
    73.     return stack->top->data;
    74. }
    75. int evaluate_expression(char *expression) {
    76.     Stack *s1 = create_stack();   // 操作数栈，用于存储操作数
    77.     Stack *s2 = create_stack();   // 操作符栈，用于存储操作符
    78.  
    79.     for (int i = 0; expression[i] != '='; i++) {
    80.         if (is_operator(expression[i])) {   // 如果当前字符为操作符
    81.             while (s2->top != NULL && priority(top(s2)) >= priority(expression[i])) {
    82.                 // 如果操作符栈不为空，并且栈顶操作符的优先级大于等于当前操作符的优先级
    83.                 int b = pop(s1);    // 出栈一个操作数作为运算的右操作数
    84.                 int a = pop(s1);    // 再出栈一个操作数作为运算的左操作数
    85.                 char op = pop(s2);  // 出栈一个操作符
    86.                 int result = calculate(a, op, b);   // 计算两个操作数和操作符的结果
    87.                 push(s1, result);   // 将计算结果入栈到操作数栈中
    88.             }
    89.             push(s2, expression[i]);  // 当前操作符入栈到操作符栈中
    90.         } else if (expression[i] == '(') { // 如果当前字符为左括号
    91.             push(s2, expression[i]);    // 入栈到操作符栈中
    92.         } else if (expression[i] == ')') { // 如果当前字符为右括号
    93.             while (top(s2) != '(') {    // 循环执行直到遇到左括号
    94.                 int b = pop(s1);    // 出栈一个操作数作为运算的右操作数
    95.                 int a = pop(s1);    // 再出栈一个操作数作为运算的左操作数
    96.                 char op = pop(s2);  // 出栈一个操作符
    97.                 int result = calculate(a, op, b);   // 计算两个操作数和操作符的结果
    98.                 push(s1, result);   // 将计算结果入栈到操作数栈中
    99.             }
    100.             pop(s2);    // 弹出左括号
    101.         } else {    // 如果当前字符为数字
    102.             int num = expression[i] - '0';  // 将当前字符转换成数字
    103.             while (expression[i + 1] >= '0' && expression[i + 1] <= '9') {
    104.                 // 如果下一个字符也是数字，则将其合并到一起
    105.                 num = num * 10 + expression[++i] - '0';
    106.             }
    107.             push(s1, num);  // 将数字入栈到操作数栈中
    108.         }
    109.     }
    110.  
    111.     // 处理剩余的操作符
    112.     while (s2->top != NULL) {
    113.         int b = pop(s1);    // 出栈一个操作数作为运算的右操作数
    114.         int a = pop(s1);    // 再出栈一个操作数作为运算的左操作数
    115.         char op = pop(s2);  // 出栈一个操作符
    116.         int result = calculate(a, op, b);   // 计算两个操作数和操作符的结果
    117.         push(s1, result);   // 将计算结果入栈到操作数栈中
    118.     }
    119.  
    120.     return pop(s1); // 返回最终的计算结果
    121. }
    122.  
    123.  
    124. int main() {
    125.     char expression[100];
    126.     
    127.     scanf("%s", expression);
    128.     int result = evaluate_expression(expression);
    129.     
    130.     printf("%d\n", result);
    131.     return 0;
    132. }

    wenti:

    1. #include
    2. #include
    3.  
    4.  
    5. typedef struct stacknode{
    6.     int data;
    7.     struct stacknode *next;
    8. }StackNode,*StackLink;
    9.  
    10. StackLink *Initstack(){
    11.     StackLink s;
    12.     s=(StackLink)malloc(sizeof(StackNode));
    13.     s->next=NULL;
    14.     return s;
    15. }
    16. void Push(StackLink stack,int e){
    17.     StackNode *node=(StackNode *)malloc(sizeof(StackNode));
    18.     //if(!node)exit(0);
    19.     node->data=e;
    20.     node->next=stack->next;
    21.     stack->next=node;
    22. }
    23. int Pop(StackLink stack,int *e){
    24.     if(stack->next ==NULL)return 0;
    25.     StackLink p=stack->next;
    26.     * e=p->data;
    27.     stack->next=p->next;
    28.     free(p);
    29.     return 1;
    30. }
    31. int GetTop(StackLink stack,int *e){
    32.     if(stack->next==NULL){
    33.         return -1;
    34.     }
    35.     *e=stack->next->data;
    36.     return 0;
    37. }
    38.  
    39.  
    40. int  is_operator(char x){
    41.     if(x=='+'||x=='-'||x=='*'||x=='/'){
    42.         return 1;
    43.     }
    44.     return 0;
    45. }
    46. int prio(char ope){
    47.     switch(ope){
    48.         case'+':
    49.         case'-':
    50.             return 1;
    51.         case'*':
    52.         case'/':
    53.             return 2;
    54.         default:
    55.             return 0;
    56.     }
    57. }
    58. int calculate(int a,char op,int b){
    59.     switch(op){
    60.         case'+':return a+b;
    61.         case'-':return a-b;
    62.         case'*':return a*b;
    63.         case'/':return a/b;
    64.         default:exit(0);
    65.     }
    66. }
    67.  
    68. int Get_evaluate(char exp[1000]){
    69.     StackLink s1,s2;
    70.     s1=Initstack();
    71.     s2=Initstack();
    72.     for(int i=0;exp[i]!='=';i++){
    73.         if(is_operator(exp[i])==1){//运算符
    74.             if(s2->next !=NULL && prio(s2->next)>=prio(exp[i])){
    75.                 int b;Pop(s1,&b);
    76.                 int a;Pop(s2,&a);
    77.                 char op;Pop(s1,&op);
    78.                 int result =calculate(a,op,b);
    79.                 Push(s1,result);
    80.             }
    81.         }
    82.         else if(exp[i]=='('){
    83.             Push(s2,exp[i]);
    84.         }
    85.         else if(exp[i]==')'){
    86.             while(s2->data!='('){
    87.                 int b;Pop(s1,&b);
    88.                 int a;Pop(s2,&a);
    89.                 char op;Pop(s1,&op);
    90.                 int result =calculate(a,op,b);
    91.                 Push(s1,result);
    92.             }
    93.             int a;Pop(s2,a);//a存放s2出栈数字
    94.         }
    95.         else{//数字
    96.             int num=exp[i]-'0';
    97.             while(exp[i+1]>='0'&&exp[i+1]<='9'){
    98.                 num=num*10+exp[++i]-'0';
    99.             }
    100.             Push(s1,num);
    101.         }
    102.     }
    103.     // 处理剩余的操作符
    104.     while (s2->next != NULL) {
    105.         int b;Pop(s1,&b);
    106.         int a;Pop(s2,&a);
    107.         char op;Pop(s1,&op);
    108.         int result =calculate(a,op,b);
    109.         Push(s1,result);
    110.     }
    111.  
    112.     int t;Pop(s1,&t); // 返回最终的计算结果
    113.     return t;
    114. }
    115. int main(){
    116.     char exp[1000];
    117.     scanf("%s",exp);
    118.     int result =Get_evaluate(exp);
    119.     printf("%d",result);
    120.     return 0;
    121. }

    九，双向栈的基本操作

    题目描述

    将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空；当第1号栈的栈顶指针top[1]等于m时，该栈为空。两个栈均从两端向中间增长。试编写双栈初始化，判断栈空、栈满、进栈和出栈算法的函数。函数调用次序依次为：进栈、栈满的判断、出栈、栈空的判断。

    输入

    第一行为一个整数m，表示数组V的大小，

    第二行为四个整数e0、e1、d0、d1，e0和e1分别代表压入0号栈和1号栈的整数序列E0和E1的长度（依次连续入栈，中间没有出栈的情况），d0和d1分别代表从0号栈和1号栈弹出的序列的长度（依次连续出栈，中间没有入栈的情况）。

    第三行和第四行分别表示序列E0和E1。

    输出

    第一行代表进栈操作完成时栈是否为满（出栈操作尚未执行），栈满输出1，栈不满输出0。

    第二行对应0号栈,第二行包括d0+1个整数，其中前d0个整数代表出栈序列D0，最后一个整数代表出栈操作完成时0号栈是否为空，栈空输出0，不空输出1。

    第三行对应1号栈,第三行包括d1+1个整数，其中前d1个整数代表出栈序列D1，最后一个整数代表出栈操作完成时1号栈是否为空，栈空输出0，不空输出1。整数之间用空格分隔。

    样例输入 Copy
    1. 7
    2. 3 4 2 2
    3. 1 2 3
    4. 2 3 4 5
    样例输出 Copy
    1. 1
    2. 3 2 1
    3. 5 4 1
    1. #include 
    2. #include 
    3.  
    4.  
    5.  
    6. typedef int elem;
    7.  
    8. typedef struct
    9. {
    10.     int top[2];//定义栈顶和栈底指针 int bot[2];
    11.     int  *V;            //栈数组
    12.     int m;                //栈最大可容纳元素个数
    13. }DblStack;
    14.  
    15. //初始化双栈
    16. void InitDblStack(DblStack *stack,int x)
    17. {
    18.     int *arr = (elem*)malloc(x*sizeof(elem));//申请空间
    19.     stack->V = arr;                            //将V指针指向申请的空间
    20.     stack->m = x;                    //初始化栈最大可容纳最大元素个数
    21.     stack->top[0] = -1;                        //左栈栈顶指针初始化
    22.     stack->top[1] = stack->m;                //右栈栈顶指针初始化
    23.     //stack->bot[0] = 0;                        //左栈栈底指针初始化
    24.     //stack->bot[1] = stack->m-1;                //右栈栈底指针初始化
    25.     
    26.     
    27. }
    28.  
    29. //判断总体是否为空栈
    30. int EmptyDblStack(DblStack stack)
    31. {
    32.     if(stack.top[0] == -1 && stack.top[1] == stack.m)
    33.         return 1;        //若是返回1
    34.     return 0;            //否则返回0
    35. }
    36.  
    37. //判断左栈是否为空栈
    38. int EmptyLeft(DblStack stack)
    39. {
    40.     if(stack.top[0] == -1)
    41.         return 0;        //若是返回1
    42.     return 1;            //否则返回0
    43. }
    44.  
    45. //判断右栈是否为空栈
    46. int EmptyRight(DblStack stack)
    47. {
    48.     if(stack.top[1] == stack.m )//加&& stack.top[0]==-1
    49.         return 0;        //若是返回1
    50.     return 1;            //否则返回0
    51. }
    52.  
    53. //判断是否为满栈
    54. int FullDblStack(DblStack stack)
    55. {
    56.     if(stack.top[1] - stack.top[0]==1 || stack.top[0] >= stack.m || stack.top[1] < 0 )
    57.         //三种满栈情况左右两栈中间相遇，左栈满，右栈满
    58.         return 1;//满栈返回1
    59.     return 0;//否则返回0
    60. }
    61.  
    62. int Fullleft(DblStack stack){
    63.     if(stack.top[0] >= stack.m )return 1;
    64.     else return 0;
    65. }
    66. int Fullright(DblStack stack){
    67.     if(stack.top[1] <0 )return 1;
    68.     else return 0;
    69. }
    70. //左栈进栈
    71. int pushLeft(DblStack *stack, elem e)
    72. {
    73.     if (stack->top[1] - stack->top[0] ==1)//判断是否为满栈
    74.     {
    75.         printf("栈已满不能进行进栈操作\n");
    76.         return 0;                //满栈返回0
    77.     }
    78.     stack->top[0]++;                //左栈栈顶指针加一
    79.     stack->V[stack->top[0]] = e;    //将数据元素进栈
    80.     //printf("%d ",stack->V[stack->top[0]]);
    81.     return 1;                    //完成操作返回1
    82. }
    83.  
    84. //右栈进栈
    85. int pushRight(DblStack *stack, elem e)
    86. {
    87.     if (stack->top[1] - stack->top[0] ==1)//判断是否为满栈
    88.         {
    89.             printf("栈已满，无法进行进栈操作\n");
    90.             return 0;                //满栈返回0
    91.         }
    92.     else{
    93.         stack->top[1]--;   //右栈栈顶指针加一
    94.         stack->V[stack->top[1]] = e;    //将数据元素进栈
    95.         //printf("%d ",stack->V[stack->top[1]]);
    96.         return 1;
    97.     }
    98. }
    99.  
    100. //左栈出栈
    101. elem popLeft(DblStack *stack)
    102. {
    103.     if (stack->top[0] == -1)//判断是否为空栈
    104.     {
    105.         printf("左栈已空，无法进行出栈操作\n");
    106.         return 0;                    //空栈返回0
    107.     }
    108.     elem e = stack->V[stack->top[0]];  //取出栈顶数据元素
    109.     stack->top[0]--;   //左栈栈顶元素减一
    110.    // stack->V[stack->top[0]];
    111.     return e;                        //返回原栈顶元素
    112. }
    113.  
    114. //右栈出栈
    115. elem popRight(DblStack *stack)
    116. {
    117.     if (stack->top[0] == stack->m)    //判断是否为空栈
    118.     {
    119.         printf("右栈已空，无法进行出栈操作\n");
    120.         return 0;                    //空栈返回0
    121.     }
    122.     elem e = stack->V[stack->top[1]];    //取出右栈栈顶元素
    123.     stack->top[1]++;                    //右栈栈顶指针加一
    124.     return e;                        //返回原栈顶元素
    125. }
    126.  
    127. //遍历双栈
    128. void printDblStack(DblStack stack)
    129. {
    130.     for (int i = 0; i <= stack.top[0]; i++) //输出左栈
    131.     {
    132.         printf("%d ", stack.V[i]);
    133.         
    134.     }
    135.     printf("\n");
    136.     for(int i = stack.top[1]; i < stack.m; i++)//输出右栈
    137.     {
    138.          printf("%d ", stack.V[i]);
    139.     }
    140.     printf("\n");
    141. }
    142.  
    143.  
    144. //调试
    145. int main()
    146. {
    147.     int m,e0,e1,d0,d1;
    148.     DblStack stack;
    149.     scanf("%d",&m);
    150.     InitDblStack(&stack,m); //初始化双栈
    151.     
    152.     scanf("%d %d %d %d",&e0,&e1,&d0,&d1);
    153.     for(int j=0;j//左栈进栈
    154.         int E0[e0];
    155.         scanf("%d",&E0[j]);
    156.         pushLeft(&stack, E0[j]);
    157.     }
    158.    
    159.     for(int j=0;j//右栈进栈
    160.         int E1[e1];
    161.         scanf("%d",&E1[j]);
    162.         pushRight(&stack, E1[j]);
    163.     }
    164.     
    165.    // printDblStack(stack);
    166.     printf( FullDblStack(stack) ==1?"1":"0");//判断是否为满栈
    167.     printf("\n");
    168.  
    169.     for(int j=0;j
    170.         int x=popLeft(&stack);
    171.         printf("%d ",x);
    172.     }
    173.     
    174.     int x=EmptyLeft(stack);
    175.     printf("%d",x);
    176.     printf("\n");
    177.     
    178.     for(int j=0;j
    179.         int x=popRight(&stack);
    180.         printf("%d ",x);
    181.     }
    182.     
    183.     x=EmptyRight(stack);
    184.     printf("%d",x);
    185.     
    186.     printf("\n");
    187.    // printDblStack(stack);
    188.     return 0;
    189. }

    十，括号匹配

    题目描述

    ​​​​​​​
    编写一个算法，利用栈检查一个字符数组表示的字符中的花括号、方括号和圆括号是否配对，若能够全部配对则返回1，否则返回0。

    输入

    输入需要检查的括号字符串，例如：{{([][])}()}。

    输出

    输出检查结果（全部配对则返回1，否则返回0）。

    样例输入 Copy
    {{([][])}()}
    样例输出 Copy
    1
    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #define MaxSize 100 //定义栈中元素最大个数
    6.  
    7. typedef struct{
    8.     char data[MaxSize];
    9.     int top;
    10. }SqStack;
    11.  
    12. //初始化栈
    13. void InitStack(SqStack *S){
    14.     S->top = -1;
    15. }
    16. //判断栈是否为空
    17. bool IsEmpty(SqStack S){
    18.     if(S.top == -1){
    19.         return true;
    20.     }
    21.     return false;
    22. }
    23. //新元素入栈
    24. void Push(SqStack *S,char x){
    25.     if(S->top == MaxSize-1){
    26.         printf("栈已满"); //栈已满
    27.         return;
    28.     }
    29.     S->top += 1;
    30.     S->data[S->top] = x;
    31. }
    32. //栈顶元素出栈，用x返回
    33. void Pop(SqStack *S,char *x){
    34.     if(S->top == -1){
    35.         printf("栈已满");
    36.         return;
    37.     }
    38.     *x = S->data[S->top];
    39.     S->top -= 1;
    40. }
    41. //匹配算法
    42. bool bracketCheck(char str[],int length){
    43.     SqStack S;
    44.     InitStack(&S); //初始化栈
    45.     for(int i=0;i
    46.         if(str[i]=='('||str[i]=='{'||str[i]=='['){
    47.             Push(&S,str[i]); //扫描到左括号就入栈
    48.         }else{
    49.             if(IsEmpty(S)){ //扫描到右括号，当前栈为空，即右括号单身情况
    50.                 return false; //匹配失败
    51.             }
    52.             char topElem; //用来保存弹出栈的栈顶元素
    53.             Pop(&S,&topElem); //栈顶元素出栈
    54.             if(str[i]==')'&&topElem!='('){
    55.                 return false;
    56.             }
    57.             if(str[i]=='}'&&topElem!='{'){
    58.                 return false;
    59.             }
    60.             if(str[i]==']'&&topElem!='['){
    61.                 return false;
    62.             }
    63.         }
    64.     }
    65.     return IsEmpty(S);
    66. }
    67. int main(){
    68.     char s[MaxSize];
    69.    
    70.     scanf("%s",s);
    71.     int len = strlen(s);
    72.     if(bracketCheck(s,len)){
    73.         printf("1");
    74.     }else{
    75.         printf("0");
    76.     }
    77.     return 0;
    78. }
    79.

    十一，进制转换

    题目描述

    编写一个算法，利用栈将一个非负的十进制整数分别转换为一个二进制数、一个八进制数和一个十六进制数。

    输入
    输入需要转换的十进制元素，例如：666。
    输出

    第一行输出转换后的二进制元素，例如：1010011010；

    第二行输出转换后的八进制元素，例如：1232；
    第三行输出转换后的十六进制元素，例如：29A。

    样例输入 Copy
    666
    样例输出 Copy
    1. 1010011010
    2. 1232
    3. 29A 
    1. #include 
    2. #include 
    3. //#ifndef __STACK_H
    4. //#define __STACK_H
    5.  
    6. #define MaxSize 1000
    7.  
    8. typedef int ElemType;
    9.  
    10. typedef struct {
    11.     ElemType data[MaxSize];
    12.     int top;
    13. }Sqstack;
    14. //创建一个空栈
    15. Sqstack * Stack_Creat(Sqstack * Stack)
    16. {
    17.     Stack = (Sqstack *)malloc(sizeof(Sqstack));
    18.     if(Stack == NULL)
    19.     {
    20.         printf("空间已满！\n");
    21.         return 0;
    22.     }
    23.     Stack->top = -1; //空栈
    24.     return Stack;
    25. }
    26.  
    27. //摧毁栈
    28. void Stack_Destory(Sqstack * Stack)
    29. {
    30.     free(Stack);
    31. }
    32.  
    33. //出栈
    34. ElemType Stack_Pop(Sqstack * Stack)
    35. {
    36.     ElemType e=-1;
    37.     if(Stack->top == -1)
    38.         printf("该栈为空栈，无法出栈!\n");
    39.     else
    40.     {
    41.         e = Stack->data[Stack->top];
    42.         Stack->top--;
    43.     }
    44.     return e;
    45. }
    46.  
    47. //入栈
    48. void Stack_Push(Sqstack * Stack,ElemType e)
    49. {
    50.     if(Stack->top == MaxSize - 1)
    51.     {
    52.         printf("栈已满，无法入栈!\n");
    53.     }
    54.     else
    55.     {
    56.         Stack->top++;
    57.         Stack->data[Stack->top] = e;
    58.     }
    59. }
    60.  
    61. //判断栈是否为空
    62. int Stack_Empty(Sqstack * Stack)
    63. {
    64.     return (Stack->top == -1 );
    65. }
    66.  
    67.  
    68.  
    69.  
    70.  
    71. void DTB(int num,Sqstack * Stack)
    72. {
    73.     char  num_b[33] ;  //用来存放转换出来的二进制
    74.     char * temp = num_b;
    75.     while(num)  //入栈
    76.     {
    77.         Stack_Push(Stack,num%2);
    78.         num /= 2;
    79.     }
    80.     while(!Stack_Empty(Stack))//出栈 直到栈为空
    81.     {
    82.         *temp = Stack_Pop(Stack) + '0';
    83.         temp++;
    84.     }
    85.     *temp = '\0';
    86.     printf("%s\n",num_b);
    87. }
    88.  
    89. void DTO(int num,Sqstack * Stack)
    90. {
    91.     char  num_o[12] ;  //用来存放转换出来的二进制
    92.     char * temp = num_o;
    93.     while(num)  //入栈
    94.     {
    95.         Stack_Push(Stack,num%8);
    96.         num /= 8;
    97.     }
    98.     while(!Stack_Empty(Stack))//出栈 直到栈为空
    99.     {
    100.         *temp = Stack_Pop(Stack) + '0';
    101.         temp++;
    102.     }
    103.     *temp = '\0';
    104.     printf("%s\n",num_o);
    105. }
    106.  
    107. void DTH(int num,Sqstack * Stack)
    108. {
    109.     char  num_h[12] ;  //用来存放转换出来的二进制
    110.     char * temp = num_h;
    111.     int   top_num;
    112.     while(num)  //入栈
    113.     {
    114.         Stack_Push(Stack,num%16);
    115.         num /= 16;
    116.     }
    117.     while(!Stack_Empty(Stack))//出栈 直到栈为空
    118.     {
    119.         top_num = Stack_Pop(Stack);
    120.         if(top_num>9)
    121.             *temp = top_num - 10 + 'A';
    122.         else
    123.             *temp = top_num + '0';
    124.         temp++;
    125.     }
    126.     *temp = '\0';
    127.     printf("%s\n",num_h);
    128. }
    129. int main(){
    130.     int flag=1,a,num_d;
    131.     Sqstack * Stack;
    132.     Stack = Stack_Creat(Stack);
    133.     
    134.     scanf("%d",&num_d);
    135.     if(num_d>0){
    136.         DTB(num_d,Stack);
    137.         DTO(num_d,Stack);
    138.         DTH(num_d,Stack);
    139.     }
    140.     if(num_d==0){
    141.         printf("0 \n0 \n0 \n");
    142.     }
    143.     return 0;
    144. }

    十二，入栈出栈基本操作

    题目描述

    输入一个整数序列a1,a2,a3...,an。当ai不等于-1时将ai进栈；当ai=-1时，输出栈顶元素并将其出栈。

    输入

    第一行为序列的长度n，

    第二行为n个整数，整数之间用空格分隔。

    输出
    输出若干行，每行为相应的出栈元素。当出栈异常时，输出“出栈失败”并结束数据的输出。
    样例输入 Copy
    1. 5
    2. 1 2 -1 -1 1
    3.
    样例输出 Copy
    1. 2
    2. 1
    1. #include
    2. #include
    3. //#define initsize 5
    4. #define incresize 5
    5.  
    6. typedef struct Sqstack{
    7.     int *base;
    8.     int *top;
    9.     int stacksize;
    10. }Sqstack;
    11.  
    12. void InitStack(Sqstack *s,int initsize){
    13.     (*s).base=(int *)malloc(initsize*sizeof(int));
    14.     if(!(*s).base)exit(0);
    15.     (*s).top=(*s).base;
    16.     (*s).stacksize=initsize;
    17. }
    18. void Push(Sqstack *s,int e){
    19.     if((*s).top-(*s).base >= (*s).stacksize){
    20.         (*s).base=(int*)realloc((*s).base,((*s).stacksize+incresize)*sizeof(int));
    21.         if(!(*s).base)exit(0);
    22.         (*s).top=(*s).base+(*s).stacksize;
    23.         (*s).stacksize+=incresize;
    24.     }
    25.     *((*s).top)=e;
    26.     (*s).top++;
    27. }
    28. void GetTop(Sqstack s,int *e){
    29.     if(s.top==s.base) printf("empty!");
    30.     *e=*(s.top-1);
    31.     
    32. }
    33. int StackLength(Sqstack s){
    34.     return s.top-s.base;
    35. }
    36. int StackEmpty(Sqstack s){
    37.     if(s.top==s.base)return 0;
    38.     else return 1;
    39. }
    40. void Pop(Sqstack *s,int *e){
    41.     if((*s).top==(*s).base) exit(0);
    42.     (*s).top--;
    43.     *e=*((*s).top);
    44. }
    45. void Destroystack(Sqstack *s){
    46.     if(s!=NULL){
    47.         free((*s).base);
    48.         (*s).base=NULL; (*s).top=NULL;
    49.         (*s).stacksize=0;
    50.     }
    51. }
    52.  
    53. int main(){
    54.     Sqstack s;
    55.     int n;
    56.     scanf("%d",&n);
    57.     InitStack(&s,n);
    58.     int e,p,x;
    59.    
    60.     s.stacksize=n;
    61.     for(int j=0;j
    62.         scanf("%d",&e);
    63.         if(e!=-1){
    64.             Push(&s,e);
    65.         }
    66.         else{
    67.             if(StackEmpty(s)==0) //printf("\n非空！");
    68.             {
    69.                 printf("出栈失败");
    70.                 exit(0);
    71.             }
    72.             GetTop(s,&p);
    73.             printf("%d\n",p);
    74.             
    75.             Pop(&s,&x);
    76.             //printf("%d",x);
    77.         }
    78.     }
    79.     
    80.     
    81.     return 0;
    82.     
    83. }

  • 相关阅读:
    【yolo训练数据集】标注好的垃圾分类数据集共享
    VSCode 运行java程序中文乱码
    git merge与git rebase详解
    【Web3 系列开发教程——创建你的第一个 NFT（7）】创建一个 NFT DApp，给你的 NFT 赋予属性，例如图片
    Python3 笔记：upper()、isupper()、lower()、islower()、swapcase()
    mapper.updateById(User)，修改为”“失败的解决方案
    【Leetcode】204. 计数质数
    pycharm基本使用（常用快捷键）
    ubuntu安装ssh,设置开机自启动
    为什么要做字节对齐 alignment？
  • 原文地址：https://blog.csdn.net/m0_74161592/article/details/133798247