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

#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);

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新资格考试认证数据结构课程设计算术表达式实验参考代码全文阅读和word下载服务。