数据结构课程设计算术表达式实验参考代码

#include<stdio.h>
#define StackSize 100
#define QueueSize 100

typedef char DataType;
typedef struct {
char data[100];
int front,rear;
}SeqQueue;//队列的定义

typedef struct{
DataType data[100];
int top;
}SeqStack;//栈类型的定义

int DeQueue(SeqQueue * Q);
void InitQueue(SeqQueue * Q);
int QueueEmpty(SeqQueue * Q);
void EnQueue(SeqQueue * Q,DataType x);
void InitStack(SeqStack * S);
void Push(SeqStack * S,DataType x);
DataType Pop(SeqStack * S);
DataType GetTop(SeqStack * S);
int Priority(DataType op);
void CTPostExp(SeqQueue *Q);

void InitQueue(SeqQueue * Q)//初始化队列
{
Q->front=0;Q->rear=0;
}

int QueueEmpty(SeqQueue * Q)//判断队列是否为空
{
return Q->front==Q->rear;
}

void EnQueue(SeqQueue * Q,DataType x)//把输入的数字进队列
{
if((Q->rear+1)%QueueSize==Q->front) //判断队列是否满了
printf("Queue overflow");
else
{
Q->data[Q->rear]=x;
Q->rear=Q->rear+1;
}
}

int DeQueue(SeqQueue * Q)//队列输出
{
char x;
x=Q->data[Q->front];
Q->front=Q->front+1;
return x;
}

void InitStack(SeqStack * S)//初始化栈
{
S->top=-1;
}

void Push(SeqStack * S,DataType x)//对输入的元素进行进栈
{
if(S->top==StackSize-1)//判断是否栈满
printf("stack overflow");
else
{
S->top=S->top+1;//不能进行交换
S->data[S->top]=x;
}
}

DataType Pop(SeqStack * S)//出栈
{
if(S->top==-1)
printf("stack underflow");
else
return S->data[S->top--];
}

DataType GetTop(SeqStack * S)//取栈顶元素
{
if(S->top==-1)
printf("stack empty");
else
return S->data[S->top];
}

int Priority(DataType op)//优先级的比较
{
switch(op)
{
case '(':
case '#':return (0);
case '+':
case '-':return (1);
case '*':
case '/':return (2);
}
}

void CTPostExp(SeqQueue * Q)//对输入的字符进行处理
{
SeqStack OS;//运算栈符
char c,t;
SeqStack *S;
S=&OS;
InitStack(S);//初始化栈
Push(S,'#');//将#号压入栈底
do
{
c=getchar();
switch(c)
{
case ' ':break;//将空格去除
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
EnQueue(Q,c);break;//把数字压入队列
case '(':Push(S,c);break;//将"（"进栈
case ')':
case '#':
do{//如果输入的字符是#号和）就开始压入栈的符号拿给t
t=Pop(S);
if(t!='('&& t!='#')
EnQueue(Q,t);
}while(t!='('&& S->top!=-1);break;
case '+':
case '-':
case '*':
case '/':
while(Priority(c)<=Priority(GetTop(S)))
{
t=Pop(S);EnQueue(Q,t);
}
Push(S,c);break;
}
}while(c!='#');
}

void CPostExp(SeqQueue *Q)
{
SeqStack VS,*S;
char ch;
int x,y;
S=&
VS;
InitStack(S);
while(Q->front!=Q->rear)
{
ch=DeQueue(Q);
if(ch>='0'&&ch<='9')
Push(S,ch-'0');
else
{
y=Pop(S);