数据结构前缀后缀表达式

实验三 后缀表达式的计算

实验目的：

熟练掌握栈和队列的存储结构设计及基本操作的实现；学会分析实际问题中具有栈特点的数据结构；了解表达式的前缀、中缀、后缀等计算机内表示形式。 实验内容与要求：

按常规形式输入算术表达式（例如：输入2*(6-4)+8/4），要求能够： （1）生成表达式的后缀表示，并输出； （2）生成表达式的前缀表示，并输出；

（3）基于表达式的后缀表示，对该表达式求值； （4）编写一个主程序对表达式求值函数进行测试。 算法设计：

#include 关系，在分析过程查找到这个值，表示表达#include 式有错。 #include char *OpretorS="+-*/()#"; //运算符集 #define ERROR 0 char *Express="2*(6-4)+8/4"; //初始化的#define OK 1 表达式 #define N 50 int InitStack(SqStack *S); //构造空栈 #define STACK_INT_SIZE 10 //存储空int push(SqStack *S,ElemType *e);

课程设计 课程名称：题目名称：

学生姓名：

课程成绩：报告

数据结构

算术表达式求值

学号

：

二零一六 年六 月

1.需求分析

本演示程序用C++6.0编写，完成栈的生成。

（1）输入的形式和输入值的范围：输入合法表达式，以“#”结尾；输入的操作数是正整数，运算符只含加减乘除四种运算符。

（2）输出的形式：显示输入是否正确、输入序列和栈的变化过程、计算结果。

（3）程序所能达到的功能：完成算术表达式的计算。 （4）测试数据：

①输入3*（2+4）#； ②输入5*－2#。

2.概要设计

（1）为了实现上述程序功能，需要定义栈的抽象数据类型：

