栈的应用

栈的应用

1，进制转换

把十进制转换成二进制

思路：要转换成几进制，就除以几，比如要转换成二进制，就每次除以2；比如要转换成16进制，就每次除以16；直到除没了为止。每次除之前，取模。把每次取到的模，压入栈。栈顶的值就是二进制的最大位，所以打印的时候，从栈顶开始打印。

#include <stdio.h>
#include <malloc.h>

push(int** top, int val){
  //先取二级指针指向的值，再取一级指针指向的值，最后让一级指针指向上面一个地址
  *(*top)++ = val;
}
int pop(int** top){
  //先取二级指针指向的值，再让一级指针的指向下面以个位置，最后取一级指针指向的值
  return *--(*top);
}
int main(){


  int *top, *base;
  top = base = (int*)malloc(sizeof(int) * 32);
  printf("请输入要转换的数字\n");
  int c,d;
  scanf("%d", &d);
  while(d != 0){
    c = d % 2;
    push(&top, c);
    d = d / 2;
  }

  while(top != base){
    printf("%d", pop(&top));
  }
  printf("\n");

}

2.各种括号配对

检查各种括号的嵌套，是否正确。

匹配正确例子：{([])[]}

匹配错误例子：{([)]}

思路：压栈之前和栈顶元素比较，如果匹配，就把栈顶元素出栈，如果不匹配就压栈。

最后看栈是否为空，如果不为空就说明匹配不成功。

#include <stdio.h>
#include <malloc.h>
#include <string.h>

void pop(char** top){
  --(*top);
}
void push (char** top, char * base, char s){
  switch (s){
  case ']':
    s = '[';
    break;
  case ')':
    s = '(';
    break;
  case '}':
    s = '{';
    break;
  default:
    break;
  }
  //保存top的指向
  char* tmp = *top;
  //第一次压栈，或者，s和栈顶的值不相同就继续压栈
  if(*top == base || s != *--tmp){
    *(*top)++ = s;
  }
  //s和栈顶的值相同就弹出
  else{
    pop(top);
  }
}
int main(){
  char* s = "[({}[])]";
  //char* s = "[";
  char *top, *base;
  top = base = (char*)malloc(sizeof(char) * strlen(s));
  int i = 0;
  for(; i < strlen(s); ++i){
    push(&top, base, s[i]);
  }
  //如果栈顶又回到了栈底，就说明完全都匹配上了
  if(top == base){
    printf("success\n");
  }else{
    printf("dead\n");
  }
  free(base);
}