![数据结构栈与队列](https://serverless-page-bucket-0k20efve-1307414288.cos-website.ap-shanghai.myqcloud.com/post-images/shu-ju-jie-gou-zhan-yu-dui-lie.jpeg)
数据结构栈与队列
⚽️表达式计算
🤾♂Stack.h
#include<stdio.h>
#include<malloc.h>
#include <stdlib.h>
#define MaxSize 100
typedef char ElemType;
typedef struct
{
ElemType data[MaxSize];
int top;
} SqStack;
void InitStack(SqStack*& s)
{
s = (SqStack*)malloc(sizeof(SqStack));
s->top = -1;
}
bool StackEmpty(SqStack* s)
{
return(s->top == -1);
}
bool Push(SqStack*& s, ElemType e)
{
if (s->top == MaxSize - 1)
return false;
s->top++;
s->data[s->top] = e;
return true;
}
bool Pop(SqStack*& s, ElemType& e)
{
if (s->top == -1)
return false;
e = s->data[s->top];
s->top--;
return true;
}
bool GetTop(SqStack* s, ElemType& e) //取栈顶元素e
{
if (s->top == -1)
return false;
e = s->data[s->top];
return true;
}
void DestroyStack(SqStack*& s)
{
free(s);
}
typedef double ElemType1;
typedef struct linknode
{
ElemType1 data; //数据域
struct linknode* next; //指针域
} LinkStNode; //链栈类型
void InitStack1(LinkStNode*& s)
{
s = (LinkStNode*)malloc(sizeof(LinkStNode));
s->next = NULL;
}
void DestroyStack1(LinkStNode*& s)
{
LinkStNode* pre = s,p=s->next;
while (p != NULL)
{
free(pre);
pre = p;
p = pre->next;
}
free(pre);
}
bool StackEmpty1(LinkStNode s)
{
return(s->next == NULL);
}
bool Push1(LinkStNode*& s, ElemType1 e)
{
LinkStNode* p;
p = (LinkStNode*)malloc(sizeof(LinkStNode));
p->data = e;
p->next = s->next;
s->next = p;
return true;
}
bool Pop1(LinkStNode*& s, ElemType1& e)
{
LinkStNode* p;
if (s->next == NULL)
return false;
p = s->next;
e = p->data;
s->next = p->next;
free(p);
return true;
}
bool GetTop1(LinkStNode* s, ElemType1& e)
{
if (s->next == NULL)
return false;
e = s->next->data;
return true;
}
🤽♀biaodashi.h
#include "Stack.h"
void trans(char exp[], char postexp[])
{
char e;
SqStack* Optr;
InitStack(Optr);
int i = 0;
while (*exp != '\0')
{
switch (*exp)
{
case '(':
Push(Optr, '(');
exp++;
break;
case ')':
Pop(Optr, e);
while (e != '(')
{
postexp[i++] = e;
Pop(Optr, e);
}
exp++;
break;
case '+':
case '-':
while (!StackEmpty(Optr))
{
GetTop(Optr, e);
if (e != '(')
{
postexp[i++] = e;
Pop(Optr, e);
}
else
break;
}
Push(Optr, *exp);
exp++;
break;
case '*':
case '/':
while (!StackEmpty(Optr))
{
GetTop(Optr, e);
if (e == '*' || e == '/')
{
postexp[i++] = e;
Pop(Optr, e);
}
else
break;
}
Push(Optr, *exp);
exp++;
break;
default:
while (*exp >= '0' && *exp <= '9')
{
postexp[i++] = *exp;
exp++;
}
postexp[i++] = '#';
}
}
while (!StackEmpty(Optr))
{
Pop(Optr, e);
postexp[i++] = e;
}
postexp[i] = '\0';
DestroyStack(Optr);
}
double compvalue(char* postexp)
{
double d, a, b, c, e;
LinkStNode* Opnb;
InitStack1(Opnb);
while (*postexp != '\0')
{
switch (postexp)
{
case '+':
Pop1(Opnb, a);
Pop1(Opnb, b);
c = b + a;
Push1(Opnb, c);
break;
case '-':
Pop1(Opnb, a);
Pop1(Opnb, b);
c = b - a;
Push1(Opnb, c);
break;
case '':
Pop1(Opnb, a);
Pop1(Opnb, b);
c = b * a;
Push1(Opnb, c);
break;
case '/':
Pop1(Opnb, a);
Pop1(Opnb, b);
if (a != 0)
{
c = b / a;
Push1(Opnb, c);
break;
}
else
{
printf("\n\t除零错误!\n");
exit(0);
}
break;
default:
d = 0;
while (*postexp >= '0' && *postexp <= '9')
{
d = 10 * d + *postexp - '0';
postexp++;
}
Push1(Opnb, d); //将数值d进栈
break;
}
postexp++; //继续处理其他字符
}
GetTop1(Opnb, e); //取栈顶元素e
DestroyStack1(Opnb); //销毁栈
return e; //返回e
}
🏀main.cpp
#include "biaodashi.h"
int main()
{
char exp[] = "(56-20)/(4+2)";
char postexp[MaxSize];
trans(exp, postexp);
printf("中缀表达式:%s\n", exp);
printf("后缀表达式:%s\n", postexp);
printf("表达式的值:%g\n", compvalue(postexp));
return 1;
}