学习总结第二十二天——栈的实现以及简易计算器

本来昨天的计划是研究背包，栈，队列的，但是没想到实际研究起来光一个栈都那么花时间。今天写了一个栈的动态数组实现API，这个API我实现了两种版本，第一种是使用了固定长度的数组来存储，很不方便，使用时必须指定大小，并且经常会有空间浪费或者栈满的需求。使用了动态数组的方法，就能实现栈的高可用性。在栈的元素较少时将栈减小，元素满时扩大。下面是第一种实现和一个测试用例：

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

typedef struct
{
  int * sta;
  int maxSize;
  int nowSize;
  } stack;
//API声明
stack* StackCreate(int size);
int StackPop (stack * sta);
bool StackPush (stack *sta,int i);
int StackSize (stack *sta);
bool StackIsEmpty (stack *sta);
bool StackIsFull (stack *sta);//
void StackFree (stack *sta);
//测试用例
int main(int argc, char const *argv[]) {
  stack *st=StackCreate(100);
  for (int i=0;!StackIsFull(st);i++)
  {
    StackPush(st,i);
  }
  while (!StackIsEmpty(st)) {
    printf("%d ",StackPop(st));
  }
  StackFree(st);
  return 0;
}
//API实现
stack* StackCreate(int size)
{
  stack *temp=malloc(sizeof(stack));
  if (size<1)
  return NULL;
  temp->sta=(int *)malloc(sizeof(int)*size);
  temp->maxSize=size;
  temp->nowSize=0;
  return temp;
}

int StackPop(stack * sta)
{
  if (StackIsEmpty(sta))
  return -1;
  else
  return sta->sta[--sta->nowSize];
}

bool StackPush (stack *sta,int i)
{
  if (StackIsFull(sta))
  return false;
  else
  sta->sta[sta->nowSize++]=i;
  return true;
}
int StackSize (stack *sta)
{
  return sta->nowSize;
}
bool StackIsEmpty (stack *sta)
{
  return sta->nowSize==0;
}
bool StackIsFull (stack *sta)
{
  return sta->nowSize==sta->maxSize;
}
void StackFree(stack *sta) {
  free(sta->sta);
  free(sta);
}

第二种实现我将其打包成了一个库，下面是具体代码：

stacklib.h
#ifndef STACK
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define STACK 0
#endif
#ifndef STACK_INIT_SIZE
#define STACK_INIT_SIZE 3
#endif
typedef struct
{
int * sta;
int maxSize;
int nowSize;
} stack;
stack* StackCreate(void);
int StackPop (stack * sta);
void StackPush (stack *sta,int i);
int StackNowSize (stack *sta);
int StackMaxSize (stack *sta);
bool StackIsEmpty (stack *sta);
//bool StackIsFull (stack *sta);
void StackFree (stack *sta);

---

stacklib.c
#include “stacklib.h”
stack* StackCreate (void)
{
stack *temp=malloc(sizeof(stack));
temp->sta=(int *)malloc(sizeof(int)*STACK_INIT_SIZE);
temp->maxSize=STACK_INIT_SIZE;
temp->nowSize=0;
return temp->staNULL?NULL:temp;
}
bool StackReSize(stack * sta,int size)
{
if (size<=0)
return false;
int *temp=malloc(sizeof(int)*size);
if (tempNULL)
return false;
for (int i=0;inowSize;i++)
{
temp[i]=sta->sta[i];
}
free (sta->sta);
sta->sta=temp;
sta->maxSize=size;
return true;
}
int StackPop(stack * sta)
{
if (StackIsEmpty(sta))
return -1;
int i=sta->sta[–sta->nowSize];
if (sta->maxSize/4>=sta->nowSize)//空间过剩时，减少数组容量
{
StackReSize(sta,sta->maxSize/2);
}
return i;
}
void StackPush (stack sta,int i)
{
if (sta->nowSize==sta->maxSize)//空间不够时，扩充数组容量
{
StackReSize(sta,sta->maxSize2);
}
sta->sta[sta->nowSize++]=i;
}
int StackNowSize (stack *sta)
{
return sta->nowSize;
}
bool StackIsEmpty (stack *sta)
{
return sta->nowSize==0;
}
void StackFree(stack *sta)
{
free(sta->sta);
free(sta);
}
int StackMaxSize(stack *sta)
{
return sta->maxSize;
}

最后，我运用栈来做了一个小计算器，可惜目前还不能实现判断运算的先后顺序，只能人为在每个运算后添加括号进行运算，比如52必须要输入(52)才能计算，代码如下：
#include “stacklib.h”
#ifndef READ_SIZE
#define READ_SIZE 30
#endif
int main(int argc, char const argv[]) {
char ch[READ_SIZE];
fgets (ch,READ_SIZE,stdin);
stack numSta=StackCreate();//数字栈
stack chSta=StackCreate();//操作符栈
bool lastIsNum=false;//标志位，判断上个读取的字符是否是数字
for (int i=0;ch[i]!=’\0’&&ch[i]!=’\n’;i++)
{
switch (ch[i])
{
//若为操作符，压入操作符栈
case ‘+’:
case ‘-’:
case '’:
case ‘/’:
case ‘%’:
lastIsNum=false;
StackPush(chSta,(int)ch[i]);
break;
case ‘)’😕/右括号表示前面是一个运算，进行运算
{
char op=StackPop(chSta);//取出操作符
int val=StackPop(numSta);//取出右操作数
switch (op)
{
case ‘+’:
val+=StackPop(numSta);
break;
case ‘-’:
val=StackPop(numSta)-val;
break;
case '’:
val=StackPop(numSta);
break;
case ‘/’:
val=StackPop(numSta)/val;
break;
case ‘%’:
val=StackPop(numSta)%val;
break;
default:
break;
}
StackPush(numSta,val);
lastIsNum=false;
}
break;
case ‘(’😕/左括号直接丢弃
lastIsNum=false;
break;
default:
if (ch[i]>47&&ch[i]<58)//判断是否为数字
{
if (lastIsNum==true)
{
int temp=StackPop(numSta);
temp=temp*10+(ch[i]-48);
StackPush(numSta,temp);
}
else
{
StackPush(numSta,ch[i]-48);
}
lastIsNum=true;
}
else//未预期的符号
{
printf(“Error\n” );
exit(-1);
}
break;
}
}
printf("%d\n",StackPop(numSta));
StackFree(numSta);
StackFree(chSta);
return 0;
}turn 0;
}