当前位置：文档之家› 四则运算表达式求值(栈+二叉树,c++版)

四则运算表达式求值(栈+二叉树,c++版)

HUNAN UNIVERSITY

课程实习报告

题目：四则运算表达式求值

学生姓名：周华毅

学生学号：201308010411

专业班级：计科1304 指导老师：吴帆

完成日期：2015/5/1

一、需求分析

a)四则运算表达式求值，将四则运算表达式用中缀表达式表示，然后转换为后缀表达

式，并计算结果。

b)本程序要求利用二叉树后序遍历来实现表达式的转换，同时可以使用实验2的结果

来求解后缀表达式的值。

c)在字符界面上输入一个中缀表达式，回车表示结束。如果该中缀表达式正确，那么

在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔

开；如果不正确，在字符界面上输出表达式错误提示。

d)测试数据

输入：

21+23*（12-6）

输出：

21 23 12 6 -*+

二、概要设计

抽象数据类型

为实现上述程序的功能，应以字符串存储用户的输入，以及计算出的结果。

算法的基本思想

根据题目要求，利用二叉树后序遍历来实现表达式的转换。该算法的基本模块包括二叉树的建立以及如何把输入的中缀表达式利用二叉树后序遍历转化为后缀表达式。

1、首先要将输入的中缀表达式（数字字符）存入到二叉树中，由于存在两位或者两位以上的数，甚至还有小数，所以考虑用字符型指针存储数字字符和操作符。

2、为了便于将中缀表达式存入二叉树中，在录入中缀表达式后，要进行相应的处理，比如去掉空格符，添加结束标志，如‘=’、‘#’等。

3、中缀表达式存入到二叉树的过程中，要注意处理的顺序，如‘+’、‘-’号的优先级比‘*’、‘/’号的低，当遇到‘*’、‘/’号时，要判断树以上的节点中是否有‘+’、‘-’号，有的话要与其交换位置。遇到‘（’时要反复创建二叉树的结点，构建子二叉树，考虑到括号内要处理的步骤可能会较多，可以考虑用递归。遇到‘）’时则直接结束此子二叉树的建立。此外二叉树中叶子结点存储操作数，非叶子结点存储操作码。

4、对创建好的二叉树进行后序遍历，即可得到相应的后缀表达式，实现方法可以用递归的方式，由于后面还要计算表达式的值，故便利的过程中要将结点中得到的数据存入新的字符数组中。

程序的流程

程序由三个模块组成：

（1）输入模块：完成一个中缀表达式的输入，存入字符串数组array[Max]中。

（2）计算模块：设计一个建立二叉树的函数，Node* crtTree(Node* root)，传入根结点指针，返回根结点指针，该函数的实现还要反复使用另一个函数char

getOp(Node *temp)，其将数字字符存入一个结点，并返回数字字符的后一个符

号。void deal()函数功能是对字符数组进行处理。void output(Node *root);

函数功能是获得处理后的字符串，也就是中缀表达式转化为的后缀表达式。

（3）输出模块：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式和表达式的值；如果不正确，在字符界面上输出表达式错误提示。

三、详细设计

物理数据类型

题目要求输入的四则运算表达式运算符只有加减乘除，操作数有整数和小数，为了能够存储，采用C语言中的字符串数组。

char ch[Max];

算法的时空分析

算法的运行时间主要耗费在二叉树的建立过程中。可以发现，每当遇到一个运算符或操作数时，都要调用一次函数char getOp(Node *temp)，来将其存入二叉树的结点中，其中也会遇到递归的情况，但耗时可以忽略。所以假设输入的字符串中字符个数为N，则算法的时间复杂度为O(N)。

输入和输出的格式

输入

本程序可以将输入的四则运算表达式（中缀表达式）转换为后缀表达式//提示

请输入四则运算表达式：//提示

等待输入

输出

//提示

后缀表达式为：//输出结果的位置

表达式的值为：//输出结果的位置

四、调试分析

本次实验的难点主要是在建立二叉树的问题上。关于如何把中缀表达式存入二叉树中，我参考了网上的一些方法，成功实现了目标，但是却遇到了一个问题，那就是不能处理小数，甚至两位或两位以上的整数。因为如果采用字符数组来存储操作数，运算符合一位整数还可以处理，但对于两位数就就会出问题，最后我改进采用字符串数组来存储操作数，成功解决了问题。

另外在处理输入的非法表达式问题中，我也费了很大功夫，但总体问题不大。

五、测试结果

六、用户使用说明（可选）

1、本程序的运行环境为DOS操作系统

2、运行程序时

提示输入四则运算表达式

本程序可以将中缀表达式转化为后缀表达式，并计算结果

请输入四则运算表达式：

输出

后缀表达式为：

表达式的值为：

七、附录（可选）

程序源代码（c++）

1、利用二叉树后序遍历来实现表达式的转换：

#include

const int Max=100;

using namespace std;

class Node{

public:

char ch[Max]; //考虑到数值有时会是两位数，所以使用字符串数组

Node* lChild;

Node* rChild;

Node(){

strcpy(ch,"");

lChild=rChild=NULL;

}

~Node(){

if(lChild!=NULL)

delete lChild;

if(rChild!=NULL)

delete rChild;

}

};

static int count=0;

static char array[Max]; //保存原始的中缀表达式

static char str[2*Max]; //保存后序遍历出来的字符串，为表达式求值提供方便static int k=0;

char getOp(Node *temp); //temp指针保存每个结点，返回的是运算符