ADT SqStack{

数据对象：D={ai| ai ∈ElemSet,i=1,2,3??，n,n≥0} 数据关系：R1={| ai-1,ai ∈D,i=1,2,3,??，n} 基本操作：

InitStack(SqStack &S)

操作结果：声明栈建立函数 Push(SqStack &S,char e)

初始条件：栈已经存在 操作结果：声明入栈函数 Pop(SqStack &S)

初始条件：栈已经存在 操作结果：声明出栈函数 DispStack(SqStack &S)

初始条件：栈已经存在

操作结果

中缀表达式的直接计算,中缀表达式转化成后缀表达式的计算

目 录

一、设计思想……………………………………………………….01

二、算法流程图…………………………………………………….02

三、源代码………………………………………………………….03

四、运行结果……………………………………………………….16

五、遇到的问题及解决…………………………………………….17

六、心得体会……………………………………………………….18

中缀表达式的直接计算,中缀表达式转化成后缀表达式的计算

一、设计思想

第一种算法

先把算术表达式转化成后缀表达式，在对后缀表达式进行计算。

首先建立一个符号栈，用于存放字符和字符的优先级别；然后在建立一个数栈，用于辅助后缀表达式的计算；最后在定义一个字符串数组，用于存放后缀表达式。建立一个计算的函数，该函数用于两个数的计算，在调用这个函数的时候，传入三个参数，两个浮点型参数和一个字符型参数，根据不同的符号进行不同的计算。定义一个判断优先级别的函数，用于判断两个操作符的优先级别，在根据优先级的不同决定不同的操作。

后缀表达式的取得，对算术表达式字符串进行挨个的扫描，如果是数字或者是小数点， 则将数字或者小数点存放到字符数组中，每取完一个

设计成绩 报告成绩 指导老师 一．实验目的

掌握线性表的使用，熟练掌握栈的各种操作函数，能借助于栈的功能将中缀表达式转换为后缀表达式，并利用后缀表达式求值。 二．实验要求及实验环境 实验要求：1.使用栈来进行操作

2.能提示用户输入正确的中缀表达式的值，并输出正确的后缀表达式 3.利用后缀表达式求值并输出 实验环境：CodeBlocks(visual stdio)/win 7系统

三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系） 主要的数据类型：

Word结构体类型的定义，含有两个变量字符型和double型 栈类型的定义，其中数组类型为word型，栈的各种操作函数的定义 主函数int main()中

char mid[100] 存放用户输入的中缀表达式

int m 记录用户输入的中缀表达式所含的字符数

word m_word[100] 可将中缀中的字符和数字分开存放在两个不同类型的数组中，并实现将连续的多位整数至于统一存储空间 word post[100] 存放转换后的后缀表达式的值 int l

算法与数据结构课程设计任务书

（09级）

题目：表达式求解问题

学生姓名： XX 学号： 09780015 班级： 计算机网络 题目类型：软件工程（R） 指导教师： XXX

一． 题目简介

该设计要求学生设计程序，实现任意算术表达式的求解问题。通过该题目的设计过程，可以加深理解线性表及栈的逻辑结构、存储结构，掌握线性表及栈上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。

二．

主要任务

1、查阅文献资料，一般在3篇以上； 2、建立数据的逻辑结构和物理结构； 3、完成相应算法的设计； 4、完成测试工作； 5、撰写设计说明书； 6、做好答辩工作。

三． 主要内容、功能及技术指标

（1）使用顺序栈存储算术表达式，主要功能有：输入并建立算术表达式、输出算术表达式、算术表达式的计算及显示输出等；

（2）至少要用10个测试数据，算法对

算法与数据结构课程设计任务书

（09级）

题目：表达式求解问题

学生姓名： XX 学号： 09780015 班级： 计算机网络 题目类型：软件工程（R） 指导教师： XXX

一． 题目简介

该设计要求学生设计程序，实现任意算术表达式的求解问题。通过该题目的设计过程，可以加深理解线性表及栈的逻辑结构、存储结构，掌握线性表及栈上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。

二．

主要任务

1、查阅文献资料，一般在3篇以上； 2、建立数据的逻辑结构和物理结构； 3、完成相应算法的设计； 4、完成测试工作； 5、撰写设计说明书； 6、做好答辩工作。

三． 主要内容、功能及技术指标

（1）使用顺序栈存储算术表达式，主要功能有：输入并建立算术表达式、输出算术表达式、算术表达式的计算及显示输出等；

（2）至少要用10个测试数据，算法对

实验 表达式括号匹配配对判断问题

姓名： 班级：

学号： 实验时间：

1.问题描述

一个算术表达式含圆括号、中括号、花括号,且它们可任意嵌套使用。写一程序，判断任一算术表达式中所含括号是否正确配对。

2.数据结构设计

匹配判别发生在右括号出现时，且被匹配的左括号应是距离右括号最近被输入的，二不是最先被输入的括号 ，即“先入后匹配”。因此用栈来解决。 #define stacksize 100 //定义栈的空间大小 struct

stack{ //定义栈的结构体

char strstack[stacksize];//定义栈的存储格式为字符型 int top; //定义栈的栈顶变量 };

void InitStack(stack &s)

{//定义一个新栈s，初始化栈顶为-1 s.top = -1; }

3.算法设计

（1）入栈的算法

char Push(stack &s, char a) { //入栈操作，将字符a入栈s

if(s.top == stacksize - 1) //当栈顶为栈的空间大小-1，栈满 return

中缀表达式转后缀表达式

中缀表达式转后缀表达式的规则。

1.遇到操作数：直接输入到后缀表达式栈 2.遇到运算符，直接入操作符栈 3.遇到左括号：直接将其入栈

4.遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出。

5.遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈

6.最终将操作符栈中的元素依次出栈，输出到后缀表达式栈。

以下是自己写的代码。亲测没有问题。（模拟一个计算器，可以带括号，中间可以空格，只支持整数输入，但是输出结果精确到小数后6位）

#include \

#define MAX_LEN 100 typedef struct cal{

unsigned char isOper;//是否是操作数 1，操作符 0.操作数 double Num; //值。或者是操作符的ASCII值 }STRUCT_CAL;

#define IS_NUM 0x00 #define IS_OPER 0x01

STRUCT_CAL stackCal[MAX_LEN]; STRUCT_CAL stackCalBack[MAX_

#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(SeqQueu

#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(SeqQueu