数据结构中缀式中缀表达式改后缀表达式并求值
- 格式：doc
- 大小：2.02 MB
- 文档页数：6
《数据结构》课程设计报告课程设计题目：中缀表达式改后缀表达式并求值
一. 实验目的
·掌握栈的特征及基本操作，如入栈、出栈等，栈的顺序存储结构和链式存储结构的实现，以便在实际问题中灵活应用。
·掌握栈的典型应用——中缀表达式转后缀表达式，并利用后缀表达式求值。
二. 实验内容
（一）中缀表达式转后缀表达式的方法：
1.遇到操作数：直接输出（添加到后缀表达式中）
2.栈为空时，遇到运算符，直接入栈
3.遇到左括号：将其入栈
4.遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出。
5.遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈
6.最终将栈中的元素依次出栈，输出。
（二）
三. 实验分析
程序源码（要求对每个函数及主要代码加上注释语句），源码出处。
//
// main.c
// 后缀表达式求值
//
// Created by 颜彦闻on 14/12/2.
// Copyright (c) 2014年颜彦闻. All rights reserved.
//
#include <stdio.h>
#include <stdlib.h>
#define StackSize 100
#define QueueSize 100
typedef char DataType;
typedef struct{
char data[100];
int front,rear;
}SeqQueue; //定义队列类型
void InitQueue(SeqQueue *Q) //初始化队列
{
Q->front=0;
Q->rear=0;
}
int QueueEmpty(SeqQueue Q) //判空
{
return Q.rear==Q.front;
}
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)%QueueSize;
}
}
DataType DeQueue(SeqQueue *Q)
{
char x;
if(QueueEmpty(*Q))
return0;
else
{
x=Q->data[Q->front];
Q->front=(Q->front+1)%QueueSize;
return x;
}
}
//栈的相关操作
typedef struct{
DataType data[100];
int top;
}SeqStack;
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");
return0;
}
else
return S->data[S->top--];
}
DataType GetTop(SeqStack S) //取栈顶元素
{
if(S.top==-1)
{
printf("stack empty");
return0;
}
else
return S.data[S.top];
}
int Priority(DataType op) //求运算符优先级函数{
switch(op)
{
case'(':
case'#':
return0;
case'-':
case'+':
return1;
case'*':
case'/':
return2;
}
return -1;
}
void CTPostExp(SeqQueue *Q)
{
SeqStack S;
char c,t;
InitStack(& S);
Push(&S,'#');
do
{
c=getchar();
switch(c)
{
case' ':break;
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=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!='#');
}
DataType CPostExp(SeqQueue Q)
{
SeqStack S;
char ch;
int x,y;
InitStack(&S);
while(!QueueEmpty(Q))
{
ch=DeQueue(&Q);
if(ch>='0'&&ch<='9')
Push(&S,ch);
else
{
y=Pop(&S)-'0';
x=Pop(&S)-'0';
switch(ch)
{
case'+': Push(&S,(char)(x+y+'0'));
break;
case'-': Push(&S,(char)(x-y+'0'));
break;
case'*': Push(&S,(char)(x*y+'0'));
break;
case'/': Push(&S,(char)(x/y+'0'));
break;
}
}
}
return GetTop(S);
}
int main(int argc, char *argv[])
{
SeqQueue Q;
InitQueue(&Q);
printf("输入表达式：\n");
CTPostExp(&Q);
printf("结果：%c\n",CPostExp(Q));
printf("后缀表达式：");
while(!QueueEmpty(Q))
printf("%2c",DeQueue(&Q));
printf("\n");
system("PAUSE");
return0;
}
四. 算法时间复杂度。
0（n）
五. 小结
除了主函数以外的其他函数是参考书上的代码，修改和增加了部分代码后，才可以运行。
通过运行代码，深刻体会栈的后进先出的特性。
六、用户手册
1）系统要求：win98以上操作系统
2）语言平台：c或c++
3）工具：Xcode。
