算术表达式的前缀式中缀式后缀式

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

目 录

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

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

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

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

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

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

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

一、设计思想

第一种算法

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

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

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

c语言 中缀、后缀 算术表达式求值用栈实现

#include<stdio.h> #include<string.h> #include<malloc.h> #include<stdlib.h> #define MaxSize 50

typedef struct {

float data[MaxSize]; int top; }OpStack; typedef struct {

char data[MaxSize]; int top; }SeqStack;

void InitStack(SeqStack *S);//初始化栈

int StackEmpty(SeqStack S);//判断栈是否为空 int PushStack(SeqStack *S,char e);//进栈

int PopStack(SeqStack *S,char *e);//删除栈顶元素 int GetTop(SeqStack S,char *e);//取栈顶元素

void TranslateExpress(char s1[],char s2[]);//将中缀表达式转化为后缀表达式

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

掌握线性表的使用，熟练掌握栈的各种操作函数，能借助于栈的功能将中缀表达式转换为后缀表达式，并利用后缀表达式求值。 二．实验要求及实验环境 实验要求：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

中缀表达式转后缀表达式

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

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_

软 件 学 院

课程设计报告书

课程名称 数据结构 设计题目 算术表达式求值演示程序 专业班级 学 号

姓 名 指导教师

2012年 1月

0

目录

1.设计时间 ..................................................... 2 2.设计目的 ..................................................... 2 3.设计任务 ..................................................... 2 4.设计内容 ..................................................... 2 4.1需求分析 ................................................... 2 4.2总体设计 ......

软 件 学 院

课程设计报告书

课程名称 数据结构 设计题目 算术表达式求值演示程序 专业班级 学 号

姓 名 指导教师

2012年 1月

0

目录

1.设计时间 ..................................................... 2 2.设计目的 ..................................................... 2 3.设计任务 ..................................................... 2 4.设计内容 ..................................................... 2 4.1需求分析 ................................................... 2 4.2总体设计 ......

这是我们老师自己写的有关编译原理follow处理办法的资料,挺不错的

LOGO

算术表达式FOLLOW的推 的推 算术表达式 理

这是我们老师自己写的有关编译原理follow处理办法的资料,挺不错的

文法： 文法： E TE’ E’ +TE’ | ε T FT’ T’ *FT’ | ε F (E) 最终答案： 最终答案：| id E:{$,)} E’:{$,)} : :

FIRST集合 集合 FIRST(F) = {(, id}; ; FIRST(E) =FIRST(T) = {(,id} FIRST(E’) = {+, ε}; FIRST(T’)={*, ε} T,T’:{+, ), $} F:{+,*,),$} : :

LOGO

规则编号： 规则编号： a、如果存在产生式 中所有非 、如果存在产生式A αBβ,那么 ，那么FIRST(β)中所有非ε的符号 中所有 的符号 都在FOLLOW(B)中。 都在 中 b1、如果存在一个产生式 、如果存在一个产生式A αB,那么 ，那么FOLLOW(A)中的所有 中的所有 符号都加入到FOLLOW(B)中. 符号都加入到 中 b2、或者 包含ε, 、或者A αBβ且FIRST(β)包含 ，那么 且 包含 那么FO

实验三 后缀表达式的计算

实验目的：

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

按常规形式输入算术表达式（例如：输入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．从左到右扫描中缀表达式，经语法分析找出中缀表达式出现的错误并给出错误的具体位置和类型。一个运算符栈存放暂时不能出现的运算符，逆波兰区存放逆波兰表达式。

2．测试所编程序，给出正确和错误的结果。

(三)实验要求

1．学生课前要认真阅读实验指导，理解实验内容与相关理论知识的关系，并完成预习报告

2．用C语言或其它高级语言编写程序

3．写出实验报告

0 / 7word.

内蒙古工业大学信息工程学院

实验报告成绩：指导教师审核（签名）：年月日

预习报告□实验报告□

语法制导把表达式翻译成逆波兰式

(一)实验目的

通过上机实习加深对语法指导翻译原理的理解，掌握运算符优先权的算法，将语法分析所识别的表达式变换成中间代码的翻译方法。

(二)实验内容

同预习报告

(三)实验要求

1.学生课前要认真阅读实验指导，理解实验内容与相关理论知识的关系，并完成预习报告

2．用C语言或其它高级语言编写程序

3．写出实验报告

(四)实验设计思路

1）表达式生成逆波兰

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

学生姓名：

课程成绩：报告

数据结构

算术表达式求值

学号

：

二零一六 年六 月

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)

初始条件：栈已经存在

操作结果