数据结构--栈

1. 顺序栈 

Stack_Opreator.c

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>typedef bool status;
#define MAXSIZE 10
struct Stack{int stack[MAXSIZE];int top;
};//创建顺序栈
struct Stack* Stack_Create(){struct Stack* p = (struct Stack*)malloc(sizeof(struct Stack));if(p==NULL){return NULL;}memset(p->stack,0,sizeof(p->stack));p->top = -1;//给初值return p;
}
status Stack_Push(struct Stack* p ,int data){//判断是否已经满了if(p->top==MAXSIZE-1){printf("栈已满，入栈失败\n");return false;}p->top+=1;p->stack[p->top] = data;return true;
}//出栈
status Stack_Pop(struct Stack* p,int* data){//判断栈是否为空if(p->top==-1){printf("栈为空栈，出栈失败！\n");return false;}*data = p->stack[p->top];p->stack[p->top]=0;//清空p->top--;return true;}//遍历栈
status Stack_travel(struct Stack* p){//判断是否为空int top_1 = p->top;if(top_1==-1){printf("栈为空\n");return false;}while(top_1>=0){printf("%d ",p->stack[top_1]);top_1--;}return true;}int main(){struct Stack* stack_ = Stack_Create();Stack_Push(stack_,10);Stack_Push(stack_,20);Stack_Push(stack_,30);Stack_travel(stack_);printf("\n******************\n");int data;Stack_Pop(stack_,&data);printf("取出的栈顶元素：%d\n",data);Stack_travel(stack_);return 0;    
}

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "stdbool.h"
#define MAXSIZE_DATA 10
#define MAXSIZE_OPERATOR 10//顺序栈表达式求值
struct Stack_Data
{int arr_data[MAXSIZE_DATA];int top;
};
struct Stack_Operator
{char arr_operator[MAXSIZE_OPERATOR];int top;
};//栈的初始化
struct Stack_Data *Stack_Data_Init()//数字栈的创建
{struct Stack_Data *stack=(struct Stack_Data*)malloc(sizeof(struct Stack_Data));if(stack==NULL){return NULL;}stack->top=-1;memset(stack->arr_data,0,sizeof(int)*MAXSIZE_DATA);return stack;
}
struct Stack_Operator*Stack_Operator_Init()//操作符栈的初始化
{struct Stack_Operator *stack=(struct Stack_Operator*)malloc(sizeof(struct Stack_Operator));if(stack==NULL){return NULL;}stack->top=-1;memset(stack->arr_operator,0,MAXSIZE_OPERATOR);return stack;
}//栈的遍历
bool Stack_Data_Travel(struct Stack_Data *P)
{if(P->top==-1){return false;}printf("################数字栈的遍历################\n");while(P->top!=-1){printf("data：%d\n",P->arr_data[P->top]);P->top--;}return true;
}bool Stack_Operator_Travel(struct Stack_Operator *P)
{if(P->top==-1){return false;}printf("################运算符栈的遍历################\n");while(P->top!=-1){printf("operator：%c\n",P->arr_operator[P->top]);P->top--;}return true;
}//栈判空
bool Stack_Data_IsEmpty(struct Stack_Data*P)
{if(P->top==-1){return true;}return false;
}
bool Stack_Operator_IsEmpty(struct Stack_Operator *P)
{if(P->top==-1){return true;}return false;
}
//入栈
bool Stack_Data_Push(struct Stack_Data *P,int data)
{if(P->top==MAXSIZE_DATA-1){return false;}P->top++;P->arr_data[P->top]=data;return true;
}
bool Stack_Operator_Push(struct Stack_Operator *P,char operator)
{if(P->top==MAXSIZE_OPERATOR-1){return false;}P->top++;P->arr_operator[P->top]=operator;return true;
}
//出栈
bool Stack_Data_Pop(struct Stack_Data *P,int *data)
{if(P->top==-1){return false;}*data=P->arr_data[P->top];P->top--;return true;
}
bool Stack_Operator_Pop(struct Stack_Operator *P,char *operator)
{if(P->top==-1){return false;}*operator=P->arr_operator[P->top];P->top--;return true;
}
//判断输入的是数字还是运算符, true:运算符, false:数字
char opt[5]={'+','-','*','/','#'};
bool is_opt(char ch)
{for(int i=0;i<sizeof(opt);i++){if(ch==opt[i]){return true;}}return false;
}
//判断运算符的优先级,假设opt1是栈顶运算符,opt2是待入栈的运算符
//如果opt1>=opt2,则opt1出栈,opt2入栈,否则opt2入栈
char Priority(char opt1,char opt2)
{switch(opt1){case '+':if(opt2=='+'){//opt1出栈,opt2入栈,取两个数字进行opt1运算,然后再入数字栈return '=';//优先级相等}else if(opt2=='-'){//opt1出栈,opt2入栈,取两个数字进行opt1运算,然后再入数字栈//优先级相等return '=';}else if(opt2=='*'){//opt2入栈return '<';}else if(opt2=='/'){//opt2入栈return '<';}break;case '-':if(opt2=='+'){//opt1出栈,opt2入栈,取两个数字进行opt1运算,然后再入数字栈return '=';//优先级相等}else if(opt2=='-'){//opt1出栈,opt2入栈,取两个数字进行opt1运算,然后再入数字栈//优先级相等return '=';}else if(opt2=='*'){//opt2入栈return '<';}else if(opt2=='/'){//opt2入栈return '<';}break;case '*':if(opt2=='+'){return '>';}else if(opt2=='-'){return '>';}else if(opt2=='*'){return '=';}else if(opt2=='/'){return '=';}break;case '/':if(opt2=='+'){return '>';}else if(opt2=='-'){return '>';}else if(opt2=='*'){return '=';}else if(opt2=='/'){return '=';}break;default:return '\0';break;//输入其他不符合法的字符返回为空}
}
int main()
{//表达式:5-4x3+5/2char express[]="5-4*3+5/2#";//可以加一个结束标志"#"struct Stack_Data *stack_data=Stack_Data_Init();struct Stack_Operator *stack_operator=Stack_Operator_Init();int data1;//每一次运算都会从数字栈中取两个数字出来int data2;for(int i=0;i<strlen(express);i++){//如果是数字,则入数字栈,如果是运算符则入运算符栈if(is_opt(express[i]))//如果为true,则是运算符{if(express[i]=='#')//遇到‘#’则整个表达式入栈和出栈完成，接下来只需要判断运算符栈是否还有数据，如果有则继续取数据进行运算，直到运算符栈为空{printf("数字栈顶指针：%d\n",stack_data->top);printf("运算符栈顶指针：%d\n",stack_operator->top);while(stack_operator->top!=-1){Stack_Data_Pop(stack_data,&data1);Stack_Data_Pop(stack_data,&data2);char yun;Stack_Operator_Pop(stack_operator,&yun);//取出栈顶操作符printf("出栈的字符：%c\n",stack_operator->arr_operator[stack_operator->top+1]);switch(yun){case '+':Stack_Data_Push(stack_data,data2+data1);break;case '-':Stack_Data_Push(stack_data,data2-data1);break;case '*':Stack_Data_Push(stack_data,data2*data1);break;case '/':Stack_Data_Push(stack_data,data2/data1);break;default:break;}}break;}if(stack_operator->top==-1){//表示是第一个运算符,进行入栈即可Stack_Operator_Push(stack_operator,express[i]);continue;//存入之后直接进入下一次循环，因为入栈了top++，如果不进入下一次循环就会进入else执行}	else //表示不是第一个运算符{//这时候需要判断该栈顶运算符与待入栈的运算符的优先级判断if(Priority(stack_operator->arr_operator[stack_operator->top],express[i])=='='||Priority(stack_operator->arr_operator[stack_operator->top],express[i])=='>'){//如果栈顶与运算符优先级与待入栈运算符优先级高或者等于,则出栈栈顶运算符,然后再入栈待入栈运算符char yun;Stack_Operator_Pop(stack_operator,&yun);switch(yun){case '+'://加法运算//取数字栈中的两个数据进行运算,运算完将结果再入栈Stack_Data_Pop(stack_data,&data1);Stack_Data_Pop(stack_data,&data2);//将运算的结果，压入数字栈Stack_Data_Push(stack_data,data2+data1);//将待入栈的运算符进行入栈Stack_Operator_Push(stack_operator,express[i]);break;case '-'://减法运算//取数字栈中的两个数据进行运算,运算完将结果再入栈Stack_Data_Pop(stack_data,&data1);Stack_Data_Pop(stack_data,&data2);//将运算的结果，压入数字栈Stack_Data_Push(stack_data,data2-data1);//将待入栈的运算符进行入栈Stack_Operator_Push(stack_operator,express[i]);break;case '*'://乘法运算//取数字栈中的两个数据进行运算,运算完将结果再入栈Stack_Data_Pop(stack_data,&data1);Stack_Data_Pop(stack_data,&data2);//将运算的结果，压入数字栈Stack_Data_Push(stack_data,data2*data1);//再判断栈顶指针是否比待入栈的优先级高或者等于，如果优先级高或者等于则继续出栈，否则入栈while(Priority(stack_operator->arr_operator[stack_operator->top],express[i])=='='||Priority(stack_operator->arr_operator[stack_operator->top],express[i])=='>'){char yun;Stack_Operator_Pop(stack_operator,&yun);if(yun=='-'){Stack_Data_Pop(stack_data,&data1);Stack_Data_Pop(stack_data,&data2);	//将运算的结果，压入数字栈Stack_Data_Push(stack_data,data2-data1);}if(stack_operator->top==-1)//直到运算符栈为空，才退出判断{break;}						}//将待入栈的运算符进行入栈Stack_Operator_Push(stack_operator,express[i]);break;case '/'://除法运算//取数字栈中的两个数据进行运算,运算完将结果再入栈Stack_Data_Pop(stack_data,&data1);Stack_Data_Pop(stack_data,&data2);//将运算的结果，压入数字栈Stack_Data_Push(stack_data,data2/data1);//将待入栈的运算符进行入栈Stack_Operator_Push(stack_operator,express[i]);break;defalut:break;}}else if(Priority(stack_operator->arr_operator[stack_operator->top],express[i])=='<'){//如果待入栈的运算符优先级大于栈顶优先级,则入栈Stack_Operator_Push(stack_operator,express[i]);}}}else{//如果是数字则入数字栈Stack_Data_Push(stack_data,express[i]-'0');}}printf("计算结果为：%d\n",stack_data->arr_data[stack_data->top]);return 0;
}