Node* crtTree(Node* root); //传入根结点指针，返回根结点指针

void output(Node *root); //获得处理后的字符串

bool isError(char); //判断字符是否有问题

void deal(); //对字符数组进行处理

double value(string); // 计算后缀表达式，得到其结果。

int main(){

Node* root=NULL;

cout<<"输入中缀表达式：";

cin.getline(array,40);

deal();

root=crtTree(root);

cout<<"输出后缀表达式：";

output(root);

cout<

cout<<"输出后缀表达式的值：";

if(value(str)!=0)

cout<

else

cout<<"A Wrong Input!"<

return 0;

}

//将数字字符存入一个结点，并返回数字字符的后一个符号char getOp(Node *temp){

int i=0;

if( isError(array[count]) )

exit(0);

while(array[count]<='9'&&array[count]>='0'||array[count]=='.'){ temp->ch[i]=array[count];

i++;

count++;

}

temp->ch[i]='\0';

count++;

return array[count-1];

}

//传入根结点指针，返回根结点指针

Node* crtTree(Node* root) {

Node *p,*q;

char op;

if(root==NULL){

root=new Node;

p=new Node;

}

op=getOp(root);

while(op!='='){

q=new Node;

q->ch[0]=op;

q->ch[1]='\0';

switch(op)

{

case '+':

case '-':

q->lChild=root;

root=q;

p=new Node;

op=getOp(p);

root->rChild=p;

break;

case '*':

case '/':

if(root->ch[0]=='+'||root->ch[0]=='-'){

p=new Node;

strcpy(p->ch,root->ch);

p->lChild=root;

p->rChild=q;

op=getOp(root);

root=p;

} else {

q->lChild=root;

root=q;

p=new Node;

op=getOp(p);

root->rChild=p;

} break;

case '(':

p=root;

while(p->rChild)

p=p->rChild;

if(p->lChild==NULL) {

p->lChild=crtTree(p->lChild); //递归创建括号里的指针

op=array[count];

count++;

break;

} else{

p->rChild=crtTree(p->rChild); //递归创建括号里的指针

op=array[count];

count++;

break;

}

case ')':

return root;

}

return root;

}

//传入根结点，后序遍历,赋值给另一个字符数组（主要是为了给后序的计算表达式值提供方便）

void output(Node *root){

int n;

if(root){

output(root->lChild);

output(root->rChild);

n=0;

while(root->ch[n]!='\0')

str[k++]=root->ch[n++];

str[k++]=' ';

}

bool isError(char ch){ //判断每个字符是否有错

if(ch!='+'&&ch!='-'&&ch!='*'&&ch!='/'&&!(ch<='9'&&ch>='0')&&ch!='.'&&ch!='('&&ch!=')'){ cout << "字符错误！";

return true;

}

return false;

}

void deal(){ //对字符数组进行处理

int i=0,n=0;

while(array[i]){

if(array[i]==' '||array[i]=='=')

i++;

array[n++]=array[i++];

}

array[n++]='=';

array[n]='\0';

}

double value(string s2){ // 计算后缀表达式，得到其结果。

stack < double> s;

double x,y;

int i = 0;

while(i < s2.length() ){

if(s2[i] == ' ')

i++;

switch(s2[i])

{

case '+':

if(s.size()>=2){

x = s.top(); s.pop(); x += s.top(); s.pop(); i++; break;

}

else

return 0;

case '-':

if(s.size()>=2){

x = s.top(); s.pop(); x =s.top()-x; s.pop(); i++; break;

}

else

return 0;

case '*':

if(s.size()>=2){

x = s.top(); s.pop(); x *= s.top(); s.pop(); i++; break;

}

else

return 0;

case '/':

if(s.size()>=2){

if( s.top()==0) return 0;

else{

x = s.top(); s.pop(); x = s.top()/x; s.pop(); i++; break;

}

else

return 0;

default :

x = 0;

while('0' <= s2[i]&&s2[i] <= '9'){

x = x*10+s2[i] - '0';

i++;

}

if(s2[i] == '.'){

double k = 10.0;

y = 0;

i++;

while('0' <= s2[i]&&s2[i] <= '9'){

y += ((s2[i]-'0')/k);

i++;

k *= 10;

}

x += y;

}

break;

}

if(x!=0)

s.push(x);

}

if( s.size()==1 )

return s.top();

else

return 0;

}

2、利用堆栈来实现中缀表达式转换为后缀表达式。

#include

using namespace std;

int cmp(char ch){ // 运算符优先级

switch(ch)

{

case '+':

case '-': return 1;

case '*':

case '/': return 2;

default : return 0;

}

void change(string &s1, string &s2){ // 中缀表达式转变后缀表达式

stack s;

s.push('#');

int i = 0;

while(i < s1.length()){ //分成四个级别来检验中缀表达式//s1.length()是为了s1的长度，不包括\0

if(s1[i] == '(') //级别一

s.push(s1[i++]);

else if(s1[i] == ')'){ //级别二

while( s.top() != '(' ){

s2 += s.top();

s2 += ' ';

s.pop();

}

s.pop();

i++;

}else if( s1[i] == '+'||s1[i] == '-'||s1[i] == '*'||s1[i] == '/' ){ //级别三

while( cmp(s.top()) >= cmp(s1[i]) ){

s2 += s.top();

s2 += ' ';

s.pop();

}

s.push(s1[i]);

i++;

}

else{ //级别四

while('0' <= s1[i]&&s1[i] <= '9'||s1[i] == '.'){

s2 += s1[i++];

}

s2 += ' ';

}

while(s.top() != '#'){ //最后一步

s2 += s.top();

s2 += ' ';

s.pop();

}

double value(string &s2){ // 计算后缀表达式，得到其结果。

stack s;

double x,y;

int i = 0;

while(i < s2.length()-1){ //由于s2的最后一位是空格，影响判断，所以用s2.length()-1

if(s2[i] == ' ')

i++;

switch(s2[i])

{

case '+': if(s.size()>=2){ x = s.top(); s.pop(); x += s.top(); s.pop(); i++; break; }

else return 0;

case '-': if(s.size()>=2){x = s.top(); s.pop(); x =s.top()-x; s.pop(); i++; break; }

else return 0;

case '*': if(s.size()>=2){x = s.top(); s.pop(); x *= s.top(); s.pop(); i++; break; }

else return 0;

case '/': if(s.size()>=2){x = s.top(); s.pop(); x = s.top()/x; s.pop(); i++; break; }

else return 0;

default :

{

x = 0;

while('0' <= s2[i]&&s2[i] <= '9'){

x = x*10+s2[i] - '0';

i++;

}

if(s2[i] == '.'){

double k = 10.0;

y = 0;

i++;

while('0' <= s2[i]&&s2[i] <= '9'){

y += ((s2[i]-'0')/k);

i++;

k *= 10;

}

x += y;

}

break;

}

s.push(x);

}

if( s.size()==1 )

return s.top();

else

return 0;

}

int main(){

string s1,s2;

cout<<"输入（中缀表达式）：";

cin>>s1;

s2="";

change(s1,s2);

if(value(s2)){

cout<<"输出1（后缀表达式）：";

cout<

cout<<"输出2（表达式的值）：";

cout<

}

else

cout<<"A wrong input!"<

return 0;

}

数据结构算术表达式求值实验报告

软件技术基础实验报告实验名称：表达式计算器系别：通信工程年级：班级：学生学号：学生姓名：《数据结构》课程设计报告题目简易计算表达式的演示【题目要求】要求：实现基本表达式计算的功能输入：数学表达式，表达式由整数和“+”、“-”、“×”、“/”、“（”、“）”组成输出：表达式的值基本操作：键入表达式，开始计算，计算过程和结果记录在文档中难点：括号的处理、乘除的优先级高于加减

1．前言在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为+、-*、/、=，用#表示结束。算法输出：表达式运算结果。算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。 2．概要设计 2.1 数据结构设计任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top 指示栈顶元素在顺序栈中的位置，base 为栈底指针，在顺序栈中，它始终指向栈底，即top=base 可作为栈空的标记，每当插入新的栈顶元素时，指针top 增1，删除栈顶元素时，指针top 减1。 2.2 算法设计为了实现算符优先算法。可以使用两个工作栈。一个称为OPTR ，用以寄存运算符，另一个称做OPND ，用以寄存操作数或运算结果。 1.首先置操作数栈为空栈，表达式起始符”#”为运算符栈的栈底元素； 2.依次读入表达式，若是操作符即进OPND 栈，若是运算符则和OPTR 栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即OPTR 栈的栈顶元素和当前读入的字符均为”#”）。 2.3 ADT 描述 ADT Stack{ 数据对象：D={ i a |i a ∈ElemSet,i=1,2,…，n, n ≧0} 数据对象：R1={< 1 ,-i i a a >| 1-i a ,D a i ∈,i=2,…，n}

数据结构表达式求值实验报告

竭诚为您提供优质文档/双击可除数据结构表达式求值实验报告篇一：数据结构实验二——算术表达式求值实验报告《数据结构与数据库》实验报告实验题目算术表达式求值学院：化学与材料科学学院专业班级：09级材料科学与工程系pb0920603 姓学邮名：李维谷号：pb09206285箱： liwg@https://www.doczj.com/doc/804632503.html,指导教师：贾伯琪实验时间：20XX年10月10日一、需要分析问题描述：表达式计算是实现程序设计语言的基本问题之一，它的实现是栈的应用的一个典型例子。设计一个程序，演示通过将数学表达式字符串转化为后缀表达式，并通过后缀表达式结合栈的应用实现对算术表达式进行四则混合运算。

问题分析：在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。设置运算符栈（字符型）和运算数栈（浮点型）辅助分析算符优先关系。在读入表达式的字符序列的同时完成运算符和运算数的识别处理，然后进行运算数的数值转换在进行四则运算。在运算之后输出正确运算结果，输入表达式后演示在求值中运算数栈内的栈顶数据变化过程，最后得到运算结果。算法规定：输入形式：一个(:数据结构表达式求值实验报告)算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为使实验更完善，允许操作数为实数，操作符为（、）、.（表示小数点）、+、-、*、/、^（表示乘方），用#表示结束。输出形式：演示表达式运算的中间结果和整个表达式的最终结果，以浮点型输出。程序功能：对实数内的加减乘除乘方运算能正确的运算出结果，并能正确对错误输入和无定义的运算报错，能连续测试多组数据。测试数据：正确输入：12*（3.6/3+4^2-1）#

数据结构实验二——算术表达式求值实验报告

《数据结构与数据库》实验报告实验题目算术表达式求值学院：化学与材料科学学院专业班级：09级材料科学与工程系PB0920603 姓名：李维谷学号：PB09206285 邮箱：liwg@https://www.doczj.com/doc/804632503.html, 指导教师：贾伯琪实验时间：2010年10月10日一、需要分析问题描述：

表达式计算是实现程序设计语言的基本问题之一，它的实现是栈的应用的一个典型例子。设计一个程序，演示通过将数学表达式字符串转化为后缀表达式，并通过后缀表达式结合栈的应用实现对算术表达式进行四则混合运算。问题分析：在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。设置运算符栈（字符型）和运算数栈（浮点型）辅助分析算符优先关系。在读入表达式的字符序列的同时完成运算符和运算数的识别处理，然后进行运算数的数值转换在进行四则运算。在运算之后输出正确运算结果，输入表达式后演示在求值中运算数栈内的栈顶数据变化过程，最后得到运算结果。算法规定：输入形式：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为使实验更完善，允许操作数为实数，操作符为（、）、.（表示小数点）、+、-、*、/、^（表示乘方），用#表示结束。输出形式：演示表达式运算的中间结果和整个表达式的最终结果，以浮点型输出。程序功能：对实数内的加减乘除乘方运算能正确的运算出结果，并能正确对错误输入和无定义的运算报错，能连续测试多组数据。测试数据：正确输入：12*（3.6/3+4^2-1）# 输出结果：194.4

算术表达式求值演示程序

数理学院课程设计报告书课程名称数据结构课程设计设计题目算术表达式求值演示专业班级学号姓名指导教师

2014 年12 月

4.2.2 基本操作： InitStack(&S) 操作结果：构造一个空栈S。 GetTop(S) 初始条件：栈S 已存在。操作结果：用P 返回S的栈顶元素。Push(&S 初始条件：，ch) 栈S 已存在。操作结果：插入元素ch 为新的栈顶元素。 Pop(&S) 初始条件：栈S 已存在。操作结果：删除S 的栈顶元素。 In(ch) 操作结果：判断字符是否是运算符，运算符即返回1 Precede(c1, c2) 初始条件：c1,c2 为运算符。操作结果：判断运算符优先权，返回优先权高的。Operate(a,op,b) 初始条件：a,b 为整数，op为运算符。操作结果： a 与 b 进行运算，op 为运算符，返回其值。num(n) 操作结果：返回操作数的长度。EvalExpr() 初始条件：输入表达式合法。操作结果：返回表达式的最终结果。}ADT Stack 主程序的流程：

EvaluateExpression() 函数实现了对表达式求值的功能，main() 函数直接调用EvaluateExpression() 对输入的表达式求值输出。 4.2.3 函数的调用关系图

4.3 详细设计 4.3.1 ① . Precede(char c1,char c2)判断运算符优先权，返回优先权高的算符间的优先关系如下：算法伪代码如下： char Precede(char c1,char c2) { static char array[49]={ >', '>', '<', '<', '<', '>', '>', >', '>', '<', '<', '<', '>', '>', >', '>', '>', '>', '<', '>', '>', >', '>', '>', '>', '<', '>', '>', <', '<', '<', '<', '<', '=', '!', >', '>', '>', '>', '!', '>', '>', <', '<', '<', '<', '<', '!', '='}; // 用一维数组存储 49 种情况 switch(c1) { /* i 为下面 array 的横标 */ case '+' : i=0;break; case '-' : i=1;break; case '*' : i=2;break;

表达式求值算法实现

湖南人文科技学院计算机科学技术系课程设计说明书课程名称:数据结构课程代码:408024 题目: 表达式求值年级/专业/班:08级计算机科学与技术二班学生姓名: 黄胜李业芝黄自强黄沅涛姚洋学号:08408210 08408211 08408212

08408213 08408215 指导教师: 袁辉勇开题时间: 2009 年12 月21 日完成时间: 2010 年 1 月 1 日

目录摘要 (1) 一、引言 (3) 二、设计目的与任务 (3) 1、课程设计目的 (3) 2、课程设计的任务 (4) 三、设计方案 (4) 1、需求分析 (4) 2、概要设计 (4) 3、详细设计 (6) 4、程序清单 (13) 四、调试分析与体会 (17) 五、运行结果 (18) 六、结论 (20) 七、致谢 (21) 八、参考文献 (21)

摘要在高级语言环境中算术表达上的结果是通过语言环境预设的算法的思想计算出来的，然而高级语言初学者并不了解表达式的计算过程和方法。本文采用算符优先分析和堆栈的方法给出了算术表达式的计算过程。所以本次课程设计的程序是在Windows系统上为用户解决包括加、减、乘、除以及括号在内的四则混合运算。用户可通过键盘输入四则运算，经过程序运行之后，可以判断出用户所输入的表达式是否正确。如果正确，就给出表达式的值；如果不正确，就提示输入有误。关键词：四则混合运算；高级语言；栈 Abstract The arithmetic expression result is the algorithm thought which supposes in advance through the language environment calculatesin the higher order language environment,however the higher order language beginner does not understand the expression the computationprocess and the method. This article used the operator first to analyze and the storehouse method has given the arithmetic expression computa-tion process. Therefore, the procedure in this curriculum design is the solution for users on Windows systems, including add, subtract, multiply, divide and brackets, including four hybrid operation. Users can enter via the keyboard 4 operation, after a program is running, you can determine the user entered expression is correct. If correct, it gives the value of the expression; if not correct, it prompted an error.

中缀表达式求值

江西理工大学软件学院计算机类课程实验报告课程名称：数据结构班级：11软件会计4班姓名：黄健学号：11222122 江西理工大学软件学院

一、目录（中缀表达式求值） 1、目录--------------------------------------------------------------2 2、实验目的--------------------------------------------------------3 3、实验要求--------------------------------------------------------3 4、实验仪器设备与材料-----------------------------------------3 5、实验原理--------------------------------------------------------4 6、实验步骤--------------------------------------------------------5 7、实验原始记录--------------------------------------------------6 8、实验数据分析计算结果--------------------------------------10 9、实验心得体会--------------------------------------------------11 10、思考题----------------------------------------------------------12

栈的应用表达式求值的设计

数据结构课程设计报告栈的应用：表达式求值专业计算机科学与技术学生姓名班级学号指导教师完成日期 2014年7月4日

表达式求值的设计目录 1设计内容 (1) 2设计分析 (1) 2.1后缀表达式设计 (1) 2.2 中缀到后缀的转换设计 (2) 3设计实践 (3) 3.1实现要求 (3) 3.2程序代码 (3) 4测试方法 (17) 4.1测试目的 (17) 4.2 测试输入 (17) 4.3 正确输出 (18) 4.4 实际输出 (18) 5程序运行效果 (18) 6设计心得 (19)

栈的应用：表达式求值的设计 1设计内容设计一个表达式求值的程序。该程序必须可以接受包含(,),+,-,*,/,%,和^（求幂运算符，a^b=a b）的中缀表达式，并求出结果。如果表达式正确，则输出表达式的结果；如果表达式非法，则输出错误信息。输入要求：程序从“input.txt”文件中读取信息，在这个文件中如果有多个中缀表达式，则每个表达式独占一行，程序的读取操作在文件在文件的结尾处停止。输出要求：对于每个表达式，将其结果放在“output.txt”文件的每一行中。这些结果可能是值，也可能是错误信息“ERROR IN INFIX NOTATION”。 2 设计分析在计算机中，算术表达式的计算往往是通过使用栈来实现的。所以，本表达式求值程序的最主要的数据结构就是栈。可以使用栈来存储输入表达式的操作符和操作数。输入的表达式是由操作数（又称运算对象）和运算符以及改变运算次序的圆括号连接而成的式子。算术表达式有中缀表示法和后缀表示法，本程序输入的表达式采用中缀表示法，在这种表达式中，二元运算符位于两个操作数中间。由于不同运算符之间存在优先级，同一优先级的运算间又存在着运算结合顺序的问题，所以简单的从左到右的计算是不充分的。当然凭直观判断一个中缀表达式中哪个运算符最先，哪个次之，哪个最后并不困难，但通过计算机处理就比较困难了。因为计算机只能一个字符一个字符地扫描，要想知道哪个运算符先算，就必须对整个中缀表达式扫描一遍。而后缀表达式则很容易通过应用栈实现表达式的计算，这为实现表达式求值程序提供了一种直接的计算机制。 2.1后缀表达式设计后缀表达式是由一系列的运算符、操作数组成的表达式，其中运算符位于两个操作数之后。后缀表达式很容易通过应用栈实现表达式的计算。其基本过程是：当输入一个操作数时，它被压入栈中，当一个运算符出现时，就从栈中弹出适当数量的操作数，对该运算进行计算，计算结果再压回栈中。对于最常见的二元运算符来说，弹出的操作数只有两个。处理完整个后缀表达式之后，栈顶上的元素就是表达式的结果值。整个计算过程不需要理解计算的优先级规则。

实验2 栈和队列的应用-算术表达式求值

1.实验题目栈和队列的应用 2.实验内容算术表达式求值 3.实验目的掌握栈和队列的概念及工作原理，运用其原理完成实验题目中的内容。 4.实验要求为了更好的掌握与理解课堂上老师所讲的概念与原理，实验前要认真预习所做的实验内容及编写源程序伪码（写在纸上及盘中均可）以便在实验课中完成老师所布置的实验内容。 5.概要设计原理 6.详细程序清单及注释说明 #include #include #include #include #define NULL 0 #define OK 1 #define OVERFLOW -2 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 20 /* 定义字符类型栈*/ typedef struct { int stacksize; char *base; char *top; }SqStack; /* ----------------- 全局变量--------------- */ SqStack OPTR,OPND;// 定义运算符栈和操作数栈 char expr[255]; /* 存放表达式串*/ char *ptr=expr; int InitStack(SqStack *s) //构造运算符栈 { s->base=(char *)malloc(STACK_INIT_SIZE*sizeof(char)); if(!s->base) exit(OVERFLOW);

s->top=s->base; s->stacksize=STACK_INIT_SIZE; return OK; } char In(char ch) //判断字符是否是运算符，运算符即返回1 { return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#'); } int Push(SqStack *s,char ch) //运算符栈插入ch为新的栈顶元素{ *s->top=ch; s->top++; return 0; } char Pop(SqStack *s) //删除运算符栈s的栈顶元素，用p返回其值{ char p; s->top--; p=*s->top; return p; } char GetTop(SqStack s)//用p返回运算符栈s的栈顶元素 { char p=*(s.top-1); return p; } /* 判断运算符优先权，返回优先权高的*/ char Precede(char c1,char c2) { int i=0,j=0; static char array[49]={ '>', '>', '<', '<', '<', '>', '>', '>', '>', '<', '<', '<', '>', '>', '>', '>', '>', '>', '<', '>', '>', '>', '>', '>', '>', '<', '>', '>', '<', '<', '<', '<', '<', '=', '!', '>', '>', '>', '>', '!', '>', '>', '<', '<', '<', '<', '<', '!', '='};

表达式求值课程设计报告

表达式求值课程设计报告表达式求值《数据结构》课程设计报告题目: 栈的应用:表达式求值 (系): 信息科学与工程学院院专业班级: 软件工程1102班学生姓名: 学号: 指导教师: 20 13 年 6 月 8 日至20 13 年 6 月 21 日表达式求值目录目录 (2) 1 概述 (1) 1.1 课程设计目的 (1) 1.2 课程设计内容 (1) 2 系统需求分析 ...................................................... 1 2.1 系统目标 (1) 2.2 主体功能 (1) 2.3 开发环境 (1) 3 系统概要设计 .................................................... 2 3.1 系统的功能模块划分 (2)

3.2 系统流程图 (2) 4系统详细设计 ..................................................... 3 5 测试 ............................................................ 6 5.1 测试方案 (6) 5.2 测试结果 (6) 6 小结 ............................................................ 8 参考文献 .......................................................... 9 附录1 源程序清单 (10) 2 数据结构课程设计报告(2012) 表达式求值 1 概述 1.1 课程设计目的 1(要求学生达到熟练掌握C语言的基本知识和技能。 2(了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。 3(提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 4(培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。

算术表达式求值课程设计报告

课程设计教学院课程名称题目专业班级姓名同组人员指导教师 2013 年 6 月22 日 (完成时间)

目录一．概述 (2) 二．总体方案设计 (4) 三．详细设计 (6) 四．程序的调试与运行结果说明 (14) 五．课程设计总结 (14) 六．附录 (16) 参考文献 (3233) （“目录”要求必须自动生成）

一概述（宋体，三号，加粗，居中） 1.课程设计的目的（小标题，宋体，四号，加粗，左对齐顶格）（1）．理解和掌握该课程中的有关基本概念，程序设计思想和方法。（2）．培养综合运用所学知识独立完成课题的能力。（3）．培养勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人员应具有的素质。（4）．掌握从资料文献、科学实验中获得知识的能力，提高学生从别人经验中找到解决问题的新途径的悟性，初步培养工程意识和创新能力。 2.课程设计的要求算术表达式求值程序实现以下功能： (1)构造一个空栈S,初始条件：栈S已存在 (2)用P返回S的栈顶元素 (3)插入元素ch为新的栈顶元素 (4)删除S的栈顶元素 (5)判断字符是否是运算符，运算符即返回1 (6)判断运算符优先权，返回优先权高的 (7)输入表达式 (8)返回表达式的最终结果。

二总体方案设计 a)需求分析该程序能实现算术四则运算表达式的求值，显示运算过程。输入的形式：表达式，例如5*（3+7）#。包含的运算符只能有'+'、 '-'、'*'、 '/'、 ' (' ') '；程序所能达到的功能：对表达式求值并输出。 b)总体设计本程序使用的是编程工具是Visual c++ 6.0，实现了运算器的功能和仿真界面（大体界面如下图所示）。在基本要求的基础上，运算数可以是实数类型，同时增加了乘方运算的功能；可以实现对负数的运算，例如用户输入表达式6* （-0.25）,则程序会在负号的前面自动加上一个0。 1)算符包括加（+）、减（-）、乘（*）、除（/）、乘方（^）；另一个称作 OPND，用以寄存操作数和运算结果，操作数可以是float型的浮点数。算法的基本思想是： 2)首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；依次读入表达式中的每个字符，若是操作数（浮点数）则进OPND栈，若是运算符（+、—、*、/、^）则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）。 3)编写一个原型为void strtofloat(char str[ ],int n,int i)，把一个数字串转换为一个实型数，并压入运算数栈中。（整个程序的源代码见附录，并有具体解释）

数据结构课程设计报告-中缀算术表达式求值

课程设计报告课程名称数据结构课题名称中缀算术表达式求值专业通信工程班级通信0902 学号姓名指导教师 2011 年07 月01 日

湖南工程学院课程设计任务书课程名称数据结构课题中缀算术表达式求值专业班级通信工程0902 学生姓名学号指导老师审批任务书下达日期2011 年06 月27日任务完成日期2011 年07 月01日

设计要求： 1. 课程设计报告规范（1）需求分析 a.程序的功能。 b.输入输出的要求。（2）概要设计 a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。 b.课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。（3）详细设计 a.采用C语言定义相关的数据类型。 b．写出各模块的类C码算法。 c.画出各函数的调用关系图、主要函数的流程图。（4）调试分析以及设计体会 a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。 b.程序调试中遇到的问题以及解决问题的方法。 c.课程设计过程经验教训、心得体会。（5）使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。（6）书写格式 a.设计报告要求用A4纸打印成册： b.一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。（7）附录源程序清单（带注释）

2. 考核方式指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分：（1）平时出勤（占10%）（2）系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）（3）程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）（4）设计报告（占30%）注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。（5）独立完成情况（占10%）。 3 . 课程验收（1）运行所设计的系统。（2）回答有关问题。（3）提交课程设计报告。（4）提交软盘（源程序、设计报告文档）。（5）依内容的创新程度，完善程序情况及对程序讲解情况打分。 2 进度安排第19 周：星期一8：00——12：00 上课星期一14：30——18：30 上机星期二14：30——18：30 上机星期四8：00——12：00 上机附：课程设计报告装订顺序：封面、任务书、目录、正文、评分表、附件（A4大小的图纸及程序清单）。正文的格式:一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。正文的内容:一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现

基于栈结构的中缀表达式求值

实验3：栈与队列实验 ——基于栈结构的中缀表达式求值一、问题描述从键盘输入任意中缀表达式字符串，读字符串，利用栈结构实现表达式求值。二、输入与输出输入：从键盘中缀表达式如： 32＋5×（6－4）输出：计算结果42 三、需求分析 1.定义两个栈结构，数栈用于存放表达式中的数，符号栈用于存放表达式中的符号，实现栈的运算 2.在读数的时候考虑多位运算 3.实现表达式求值四、开发工具与环境硬件设备：微型计算机系统软件环境：操作系统Windows 开发工具：Devc++ 五、概要设计参考结构定义 typedef struct /* 运算符栈 */ { char *base,*top; int stacksize; }SqStack; typedef struct /* 运算数栈 */ { int *base,*top; int stacksize; }SqStack1; int priority[7][7]={{'>', '>', '<', '<', '<', '>', '>'}, // + {'>', '>', '<', '<', '<', '>', '>'}, // -

{'>', '>', '>', '>', '<', '>', '>'}, // * {'>', '>', '>', '>', '<', '>', '>'}, // / {'<', '<', '<', '<', '<', '=', ' '}, // ( {'>', '>', '>', '>', ' ', '>', '>'}, // ) {'<', '<', '<', '<', '<', ' ', '='} // # }; /*用于比较符号优先级的全局二维数组*/ 2．各函数模块 void InitStack(SqStack *s); 操作结果：初始化运算符栈 char GetTop(SqStack *s); 操作结果：得到运算符栈的栈顶元素 void Push(SqStack *s,char e); 操作结果：对运算符栈进行压栈操作 int IsNumber(char c); 操作结果：判断一个字符是否是数字 int MidExpression_Eval(char Express[]); 操作结果：计算中缀表达式的值 int Operate (int a,char x,int b); 操作结果：计算表达式axb，并返回结果六、详细设计 #include #include using namespace std; /*定义区*/ #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OVERFLOW -1 #define ERROR 0 #define OK 1 //运算符栈 typedef struct { char *base, *top; int stacksize; }SqStack; //运算数栈 typedef struct { int *base, *top; int stacksize;

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

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[]);//将中缀表达式转化为后缀表达式float ComputeExpress(char s[]);//计算后缀表达式的值 void main() { char a[MaxSize],b[MaxSize]; float f; printf("请输入一个算术表达式:\n"); gets(a); printf("中缀表达式为：%s\n",a); TranslateExpress(a,b); printf("后缀表达式为：%s\n",b); f=ComputeExpress(b); printf("计算结果：%f\n",f); } void InitStack(SeqStack *S)//初始化栈

算术表达式求值课设报告

数据结构课程设计设计说明书表达式求值算法的实现（（（）（）（（学生姓名学号班级成绩指导教师数学与计算机科学学院 2012年 9月 7日

数据结构课程设计评阅书

课程设计任务书 2011—2012学年第2学期专业学号：姓名：课程设计名称：数据结构课程设计设计题目：表达式求值算法的实现完成期限：自 2012 年 8 月 28 日至 2012 年 9 月 7 日共 2 周栈的存储和相关运算是数据结构中数组部分的重点知识和技能。表达式求值算法可借助栈来完成，它的存储可以使用顺序结构也可以使用链式结构，这要根据具体的应用来决定。本课程设计按以下的要求运用C/ C++结构体、指针、数据结构等基知识编程实现。任务要求：1）阐述设计思想,画出流程图;2）任意输入一个表达式（算术、逻辑、关系表达式）；3）建立栈；4）借助栈的相关运算完成表达式求值过程;5）将表达式及其运算结果按照其数学形式打印输出; 6）说明测试方法,写出完整的运行结果,较好的界面设计；7）按照格式要求完成课程设计说明书。设计要求: 1）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？确定问题的输入数据集合。 2）逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的功能说明），各个主要模块的算法，并画出模块之间的调用关系图； 3）详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架； 4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚； 5）程序调试与测试：能够熟练掌握调试工具的各种功能，设计测试数据确保程序正确。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果； 6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析； 7）编写课程设计报告；指导教师（签字）：教研室主任（签字）：批准日期：年月日

c语言实现一.二叉树操作二.用栈实现算术表达式求值课设报告

目录题目一.二叉树操作（1）二.算术表达式求 (1) 一、课程设计的目的 (1) 二、课程设计的内容和要求 (1) 三、题目一设计过程 (2) 四、题目二设计过程 (6) 五、设计总结 (17) 六、参考文献 (18)

题目一.二叉树操作（1）二.算术表达式求一、课程设计的目的本学期我们对《数据结构》这门课程进行了学习。这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计实习。这次课程设计不但要求学生掌握《数据结构》中的各方面知识，还要求学生具备一定的C语言基础和编程能力。（1）题目一的目的： 1、掌握二叉树的概念和性质 2、掌握二叉树的存储结构 3、掌握二叉树的基本操作（2）题目二的目的： 1、掌握栈的顺序存储结构和链式存储结构 2、掌握栈的先进后出的特点 3、掌握栈的基本运算二、课程设计的内容和要求（1）题目一的内容和要求： 1、编写已知二叉树的先序、中序序列，恢复此二叉树的程序 2、编写求二叉树深度的程序（2）题目二的内容和要求： 1、算术表达式由操作数、运算符和界限符组成。操作数是正整数，运算符为加减乘除，界限符有左右括号和表达式起始 2、将一个表达式的中缀形式转化为相应的后缀形式 3、依据后缀表达式计算表达式的值

三、题目一设计过程 1、题目分析现已知一棵二叉树的先序遍历序列和中序遍历序列，依次从先序遍历序列中取结点，由先序序列确定根结点(就是第一个字母)，每次取出一个结点就与中序遍历的序列进行比较，当相等的时候，中序遍历序列就被分成以该结点为根的二叉树子树，该结点左部分为左子树，右部分为右子树，直到取完先序列里的所有结点，则二叉树构造完毕（树用链式存储结构存储），用递归实现！由建好的二叉树，先判断这棵树是否为空，若不为空则找数的左子树，统计它的高度，然后找树的右子树，统计它的高度，比较左子树和右子树的高度，然后返回其中大的那个值加一，则求出数的高度。这里用递归实现！ 2、算法描述 main ( )（主函数）先构造一颗二叉树，初始化为空，用来存储所构造的二叉树，并输入一棵树的先序序列和中序序列，并统计这个序列的长度。然后调用实现功能的函数。 void CreateBiTree(BiTree *T,char *pre,char *in,int len)（由先序序列和中序序列构造二叉树）根据前序遍历的特点, 知前序序列(pre)的首个元素(pre[0])为根(root), 然后在中序序列(in)中查找此根(pre[0]), 根据中序遍历特点, 知在查找到的根(root) 前边的序列为左子树, 后边的序列为右子树。设根前边有n个元素，则又有, 在前序序列中，紧跟着根(root)的n个元素序列(即pre[1...n]) 为左子树, 在后边的为右子树，而构造左子树问题其实跟构造整个二叉树问题一样，只是此时前序序列为pre[1...n]), 中序序列为in[0...n-1], 分别为原序列的子串, 构造右子树同样。这里用递归实现！ int Depth(BiTree T)（求树的深度）当所给的参数T是NULL时，返回0。说明这个树只有一个叶子节点深度为0，当所给的参数不是NULL时，函数调用自己看看这个参数的左分支是不是NULL，

四则运算表达式求值(栈+二叉树,c++版)

HUNAN UNIVERSITY 课程实习报告题目：四则运算表达式求值学生姓名：周华毅学生学号：201308010411 专业班级：计科1304 指导老师：吴帆完成日期：2015/5/1

一、需求分析 a)四则运算表达式求值，将四则运算表达式用中缀表达式表示，然后转换为后缀表达式，并计算结果。 b)本程序要求利用二叉树后序遍历来实现表达式的转换，同时可以使用实验2的结果来求解后缀表达式的值。 c)在字符界面上输入一个中缀表达式，回车表示结束。如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。 d)测试数据输入： 21+23*（12-6）输出： 21 23 12 6 -*+ 二、概要设计抽象数据类型为实现上述程序的功能，应以字符串存储用户的输入，以及计算出的结果。算法的基本思想根据题目要求，利用二叉树后序遍历来实现表达式的转换。该算法的基本模块包括二叉树的建立以及如何把输入的中缀表达式利用二叉树后序遍历转化为后缀表达式。 1、首先要将输入的中缀表达式（数字字符）存入到二叉树中，由于存在两位或者两位以上的数，甚至还有小数，所以考虑用字符型指针存储数字字符和操作符。 2、为了便于将中缀表达式存入二叉树中，在录入中缀表达式后，要进行相应的处理，比如去掉空格符，添加结束标志，如‘=’、‘#’等。 3、中缀表达式存入到二叉树的过程中，要注意处理的顺序，如‘+’、‘-’号的优先级比‘*’、‘/’号的低，当遇到‘*’、‘/’号时，要判断树以上的节点中是否有‘+’、‘-’号，有的话要与其交换位置。遇到‘（’时要反复创建二叉树的结点，构建子二叉树，考虑到括号内要处理的步骤可能会较多，可以考虑用递归。遇到‘）’时则直接结束此子二叉树的建立。此外二叉树中叶子结点存储操作数，非叶子结点存储操作码。 4、对创建好的二叉树进行后序遍历，即可得到相应的后缀表达式，实现方法可以用递归的方式，由于后面还要计算表达式的值，故便利的过程中要将结点中得到的数据存入新的字符数组中。程序的流程程序由三个模块组成：（1）输入模块：完成一个中缀表达式的输入，存入字符串数组array[Max]中。（2）计算模块：设计一个建立二叉树的函数，Node* crtTree(Node* root)，传入根结点指针，返回根结点指针，该函数的实现还要反复使用另一个函数char getOp(Node *temp)，其将数字字符存入一个结点，并返回数字字符的后一个符号。void deal()函数功能是对字符数组进行处理。void output(Node *root); 函数功能是获得处理后的字符串，也就是中缀表达式转化为的后缀表达式。（3）输出模块：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式和表达式的值；如果不正确，在字符界面上输出表达式错误提示。三、详细设计

文档之家

四则运算表达式求值(栈+二叉树,c++版)

数据结构算术表达式求值实验报告

数据结构表达式求值实验报告

数据结构实验二——算术表达式求值实验报告

算术表达式求值演示程序

表达式求值算法实现

中缀表达式求值

栈的应用表达式求值的设计

实验2 栈和队列的应用-算术表达式求值

表达式求值课程设计报告

算术表达式求值课程设计报告

数据结构课程设计报告-中缀算术表达式求值

基于栈结构的中缀表达式求值

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

算术表达式求值课设报告

c语言实现一.二叉树操作 二.用栈实现算术表达式求值 课设报告

最新《数据结构》算术表达式求值

四则运算表达式求值(栈+二叉树,c++版)

c语言实现一.二叉树操作二.用栈实现算术表达式求值课设报告