后缀表达式求值_数据结构设计

表达式求值（数据结构-栈的应⽤）⼀.问题描述：限制：只含有‘+’，‘-’，‘*’，‘/ ’和圆括号,正整数。

表⽰：字符数组，栈。

中缀表达式：在程序语⾔中，运算符位于两个运算数中间的表达式称为中缀表达式，例如 1+2*3.中缀表达式运算规则：先乘除，后加减，从左到右，先括号内，后括号外，因此中缀表达式不仅要判断运算符的优先级，⽽且还有处理括号。

后缀表达式：运算符在运算数的后⾯，如1+2*3的后缀表达式：1 2 3*，在后缀表达式中已经考虑了运算符的优先级，没有括号，只有运算数和运算符。

后缀表达式的运算：按照运算符的次序进⾏的。

例如123*+，从左到右扫描时，第⼀个运算符为*，先执⾏2*3=6，第⼆个运算符为‘+’，执⾏1+6=7。

⼆ .表达式求值的过程：将算术表达式转换成后缀表达式，然后对后缀表达式求值。

1.将算术表达式转换为后缀表达式。

（1）从左到右⼀次扫描中缀表达式的每⼀个字符，如果是字符串，直接写⼊后缀表达式。

（2）如果遇到的是' ( '，则压⼊操作符栈，遇到‘（’时，将栈中的元素放到后缀表达式中，直达栈顶元素为'('时，将栈顶元素'('删除，不需要⼊栈。

（3）如果遇到的是操作符，则将操作符和操作符栈顶元素⽐较。

：如果a[i]的运算符的优先级⼩于等于栈顶元素的优先级，退栈运算符并放到后缀表达式中，直到a[i]的运算符优先级⼤于栈顶运算符的优先级：否则⼊栈。

（4）重复上述步骤，知道中缀表达式的结束符标记“#”，转换结束。

我的代码：#include<bits/stdc++.h>using namespace std;stack<char>f;//操作符栈stack<double>s;//操作数栈bool flag;int prior(char ch)//运算符的优先级{switch(ch){case'+':case'-':return 1;case'*':case'%':case'/':return 2;default:return 0;//括号}}string trans(string a){while(!f.empty()) f.pop();f.push('#');string ret="";//保存中缀表达式int len=a.size(),i=0;while(i<len){if(a[i]==' '||a[i]=='=')//??{i++;continue;}else if(a[i]=='(')f.push(a[i++]);else if(a[i]==')'){while(f.top()!='('){ret+=f.top();ret+=' ';f.pop();}f.pop();//(出栈i++;}else if(a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/'||a[i]=='%'){while(prior(f.top())>=prior(a[i]))//如果a[]的运算符的优先级⼩于等于栈顶元素的优先级，退栈运算符并放到后缀表达式中，直到a[i]的运算符优先级⼤于栈顶运算符的优先级ret+=f.top();ret+=' ';f.pop();}f.push(a[i++]);}else{while((a[i]>='0'&&a[i]<='9')||a[i]=='.'){ret+=a[i++];}ret+=' ';}}while(f.top()!='#'){ret+=f.top();ret+=' ';f.pop();}ret+='=';return ret;}double cal(double a,double b,double ch)//计算{if(ch=='+') return a+b;if(ch=='-') return a-b;if(ch=='*') return a*b;if(ch=='%') return ((int)a%(int)b);if(ch=='/'){if(b!=0)return a/b;flag=true;return 0;}}double solve(string a)//后缀表达式计算{string t=trans(a);while(!s.empty()) s.pop();flag=false;int len=t.length(),i=0;while(i<len){if(t[i]==' '||t[i]=='='){i++;continue;}else if(t[i]=='+'||t[i]=='-'||t[i]=='*'||t[i]=='/'||t[i]=='%') {double num1,num2;num1=s.top();s.pop();num2=s.top();s.pop();s.push(cal(num1,num2,t[i]));i++;}else{double x=0;while(t[i]>='0'&&t[i]<='9'){x=x*10+t[i]-'0';i++;}if(t[i]=='.'){double k=10.0,y=0;i++;while(t[i]>='0'&&t[i]<='9'){y+=((t[i]-'0')/k);i++;k*=10;;}x+=y;}s.push(x);}}return s.top();}int main(){int num;scanf("%d",&num);while(num--){cin>>a;// cout<<e.trans(a)<<endl;//将中缀表达式装换为后缀表达式 cout<<solve(a)<<endl;}return 0;}。

一、设计思想（一）中缀转后缀的设计思想设计一个能实现表达式自动求值计算，算术表达式由操作数、算符和括号组成。

由于运算符的优先级不同还要考虑括号。

所以表达式不可能一直的从左到右进行，所以就借助栈来实现这个表达式的求值。

首先要把算术表达式变换成与之等值的无括号表达式，也就是中缀转后缀，它也是这个算法的关键。

设计两个栈，一个为字符型的，存放运算符，用以将算术表达式变成无括号的表达式；另一个浮点型的，存放操作数，用以对无符号的表达式进行求值。

我们要假设运算符的优先级：( ) , * /, + - 。

首先将一左括号‘(’入栈，作为栈底元素；接着从左到右对算术表达式进行扫描。

每次读一位，若遇到左括号‘（’，则进栈；若遇到的是操作数，则立即输出；若又遇到运算符，如果它的优先级比栈顶元素的优先级数高的话，则直接进栈，否则输出栈顶元素，直到新的栈顶元素的优先级数比它低的，然后将它压栈；若遇到是右括号‘）’，则将栈顶的运算符输出，直到栈顶的元素为‘（’，然后，左右括号互相底消；到设计的结束标志的时候表示表达式已经扫描完毕，表达式已经全部输入，将栈中的运算符全部输出，删除栈底的左括号。

以上完成了中缀表达式转后缀表达式，输出无括号的后缀表达式。

读后缀表达式，若遇数值，操作数进栈；若遇运算符，让操作数栈的栈顶和次栈顶依次出栈并与此运算符进行运算，运算结果入操作数栈；重复这个步骤，直到遇到结束标志，则此时栈中的结果便是所求的后缀表达式的值，接着输出结果。

以上就是设计这个算法的主要的思想。

(二) 直接计算的设计思想直接计算其实跟上一个相似，它是在上面扫两遍的思想进行修改的得来。

首先，要建立两个栈，一个为字符型的，存放运算符，另一个浮点型的，存放操作数，我们开始对表达式进行扫描。

首先要确定运算符的优先级：（、）、*、/、+、-。

如果扫描到的是数字符号，把它们转换成浮点型数据或其他可运算的数据类型，存入操作数栈中。

如果扫描到的是运算符号，第一个运算符进栈，遇到‘（’存入运算符栈中，我们按照第一种算法的方法将表达式依次扫描。

课程设计报告题目：计算表达式的值1.问题描述对于给定的一个表达式，表达式中可以包括常数、算术运行符（“+”、“-”、“*”、“/”）和括号，编写程序计算表达式的值。

基本要求：从键盘输入一个正确的中缀表达式，将中缀表达式转换为对应的后缀表达式，并计算后缀表达式的值。

对于表达式中的简单错误，能够给出提示，并给出错误信息；表达式中可以包括单个字母表示的变量。

测试数据：任意选取一个符合题目要求的表达式。

提高要求：（1）能够处理多种操作符。

（2）实现包含简单运算的计算器。

（3）实现一个包含简单运算和函数运算的计算器。

2.需求分析（1）软件的基本功能本软件实在win32工程下实现的带有界面和图标的功能较为齐全的计算器。

此计算器分三个方面进行计算，分别为数值表达式的计算，字母表达式的计算和函数计算。

可由键盘或用鼠标点击按键输入带有数字或字母的中缀表达式，程序可以将输入的带有数字或字母的中缀表达式转换成对应的后缀表达式，并计算只含有数字的后缀表达式的值。

本软件支持含小数、多位数等多种操作数的处理，可以计算含加、减、乘、除、百分号、求余、求幂，求阶乘，求三角函数的值等多种运算符和函数的表达式（2）输入/输出形式用户可通过打开图标弹出来的计算器界面任意点击操作。

对于在输入时发生的简单错误，软件通过弹出对话框给出提示并且在提示错误的同时自动将用户的出错输入略去转化成正确的表达式进行计算，用户也可选择清楚操作然后重新输入a.对于数值和函数表达式软件会输出其表达式的后缀表达式和计算结果并保留六位小数；b.对于字母表达式因字母无法进行数值运算，软件仅输出其后缀表达式的值；清楚按钮可以清楚有已经输入或输出的数据从头计算；软件窗口可实现最小化。

并且输入编辑框可进行修改，复制，粘贴等操作，但后缀表达式和求值结果的编辑框中的内容不可修改，只能执行复制操作。

（3）测试数据要求用户可以输入一个符合要求的中缀表达式，也可以输入一个包含简单错误的表达式。

《数据结构》课程设计报告书课程题目：表达式求值问题一.需求分析（1）以字符序列的形式从终端输入语法正确的不含变量的整数表达式，将该中缀表达式转换为后缀表达式。

（2）实现对后缀表达式的求值。

（3）演示在求值过程中运算符栈，操作数栈，输入字符和主要操作的变化过程。

二.概要设计表达式求值的算法分为两步进行：首先将中缀表达式转换为后缀表达式，再求后缀表达式的值。

（1）将中缀表达式转换为后缀表达式，对于字符串形式的合法的中缀表达式，“（”的运算优先级最高，“*”次之，“+”，“—”最低，同级运算符从左到右按顺序运算。

转化过程算法描述如下：从左到右对中缀表达式进行扫描，每次处理一个字符。

若遇到左括号入栈。

如遇到数字，原样输出。

若遇到运算符，如果它的优先级比栈顶元素优先级高，则直接入栈，否则栈顶元素出栈，直到新栈顶数据元素的优先级比它低，然后将它直接入栈。

重复以上步骤，直到表达式结束。

若表达式已全部结束，将栈顶元素全部出栈。

（2）后缀表达式求值算法描述如下：从左到右对后缀表达式进行扫描，每次处理一个字符。

若遇到数字，转化为整数，入栈。

若遇到运算符，出栈两个值进行运算，运算结果再入栈。

重复以上步骤，直到表达式结束，栈中最后一个数据元素就是所求表达式的结果。

三.详细设计#include<stdio.h>#include<stdlib.h>#define TRUE 1#define FALSE 0#define MAXNUM 100typedef int DataType;struct SeqStack{ DataType s[MAXNUM];int t;};typedef struct SeqStack *PSeqStack;PSeqStack createEmptyStack_seq(){PSeqStack pastack;pastack = (PSeqStack)malloc(sizeof(struct SeqStack)); if (pastack == NULL)printf("Out of space!!\n");elsepastack->t = -1;return pastack;} int isEmptyStack_seq(PSeqStack pastack){return pastack->t == -1;} void push_seq(PSeqStack pastack, DataType x){if (pastack->t >= MAXNUM - 1)printf("Overflow!\n");else{pastack->t = pastack->t + 1;pastack->s[pastack->t] = x;}} void pop_seq(PSeqStack pastack){if (pastack->t == -1)printf("Underflow!\n");elsepastack->t = pastack->t - 1;} DataType top_seq(PSeqStack pastack){return pastack->s[pastack->t];} int infixtoSuffix(const char * infix, char * suffix){ /*将中缀表达式转换为后缀表达式，顺利转换返回true，若转换过程中发现中缀表达式非法则返回false*/int state_int = FALSE;/*state_int记录状态，等于true表示刚读入的是数字字符，等于false表示刚读入的不是数字字符，设置这个变量是为了在每输出一个整数后输出一个空格，以免连续输出的两个整数混在一起。

ＸＸXＸXX大学《数据结构》课程设计报告班级：学号：姓名：指导老师:目录一算术表达式求值一、需求分析二、程序得主要功能三、程序运行平台四、数据结构五、算法及时间复杂度六、测试用例七、程序源代码二感想体会与总结算术表达式求值一、需求分析一个算术表达式就是由操作数(oｐeranｄ）、运算符(operator）与界限符（deｌimiter)组成得。

假设操作数就是正整数，运算符只含加减乘除等四种运算符,界限符有左右括号与表达式起始、结束符“#”，如：＃(7+15）*（2３—２8/４）#。

引入表达式起始、结束符就是为了方便.编程利用“算符优先法”求算术表达式得值.二、程序得主要功能（1）从键盘读入一个合法得算术表达式，输出正确得结果。

(2）显示输入序列与栈得变化过程。

三、程序运行平台Ｖｉsｕaｌ C＋+6、0版本四、数据结构本程序得数据结构为栈。

（1）运算符栈部分：struct SqStaｃk ／/定义栈{char *base； //栈底指针ｃｈａr *toｐ; ／/栈顶指针inｔstacｋsiｚe； //栈得长度};inｔInitSｔack (SqＳｔack &ｓ) //建立一个空栈S{ｉf （!(s、ｂａse= (char ＊）ｍalloc(5０＊ｓizeof（chａr）)）)exｉt（0）；ｓ、ｔop=s、bａse;s、staｃksiｚｅ=５0；retuｒn OK；}ｃhar GeｔTop（SqStack s,char &e) /／运算符取栈顶元素｛iｆ (s、ｔop==s、ｂase) //栈为空得时候返回EＲROR｛ﻩ prｉntf(＂运算符栈为空！＼n")；ﻩ reｔurn ERＲＯR;｝elsee＝*（s、ｔoｐ-1); //栈不为空得时候用ｅ做返回值，返回S得栈顶元素，并返回OK returnＯＫ;｝ｉnt Push(SqStacｋ＆s，cｈａr ｅ） //运算符入栈｛if （s、tｏp—s、baｓe >= ｓ、ｓtacksｉzｅ）ﻩ{ｐriｎtf（＂运算符栈满!＼n"）;ﻩs、basｅ=（cｈaｒ*）reａlloｃ(s、bａｓe，(s、sｔackｓｉze+5)*ｓizeoｆ(cｈar））；//栈满得时候,追加5个存储空间ｉf(！s、basｅ)exｉt （OVERＦＬOW）；s、top=s、ｂａsｅ+s、ｓｔacｋsize;s、ｓtaｃksiｚｅ+=５;}ﻩ＊(s、ｔop）＋＋=e；／/把e入栈ﻩｒeturn OK;}ｉnｔ Pop(SqStaｃk &ｓ，char ＆ｅ） /／运算符出栈｛ｉｆ (s、toｐ==s、base) ／/栈为空栈得时候，返回ERＲOＲ｛ｐrintf（＂运算符栈为空!\n”）;ﻩ return ERROＲ;}else｛ﻩﻩe=＊-—ｓ、tｏp；/／栈不为空得时候用e做返回值，删除S得栈顶元素，并返回ＯK return OK；}}iｎt StackTｒaｖerse（ＳqStacｋ&ｓ)／/运算符栈得遍历｛ﻩchar ＊t；ﻩt=s、ｂａｓｅ；ﻩif (s、top＝=s、baｓe）｛ﻩ printｆ（”运算符栈为空！\ｎ”)； //栈为空栈得时候返回ＥＲRORｒeturn ERＲOＲ;}ｗhile（t！＝s、tｏp)｛ﻩﻩｐrｉｎｔf（" %c",＊t)； //栈不为空得时候依次取出栈内元素t++;ﻩ}ｒeturｎ EＲRＯR；｝（2）数字栈部分：strｕｃt SqSｔackn//定义数栈｛ｉnt *bａse; //栈底指针ｉnt＊tｏp； //栈顶指针ｉnｔ sｔacksｉze； //栈得长度｝;inｔIｎｉtStackｎ (SqSｔackn &s) //建立一个空栈Ｓ{s、base=（int＊）malｌoc（50*sｉzeof(int）);if(！ｓ、ｂase）eｘiｔ（OVEＲFLＯW）；//存储分配失败s、top=s、base；s、stacksizｅ=5０;reｔuｒn OK；｝ｉｎt GｅtToｐn(ＳqＳtａcｋn s,inｔ＆e) //数栈取栈顶元素{if（s、ｔop=＝s、base）{prinｔｆ(＂运算数栈为空!\ｎ＂);//栈为空得时候返回ERRORﻩ rｅturｎ ERROR;}eｌseﻩe＝＊（s、toｐ-1);／/栈不为空得时候，用e作返回值，返回S得栈顶元素，并返回OＫreturｎＯK；｝int Pｕshn（SｑStａckn ＆s，int ｅ) //数栈入栈｛if（s、tｏp—s、ｂasｅ＞＝s、stacksiｚe)｛ﻩﻩprｉｎｔf（"运算数栈满!\ｎ"）；／/栈满得时候,追加5个存储空间ﻩs、base=(int＊）realloc (s、baｓe,(s、stａcksize＋5)＊sｉzｅof（ｉnt));ｉf（!s、base) ｅxit (ＯＶERFLOW)；ﻩs、top=ｓ、bａsｅ＋ｓ、stacｋsize;//插入元素e为新得栈顶元素s、stacksｉｚe+=5；}*（s、top）++=e; /／栈顶指针变化returｎOK;}ｉｎt Popｎ(ＳｑSｔacｋn ＆s，iｎt &e)//数栈出栈｛ﻩif （s、top=＝ｓ、base）｛ﻩ pｒiｎtｆ（"运算符栈为空！\n＂);//栈为空栈得视时候，返回ERRＯＲﻩ retｕrn ERROR；ﻩ｝ｅlse｛ﻩﻩe=＊—-ｓ、tｏp；／/栈不空得时候，则删除S得栈顶元素,用e返回其值，并返回OK ﻩreturｎOK；｝}ｉnt StacｋＴraveｒsｅn（SqStackn &s)/／数栈遍历{ﻩiｎｔ＊t;ﻩｔ=s、basｅ ;ﻩif（s、top==s、basｅ）ﻩ｛pｒinｔf(＂运算数栈为空！\n”）；//栈为空栈得时候返回ERRORﻩ rｅｔｕrn ERＲＯＲ；ﻩ｝ﻩwｈile（t！=ｓ、ｔop)ﻩ{priｎtf(” ％d”，*ｔ); /／栈不为空得时候依次输出t＋＋;｝return ERRＯR；｝五、算法及时间复杂度１、算法:建立两个不同类型得空栈,先把一个‘＃’压入运算符栈。

韶关学院
学生实验报告册
实验课程名称：数据结构与算法
实验项目名称：实验二后缀表达式求值
实验类型（打√）：（基础、综合、设计√）
院系：计算机科学学院专业：计算机科学技术姓名：*** 学号：*****
指导老师：***
韶关学院教务处编制
一、实验预习报告内容
二、实验原始（数据）记录
实验时间：2011 年9 月21 日（星期三第7，8 节）
实验同组人：
【程序运行结果】
通过分析输入数据和运行结果，证明程序顺利完成实验内容和要求。

指导教师
批阅及签名签名：年月日
三、实验报告内容
2011年9 月21 日
注：1、如有个别实验的实验报告内容多，实验报告册页面不够写，或有识图，画图要求的，学生应根据实验指导老师要求另附相同规格的纸张并粘贴在相应的“实验报告册”中。

2、实验报告册属教学运行材料，院系（中心）应按有关规定归档保管。

数据结构表达式求值实验报告数据结构表达式求值实验报告1. 引言表达式求值是计算机科学中的一个重要问题，也是数据结构的一个经典应用。

通过将中缀表达式转换为后缀表达式，并利用栈这一数据结构，可以实现对表达式的有效求值。

本实验旨在探究数据结构在表达式求值中的应用。

2. 实验内容本实验中，我们将实现一个表达式求值的程序。

具体步骤如下：1. 将中缀表达式转换为后缀表达式。

2. 使用栈来求解后缀表达式。

3. 算法原理3.1 中缀表达式转后缀表达式中缀表达式是我们常见的数学表达式，如 2 + 3 4。

而后缀表达式是将操作符放在操作数后面的表达式，上述中缀表达式的后缀表达式为 2 3 4 +。

中缀表达式到后缀表达式的转换可以通过以下步骤完成：1. 初始化一个栈和一个输出队列。

2. 从左到右遍历中缀表达式的每个字符。

3. 如果当前字符是数字，将其加入输出队列。

4. 如果当前字符是左括号，将其压入栈。

5. 如果当前字符是右括号，将栈中的操作符依次弹出并加入输出队列，直到遇到左括号为止。

6. 如果当前字符是操作符，将其与栈顶操作符进行比较：1. 如果栈为空，或者栈顶操作符为左括号，直接将当前操作符压入栈。

2. 否则，比较当前操作符与栈顶操作符的优先级，如果当前操作符的优先级较低，将栈顶操作符弹出并加入输出队列，然后将当前操作符压入栈。

3. 如果当前操作符的优先级大于等于栈顶操作符的优先级，则直接将当前操作符压入栈。

7. 遍历完中缀表达式后，将栈中的操作符依次弹出并加入输出队列。

3.2 后缀表达式求值通过将中缀表达式转换为后缀表达式，我们可以利用栈来对后缀表达式进行求值。

具体求值操作如下：1. 初始化一个栈。

2. 从左到右遍历后缀表达式的每个字符。

3. 如果当前字符是数字，将其加入栈。

4. 如果当前字符是操作符，从栈中弹出两个数字，进行相应的运算，然后将结果加入栈。

5. 遍历完后缀表达式后，栈中的元素即为最终的结果。

4. 实验结果我们用中缀表达式\。

1.问题描述（1）表达式求值问题表达式是数据运算的基本形式。

人们的书写习惯是中缀式，如：11+22*(7-4)/3。

中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。

表达式还有后缀式（如：22 7 4 - * 3 / 11 +）和前缀式（如：+ 11 / * 22 – 7 4 3）。

后缀表达式和前缀表达式中没有括号，给计算带来方便。

如后缀式计算时按运算符出现的先后进行计算。

本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。

2.数据结构设计（1）表达式求值问题由于表达式中有字符与数字两种类型，故定义结点一个标志域data，标志结点存储的为字符data=2还是数字data=1，再寻找结点中对应的存储位置，读取数字域data1,字符域data2。

而在前缀表达式时，存在表达式逆序，因表达式类型不统一，用栈逆序极不方便，选择构建双向链表，存储表达式。

typedef struct Node //定义存储中缀表达式的结点类型{int data;int data1;char data2;struct Node *next;}Lnode;typedef struct Node2 //定义存储前缀表达式的结点类型{int data;int data1;char data2;struct Node2 *next;struct Node2 *prior;}Lnode2;3.运行、测试与分析（1）表达式求值问题（1）按提示输入中缀表达式，如图1.1所示。

如输入中缀表达式不正确，提示输入有误，如图1.2,1.3所示。

图1.1图1.2图1.3（2）选择表达式转换并求值方式。

按“1”选择中缀表达式求值，如图1.4所示。

图1.4（3）按“2”选择中缀表达式转变为后缀表达式并求值，如图1.5所示。

图1.5（4）按“3”选择中缀表达式转变为前缀表达式并求值，如图1.6所示。

图1.6附录：源代码（1）表达式求值问题#include<stdio.h>#include<stdlib.h>#define MAXNUM 100typedef struct Node //定义存储中缀表达式的结点类型{int data;int data1;char data2;struct Node *next;}Lnode;typedef struct Node2 //定义存储前缀表达式的结点类型{int data;int data1;char data2;struct Node2 *next;struct Node2 *prior;}Lnode2;typedef int selemtype1; //定义运算数栈的结点typedef struct //定义运算数栈的类型{selemtype1 *base;selemtype1 *top;}sqstack1;void InitStack1(sqstack1 &s) //新建一个空运算数栈{s.base=(selemtype1 *)malloc(MAXNUM*sizeof(selemtype1)); s.top=s.base;if(!s.base) printf("出错：申请空间失败！\n");}void Push1(sqstack1 &s,selemtype1 &e) //运算数栈，入栈：插入元素e为新的栈顶元素{ if(s.top-s.base>=MAXNUM)printf("出错：表达式过长！1\n");*s.top++ =e;}void GetTop1(sqstack1 s,selemtype1 &e) //运算数栈，用e返回栈顶元素{e=*(s.top-1);}void Popopnd1(sqstack1 &s,selemtype1 &e) //运算数栈，退栈：删除栈顶元素，并用e返回其值{e=*--s.top;}int stackempy1(sqstack1 s) //运算数栈，若为空栈返回1，否则返回0{if(s.top==s.base) return 1;else return 0;}typedef char selemtype2; //定义运算符栈的结点类型typedef struct //定义运算符栈类型{selemtype2 *base;selemtype2 *top;}sqstack2;void InitStack2(sqstack2 &s) //新建一个空运算符栈{s.base=(selemtype2 *)malloc(MAXNUM*sizeof(selemtype2));s.top=s.base;if(!s.base) printf("出错：申请空间失败！\n");}void Push2(sqstack2 &s,selemtype2 &e) //运算符栈，入栈：插入元素e为新的栈顶元素{ if(s.top-s.base>=MAXNUM)printf("出错：表达式过长！2\n");*s.top++ =e;}void GetTop2(sqstack2 s,selemtype2 &e) //运算符栈，用e返回栈顶元素{e=*(s.top-1);}void Popopnd2(sqstack2 &s,selemtype2 &e) //运算符栈，退栈：删除栈顶元素，并用e返回其值{e=*--s.top;}int stackempy2(sqstack2 s) //运算符栈，若为空栈返回1，否则返回0{if(s.top==s.base) return 1;else return 0;}void priority(char c,int &i) //确定运算符优先级{if (c=='*'||c=='/'||c=='%') i=2 ;else if (c=='+'||c=='-') i=1 ;else i=0;}int compare(char a,char b) //比较栈顶元素运算符与外部运算符优先级大小，外部优先级大则返回1，反之返回0{int in,out;priority(a,in);priority(b,out);if(out>in) return 1;else return 0;}void Operat(sqstack1 &OPND,sqstack2 &OPTR){int num1,num2,num;char c;Popopnd1(OPND,num2);Popopnd1(OPND,num1);Popopnd2(OPTR,c);switch(c){case '+':num=num1+num2;break;case '-':num=num1-num2;break;case '*':num=num1*num2;break;case '/':num=num1/num2;break;case '%':num=num1%num2;break;}Push1(OPND,num);}void Operatqianzhui(sqstack1 &OPND,sqstack2 &OPTR){int num1,num2,num;char c;Popopnd1(OPND,num1);Popopnd1(OPND,num2);Popopnd2(OPTR,c);switch(c){case '+':num=num1+num2;break;case '-':num=num1-num2;break;case '*':num=num1*num2;break;case '/':num=num1/num2;break;case '%':num=num1%num2;break;}Push1(OPND,num);}void houzhuiqiuzhi(Lnode *p,int &e) //后缀表达式求值{sqstack1 OPND; //运算数栈sqstack2 OPTR; //运算符栈int n;char c;p=p->next;InitStack1(OPND);InitStack2(OPTR);while(p){switch(p->data){case 1:n=p->data1;Push1(OPND,n);break;case 2:c=p->data2;Push2(OPTR,c);Operat(OPND,OPTR);break;default:printf("结点有误");break;}p=p->next;}Popopnd1(OPND,n);e=n;}void zhongzhui(Lnode *p) //中缀表达式求值{sqstack1 OPND; //运算数栈sqstack2 OPTR; //运算符栈int n;char c,c2;Lnode *first;first=p;p=p->next;InitStack1(OPND);InitStack2(OPTR);while(!stackempy2(OPTR)||p){while(p){switch(p->data){case 1:n=p->data1;Push1(OPND,n);break;case 2:c=p->data2;if(stackempy2(OPTR)) Push2(OPTR,c);else { switch(c){case '(': Push2(OPTR,c);break;case ')': GetTop2(OPTR,c2);while(c2!='('){Operat(OPND,OPTR);GetTop2(OPTR,c2);}Popopnd2(OPTR,c2);break;default: GetTop2(OPTR,c2);if(compare(c2,c)) Push2(OPTR,c); else { Operat(OPND,OPTR);Push2(OPTR,c);}break;}}break;default: printf("结点有误");break;}p=p->next;}while(!stackempy2(OPTR))Operat(OPND,OPTR);}Popopnd1(OPND,n);p=first->next;while(p){if(p->data==1) printf("%d ",p->data1);if(p->data==2) printf("%c",p->data2);p=p->next;}printf("=%d ",n);}void houzhui(Lnode *p) //中缀表达式转化为后缀表达式{sqstack2 OPTR; //运算符栈Lnode *r,*q,*head;int n;char c,c2;InitStack2(OPTR);p=p->next;q=(Lnode*)malloc(sizeof(struct Node));head=q;while(p){ switch(p->data){case 1:n=p->data1;r=(Lnode*)malloc(sizeof(struct Node));q->next=r;q=q->next;q->data=1;q->data1=n;break;case 2:c=p->data2;if(stackempy2(OPTR)) Push2(OPTR,c);else { switch(c){ case '(': Push2(OPTR,c);break;case ')': Popopnd2(OPTR,c2);while(c2!='('){ r=(Lnode*)malloc(sizeof(struct Node));q->next=r;q=q->next;q->data=2;q->data2=c2;Popopnd2(OPTR,c2);}break;default: GetTop2(OPTR,c2);while(!compare(c2,c)){ Popopnd2(OPTR,c2);r=(Lnode*)malloc(sizeof(struct Node));q->next=r;q=q->next;q->data=2;q->data2=c2;GetTop2(OPTR,c2);}Push2(OPTR,c);break;}}break;default: printf("结点有误");break;}p=p->next;}while(!stackempy2(OPTR)){ Popopnd2(OPTR,c2);r=(Lnode*)malloc(sizeof(struct Node));q->next=r;q=q->next;q->data=2;q->data2=c2;}q->next=NULL;q=head->next;while(q){if(q->data==1) printf("%d ",q->data1);if(q->data==2) printf("%c",q->data2);q=q->next;}houzhuiqiuzhi(head,n);printf("=%d ",n);}void qianzhuiqiuzhi(Lnode2 *p,int &e) //前缀表达式求值{sqstack1 OPND; //运算数栈sqstack2 OPTR; //运算符栈int n;char c;Lnode2 *head;head=p;p=p->next;InitStack1(OPND);InitStack2(OPTR);while(p!=head){switch(p->data){case 1:n=p->data1;Push1(OPND,n);break;case 2:c=p->data2;Push2(OPTR,c);Operatqianzhui(OPND,OPTR); break;default:printf("结点有误");break;}p=p->next;}Popopnd1(OPND,n);e=n;}void qianzhui(Lnode *p) //中缀表达式转化为前缀表达式{sqstack2 OPTR; //运算符栈InitStack2(OPTR);int n;char c,c2;Lnode *first;Lnode2 *q,*head,*r,*head2,*s;first=p;p=p->next;q=(Lnode2*)malloc(sizeof(struct Node2)); //建立存中缀表达式的双向循环链表head=q;while(p){r=(Lnode2*)malloc(sizeof(struct Node2));q->next=r;r->prior=q;q=q->next;q->data=p->data;q->data1=p->data1;q->data2=p->data2;p=p->next;}q->next=head;head->prior=q;s=(Lnode2*)malloc(sizeof(struct Node2)); //建立存前缀表达式的双向循环链表head2=s;while(q!=head){switch(q->data){case 1:n=q->data1;r=(Lnode2*)malloc(sizeof(struct Node2));s->next=r;r->prior=s;s=s->next;s->data=1;s->data1=n;break;case 2:c=q->data2;if(stackempy2(OPTR)) Push2(OPTR,c);else{ GetTop2(OPTR,c2);if(c2==')') Push2(OPTR,c);else{ switch(c){ case ')':Push2(OPTR,c);break;case '(': Popopnd2(OPTR,c2);while(c2!=')'){ r=(Lnode2*)malloc(sizeof(struct Node2));s->next=r;r->prior=s;s=s->next;s->data=2;s->data2=c2;Popopnd2(OPTR,c2);}break;default: GetTop2(OPTR,c2);while(!compare(c2,c)){ Popopnd2(OPTR,c2);r=(Lnode2*)malloc(sizeof(struct Node2));s->next=r;r->prior=s;s=s->next;s->data=2;s->data2=c2;GetTop2(OPTR,c2);}Push2(OPTR,c);break;}}}break;default:printf("结点有误");break;}q=q->prior;}while(!stackempy2(OPTR)){ Popopnd2(OPTR,c2);r=(Lnode2*)malloc(sizeof(struct Node2));s->next=r;r->prior=s;s=s->next;s->data=2;s->data2=c2;}s->next=head2;head2->prior=s;while(s!=head2){if(s->data==1) printf("%d ",s->data1); if(s->data==2) printf("%c",s->data2); s=s->prior;}qianzhuiqiuzhi(head2,n);printf("=%d ",n);}int main(){ char n[10];char c;int i,j,k,a,b,z,y,e;Lnode *p,*q,*first;i=0;e=1;a=0;b=1;z=0;y=0;p=(Lnode*)malloc(sizeof(struct Node));first=p;printf("请输入中缀表达式");do{ c = getchar();if('0'<=c&&c<='9'){ n[i]=c;i++;}else{ switch (c){ case '+':case '-':case '*':case '/':case '%':case '(':case ')':case '\n':{ if(n[0]>'0'&&n[0]<='9'){ q=(Lnode*)malloc(sizeof(struct Node)); p->next=q;p=p->next;for(k=0;k<i;k++){ for(j=0;j<=i-k-2;j++)e=e*10;a=a+(n[k]-'0')*e;e=1;n[k]='0';}p->data=1;p->data1=a;i=0;a=0;}if(c!='\n'){ if(p->data==2){ if(p->data2!=')'&&c!='(')b=0;}q=(Lnode*)malloc(sizeof(struct Node));p->next=q;p=p->next;p->data=2;p->data2=c;if(c=='(') z++;if(c==')') y++;}}default:if(c!='+'&&c!='-'&&c!='*'&&c!='/'&&c!='%'&&c!='\n'&&c!='('&&c!=')') b=0;}}}while (c != '\n');if(z!=y) b=0;p->next=NULL;if(b==0)printf("输入中缀表达式有误");else{printf("输入1中缀表达式求值，输入2后缀表达式求值，输入3前缀表达式求值");scanf("%d",&b);if(b==1) zhongzhui(first);if(b==2) houzhui(first);if(b==3) qianzhui(first);}return 1;}。

【导读】本文将介绍数据结构中的四则运算、中缀表达式和后缀表达式，并提供相关代码示例，帮助读者更好地理解和应用这些概念。

1. 数据结构概述数据结构是计算机科学中的重要概念，用于组织和存储数据以便于访问和操作。

常见的数据结构包括数组、链表、栈、队列、树等，其中栈和队列是实现四则运算和表达式求值的重要工具。

2. 四则运算四则运算是数学中的基本运算，包括加法、减法、乘法和除法。

在计算机中，常常需要对表达式进行四则运算，因此需要设计算法和数据结构来实现这一功能。

3. 中缀表达式中缀表达式是我们通常使用的表达式形式，如 3+5*2。

中缀表达式中运算符的优先级和结合性需要考虑，因此需要设计算法来对中缀表达式进行求值。

4. 后缀表达式后缀表达式，也称为逆波兰表达式，是一种不含括号的表达式形式。

在后缀表达式中，运算符总是跟随着其操作数，因此不需要考虑优先级和结合性的问题，可以直接进行求值。

5. 代码示例下面以Python语言为例，给出中缀表达式转换为后缀表达式的代码示例，以及使用栈进行后缀表达式求值的代码示例。

``` python#中缀表达式转后缀表达式def infix_to_postfix(infix):precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}stack = []postfix = []for token in infix.split():if token.isdigit():postfix.append(token)elif token in precedence:while stack and precedence.get(stack[-1], 0) >= precedence[token]:postfix.append(stack.pop())stack.append(token)elif token == '(':stack.append(token)elif token == ')':while stack[-1] != '(':postfix.append(stack.pop()) stack.pop()while stack:postfix.append(stack.pop())return ' '.join(postfix)#后缀表达式求值def eval_postfix(postfix):stack = []for token in postfix.split():if token.isdigit():stack.append(int(token))else:b, a = stack.pop(), stack.pop() if token == '+':stack.append(a + b)elif token == '-':stack.append(a - b)elif token == '*':stack.append(a * b)elif token == '/':stack.append(a / b)return stack.pop()#测试代码infix_exp = "3 + 5 * 2"postfix_exp = infix_to_postfix(infix_exp)result = eval_postfix(postfix_exp)print("中缀表达式转后缀表达式：", postfix_exp)print("后缀表达式求值结果：", result)```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 100typedef 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;}elsereturn S->data[S->top--];}DataType GetTop(SeqStack S) //取栈顶元素{if(S.top==-1){printf("stack empty");return0;}elsereturn 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;}四. 算法时间复杂度。

表达式求值实验报告表达式求值实验报告一、引言表达式求值是计算机科学中一个重要的概念，它涉及到对数学表达式的计算和求解。

在本次实验中，我们将探讨表达式求值的相关算法和实现方法，并通过编程实现一个简单的表达式求值器。

二、算法原理1. 表达式的表示方法在计算机中，我们通常使用字符串来表示表达式。

例如，一个简单的数学表达式"2 + 3 * 4"可以表示为字符串"2+3*4"。

在实现表达式求值的算法时，我们需要将字符串中的数字和运算符进行分离，以便进行后续的计算。

2. 中缀表达式转后缀表达式为了方便计算，我们通常将中缀表达式转换为后缀表达式。

后缀表达式也称为逆波兰表达式，它的特点是运算符位于操作数的后面。

例如，上述的中缀表达式"2+3*4"可以转换为后缀表达式"234*+"。

转换的方法可以通过使用栈来实现。

3. 后缀表达式求值得到后缀表达式后，我们可以通过扫描表达式并使用栈来求解。

当遇到操作数时，将其压入栈中；当遇到运算符时，从栈中弹出相应数量的操作数进行计算，并将结果压入栈中。

最终，栈中的唯一元素即为表达式的求值结果。

三、实验过程1. 数据结构设计为了实现表达式求值器，我们需要设计相应的数据结构。

在本次实验中，我们选择使用栈来存储操作数和运算符。

2. 中缀表达式转后缀表达式首先，我们需要编写一个函数来将中缀表达式转换为后缀表达式。

该函数的实现可以通过使用栈和遍历字符串来实现。

具体的步骤如下：- 创建一个空栈和一个空字符串用于存储后缀表达式。

- 从左到右遍历中缀表达式的每个字符。

- 如果遇到操作数，直接将其添加到后缀表达式字符串中。

- 如果遇到运算符，将其与栈顶的运算符进行比较：- 如果栈为空或栈顶为左括号"("，则直接将运算符入栈。

- 如果栈顶的运算符优先级低于当前运算符，则将当前运算符入栈。

- 如果栈顶的运算符优先级高于或等于当前运算符，则将栈顶的运算符弹出并添加到后缀表达式字符串中，直到栈顶的运算符优先级低于当前运算符或栈为空。

中缀转后缀，后缀求值13070319张乐2015.4.211、需求分析明确规定：需要运用栈来实现对中缀表达式转换为后缀表达式，并且再次输入后缀表达式，得出结果。

输入形式、输入值的范围；中缀表达式的输入，操作数必须不为负数，并且表达式以=结束输入输出形式；第一次输出后缀表达式，接着输出后缀表达式求得的值程序功能；中缀表达式转换为后缀表达式，后缀表达式求值测试数据：10(20-10)+10=2、概要设计ADT定义:class arrStack{private:int mSize; //栈最多存放元素个数int top; //栈顶指针T *st; //存栈元素的数组public:arrStack(int sizee) { //创建定长顺序栈的实例mSize = sizee;top = -1;st =new T[mSize];}arrStack( ) {}~arrStack( ) {}void clear( ) { }bool isEmpty( ){}bool push(const T item){}bool pop(T& item) {} T& gettop() {}bool input(){}int trans(){}bool Caculator(){ }}主程序流程:各程序模块间的调用关系；3、详细设计实现ADT定义的数据类型:arrStack(int sizee) { //创建定长顺序栈的实例mSize = sizee;top = -1;st =new T[mSize];}arrStack( ) { //清空top = -1;}~arrStack( ) { //销毁delete [ ]st;}void clear( ) { //清空top = -1;}bool isEmpty( ){ //若栈已空返回trueif(top==-1)return true;return false;}bool push(const T item) //入栈 O(1){/*if (top==(mSize-1)){ //若上溢T *newst = new T[ mSize*2 ]; //扩容到2倍for(int i = 0; i<= top; i++) //复制newst[ i ]= st[ i ];delete [ ]st; //释放旧空间st = newst; //恢复stmSize *=2; //改写mSize }*/st[ ++top ] = item; //插入item return true;}bool pop(T& item) //出栈 O(1){if (top==-1){cout<<"空栈不能删"<<endl;return false;}else{item=st[ top-- ];return true;}}T& gettop() //取栈顶O(1){if (top==-1){cout<<"空栈不能读取"<<endl;}elsereturn st[ top ];}bool input(){char in;int i=0;cout<<"请您输入您要转换的前缀表达式"<<endl; cin>>in;while(in!='='){a[i]=in;cin>>in;i++;}a[i]='=';i=0;while(a[i]!='='){cout<<a[i];i++;}}int trans(){int i=0,j=0;char ch,e;ch=a[i];while(ch!='='){switch(ch){case '(':push(ch);break;case '+':case '-':case '/':case '*':{while(!isEmpty() && gettop()!='(' && gettop()<=ch){ e=gettop();b[j]=e;pop(e);j++;}push(ch);}break;case ')':if (!isEmpty()){while(gettop()!='('){e=gettop();b[j]=e;pop(e);j++;}}pop(e);break;default:if (ch>='0'<='9')b[j++]=ch;}ch=a[++i];}while(!isEmpty()){e=gettop();b[j++]=e;pop(e);}int k=0;cout<<endl<<"您得到的后缀表达式为："<<endl;for (;k<j;k++)cout<<b[k]<<' ';return j;}};bool Caculator(){ //全局函数来计算后缀表达式arrStack<int>s(100);int newope,ope1,ope2,e;char c;cout<<endl<<"请您输入您得到的后缀表达式(以输入等号结束):"<<endl;while(cin>>c,c!='='){switch(c){case '+': ope2=s.gettop();s.pop(e);ope1=s.gettop();s.pop(e);s.push(ope1+ope2);break;case '-': ope2=s.gettop();s.pop(e);ope1=s.gettop();s.pop(e);s.push(ope1-ope2);break;case '*': ope2=s.gettop();s.pop(e);ope1=s.gettop();s.pop(e);s.push(ope1*ope2);break;case '/': ope2=s.gettop();s.pop(e);ope1=s.gettop();s.pop(e);s.push(ope1/ope2);break;default:cin.putback(c);cin>>newope;s.push(newope);break;}}cout<<endl<<"求得的值为："<<endl;e=s.gettop();cout<<e<<endl;s.pop(e);}4、调试分析调试中遇到的问题、如何解决、对设计与实现的分析讨论；调试过程中出现了中缀表达式转换为后缀表达式转换错误的问题，原因是操作符号优先级判断判断错。

实验名称：后缀算术表达式求值背景描述：表达式求值是程序设计语言编译中的一个最基本的问题。

因为任何程序设计语言都必须具有表达式求值的功能，同时表达式的计算应用也相当广泛，比如电力调度系统中的计算遥测、车站票务系统中的票价类型计算公式等。

通常，我们所说的表达式是由运算符、操作数、界限符所组成。

而算术表达式中最常见的表示法形式有中缀、前缀和后缀表示法。

中缀表示法是书写表达式的常见方式，而前缀和后缀表示法主要用于计算机科学领域。

一、表达式表示法1、中缀表达式---将运算符放在两操作数的中间。

在运算中存在运算符的优先权与结合性的问题。

例如运算：a*b+(c-d/e)*f 时，编译器即自左向右逐一检查，当检查到第一个运算符"*"时还无法知道是否执行；待检查到第二个运算符" + "时，因为知道"*"的优先级别高于" + "时，才知道执行"a*b"；当继续检查到" ( "时，可知道先执行括号以内部分等。

2、前缀表达式---将运算符放在两操作数的前面。

这种表示法经常用于计算机科学，特别是编译器设计方面。

为纪念其发明家-Jan Lukasiewicz，这种表示法也称波兰表示法。

3、后缀表达式---将运算符放在两操作数的后面。

后缀表达式也称逆波兰表达式，因其使表达式求值变得轻松，所以被普遍使用。

前缀和后缀表示法有三项公共特征：（1）操作数的顺序与等价的中缀表达式中操作数的顺序一致；（2）不需要括号；（3）操作符的优先级不相关。

问题描述：读入一个后缀表达式表达式，利用堆栈来计算该表达式的值，同时要效验后缀表达式是否正确。

输入输出格式：第一种方式：输入：在字符界面上输入一个后缀表达式，其中两相邻操作数之间利用空格隔开。

以"#"表示结束。

输出：如果该后缀表达式正确，那么在字符界面上输出其结果，计算结果小数点后面保留两位有效数字，如果不正确，请在字符界面上输出表达式错误提示。

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

实验内容与要求：按常规形式输入算术表达式（例如：输入2*(6-4)+8/4），要求能够：（1）基于表达式的中缀表示，对该表达式求值；（2）生成表达式的后缀表示，并输出；（3）基于表达式的后缀表示，对该表达式求值；（4）编写一个主程序对中序和后序表达式求值函数进行测试。

源程序：#include<stdio.h>#include<string.h>#include<stdlib.h>char s1[20],s2[20],a;int x,y,z,n,m,i,j=0;typedef struct node //数据结构常用类型{char data;int num;struct node *next;}sqstack;sqstack *InitSqStack()//创建栈并实现输入{sqstack *top;top=(sqstack *)malloc(sizeof(sqstack));top->data='#';top->num=0;top->next=NULL;return top;}sqstack *Push(sqstack *s)//实现表达式的后序表达{sqstack *p,*top;top=s;gets(s1);m=strlen(s1);for(i=0;i<=m;i++){a=s1[i];if('0'<=s1[i]&&s1[i]<='9'){s2[j]=s1[i];j++;} else{switch(a){case '(':{p=(sqstack *)malloc(sizeof(sqstack));p->data=a;p->next=top;top=p;break;}case '*':case '/':s2[j]=' ';j++;if((top->data=='*')||(top->data=='/')){s2[j]=top->data;j++;top->data=a;break;} else{p=(sqstack *)malloc(sizeof(sqstack));p->data=a;p->next=top;top=p;break;}case '+':case '-':{s2[j]=' ';j++;if(top->data=='+'||top->data=='-'||top->data=='*'||top->data=='/'){s2[j]=top->data;j++;top->data=a;break;} else{p=(sqstack *)malloc(sizeof(sqstack));p->data=a;p->next=top;top=p;break;}}case ')':{s2[j]=' ';j++;if(top->data=='#'){printf("input error");break;}while(top->data!='('){s2[j]=top->data;j++;p=top;top=top->next;free(p);}p=top;top=top->next;free(p);break;}}}}while(top->data!='#')//外部加入的输出函数{s2[j]=top->data;j++;p=top;top=top->next;free(p);}s2[j]='#';printf("后缀表达式为:%s\n",s2);return top;}sqstack *Calcolate(sqstack *s)//中序求值法{sqstack *top,*p;char *q;top=s;for(i=0;i<=j;i++){if(s2[i]>='0'&&s2[i]<='9'){q=&s2[i];z=atoi(q);for(n=i;s2[n]>='0'&&s2[n]<='9';n++)p=(sqstack *)malloc(sizeof(sqstack));p->num=z;p->next=top;top=p;i=n-1; elseif(s2[i]=='#')printf("表达式求值结果为:%d\n",top->num); else{if(s2[i]==' ') else{y=top->num;p=top;top=top->next;free(p);x=top->num;p=top;top=top->next;free(p);switch(s2[i]){case '+':{z=x+y;p=(sqstack *)malloc(sizeof(sqstack));p->num=z;p->next=top;top=p;break;}case '-':{z=x-y;p=(sqstack *)malloc(sizeof(sqstack));p->num=z;p->next=top;top=p;break;}case '*':{z=x*y;p=(sqstack *)malloc(sizeof(sqstack));p->num=z;p->next=top;top=p;break;}case '/':{z=x/y;p=(sqstack *)malloc(sizeof(sqstack));p->num=z;p->next=top;top=p;break;}}}}}return 0;}void main()//主函数部分{sqstack *top,*head;top=InitSqStack();printf("请输入表达式：");head=Push(top);Calcolate(head);}测试结果：心得体会：这个程序极为复杂，算法都不会，没有写出来，这个程序是根据同学的程序改了一些形式而已，没有内部算法的改动，盯着电脑看了一整天大致看懂了。

数据结构实验报告知识范畴：栈与队列完成日期：2017年4月03日实验题目：后缀表达式求值实验内容及要求：从键盘输入后缀表达式（运算符和操作数建议以字符串形式输入，空格作为分隔符），计算并输出后缀表达式的求值结果。

基本要求：实现 +, -, *, /四个二元运算符；实现+, -两个一元运算符（即正、负号）；操作数用整数表示。

提高要求：输出对应的前缀表达式。

每位同学可必须实现基本要求，可选择实现提高要求；程序可不处理表达式语法错误。

实验目的：掌握堆栈在表达式求值中的应用。

数据结构设计简要描述：序言：这是本学期第三个实验，这个实验比较的基本要求是要我们求出一个已经按后缀表达式形式输入的值，除了之前的堆栈部分，新增了一部分就是判断操作数和运算符，并将操作数入栈，将运算符进行对应的操作数功能实现，并将结果入栈。

数据结构简要设计：本实验主要可分为两个大的模块，一个是堆栈操作，另外一个就是后缀表达式求值操作。

堆栈操作：用结构体类型名来创建用于保存操作数的堆栈，并实现判断栈空、栈满、栈初始化、入栈以及退栈等操作；后缀表达式求值操作：用string类型定义一个字符串，并对其进行判断，是操作数就入栈，是运算符就进行运算，并保存结果。

算法设计简要描述：后缀表达式求值算法：用string类型定义一个字符串，并用一个switch来实现运算符的操作和操作数的入栈，再用一个while来进行循环遍历整个字符串，直到字符串的末尾为止。

最后将算得最终结果退栈，并打印到屏幕上即可。

输入/输出设计简要描述：输入：从键盘上输入一个已经排好序的后缀表达式，如12-82-74-/*输出：屏幕上将输出后缀表达式的值，如上面表达式的值为6编程语言说明：1，编程软件，CodeBlocks 16.0；2，代码均用C++语言实现；3，输入输出采用C++语言的cout和cin函数；4，程序注释采用C/C++规范；主要函数说明：void InitStack(Stack *s);//栈的初始化int EmptyStack(Stack *s);//判断栈空int full(Stack *s);//判断栈满int push(Stack *s,elemtype x);//入栈操作int pop(Stack *s,elemtype &x);//退栈操作int result(string s);//后缀表达式求值程序测试简要报告：见截图：1，2，源程序代码：#include<iostream>#include<malloc.h>using namespace std;typedef int elemtype;//整数型数据类型typedef struct{elemtype *elem;int length;int top;} Stack;//函数声明void InitStack(Stack *s);//栈的初始化int EmptyStack(Stack *s);//判断栈空int full(Stack *s);//判断栈满int push(Stack *s,elemtype x);//入栈操作int pop(Stack *s,elemtype &x);//退栈操作int result(string s);//后缀表达式求值//函数具体实现//顺序存储的栈结构，以及其相应算法void InitStack(Stack *s){s->length = 100;s->elem = (elemtype *)malloc((sizeof(elemtype)*s->length));s->top = -1;}//判断栈是否为空int EmptyStack(Stack *s){return s->top == -1;}//判断栈满int full(Stack *s){return s->top>=s->length-1;}//入栈int push(Stack *s,elemtype x){if(full(s)){return 0;}s->elem[++s->top] = x;return 1;}//退栈int pop(Stack *s,elemtype &x){if(EmptyStack(s)){return 0;}x = s->elem[s->top--];return 1;}//后缀表达式求值函数int result(string s){int Result;//定义一个保存输出结果的值Stack *p;//建栈p = (Stack *)malloc(sizeof(Stack));//为新建的栈分配内存空间InitStack(p);//初始化刚建的栈，这一步不进行的话，入栈将不能进行，之前这个问题将我难到了好久int i = 0;//定义一个字符串下标，用来循环判断字符串中的内容elemtype a,b,d;//定义三个elemtype类型变量，用来进行操作数的实现while(1){if(i>s.length()-1)break;switch(s[i]){case '+'://加号则退两个，并相加将结果保存在栈中 pop(p,a);pop(p,b);d = a + b;push(p,d);break;case '-'://加号则退两个，并相减将结果保存在栈中 pop(p,a);pop(p,b);d = b - a;push(p,d);break;case '*'://加号则退两个，并相乘将结果保存在栈中 pop(p,a);pop(p,b);d = a*b;push(p,d);break;case '/'://加号则退两个，并相除结果保存在栈中 pop(p,a);pop(p,b);d = b/a;push(p,d);break;default://是数字就转换为数字后入栈 d = s[i] - '0';push(p,d);break;}i++;//字符串自增一进行遍历}pop(p,Result);//将计算后的结果退栈cout<<Result<<endl;//输出最后的结果return 0;}int main(){string s;cout<<"请输入一个后缀表达式:\n";cin>>s;cout<<"后缀表达式的值为：\n";result(s);return 0;}。

琼州学院实验报告一、实验目的1、掌握接口、范型的定义及使用方法；2、掌握堆栈的定义及实现方法；3、运用堆栈解决问题。

二、实验内容及要求（选作1题）实验内容1：一列货运列车共有n节车厢，重新排列车厢，使各车厢从前至后按编号1到n的次序排列。

我们在一个转轨站里完成车厢的重排工作，在转轨站中有一个入轨、一个出轨和k个缓冲铁轨（位于入轨和出轨之间）。

图3.1a 有k= 3个缓冲铁轨H1，H2和H3。

开始时，n节车厢的货车从入轨处进入转轨站，转轨结束时各车厢从右到左按照编号1至编号n的次序离开转轨站。

根据上面的描述，编写程序实现下面的功能：1）编写一算法实现火车车箱的重排；2）编写程序模拟具有9节车厢的火车入轨和出轨的过程。

实验内容2：后缀表达式就是把运算符置于操作数之后的表示法。

编写程序实现下面的功能：1）编写算法计算后缀表达式的值；2）显示后缀表达式的计算过程。

要求：1）使用数组或链表以及C#接口和范型技术实现通用的堆栈功能；2）利用1）实现堆栈，并完成相应功能。

三、实验设备环境仪器：计算机；实验环境：Microsoft Visual Studio 2008四、实验原理1、堆栈接口定义及说明；interface IStack<T>{void Push(T item); //入栈操作将指定类型元素item进到栈中。

T Pop(); //出栈操作将栈中的栈顶元素取出来，并在栈中删除栈顶元素。

T GetTop(); //取栈顶元素 将栈中的栈顶元素取出来，栈中的元素不变。

int GetLength(); //求栈的长度 获得栈的长度。

bool IsEmpty(); //判断栈是否为空 若栈为空，返回true ，否则返回flase 。

void Clear(); //清空操作 从栈中清除所有的数据元素。

}2、范型顺序栈/链栈实现堆栈接口；顺序栈（SeqStack ）定义了三个字段:data,maxsize,top. private int maxsize; //顺序栈的容量private T[] data; //数组，用于存储顺序栈中的数据元素private int top; //指示顺序栈的栈顶顺序栈（SeqStack ）的存储结构用一维数组来表示。