 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
数据结构算术表达式求值实验报告
下载积分：1000
内容提示：数据结构算术表达式求值实验报告
文档格式：DOC|
浏览次数：73|
上传日期： 14:37:33|
文档星级：
该用户还上传了这些文档
数据结构算术表达式求值实验报告
官方公共微信君，已阅读到文档的结尾了呢~~
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
数据结构实验报告_表达式求值
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口君，已阅读到文档的结尾了呢~~
数据结构表达式求值 表达式求值..
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
《数据结构 课程设计》表达式求值 实验报告
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口　　　　　　　　　　　　　　　　&&&&&&&&&& 中缀表达式求值问题
　　中缀表达式的求值问题是一个比较常见的问题之一，我们通常在编写程序时，直接写出表达式让编译器去处理，很少去关心编译器是怎么对表达式进行求值的，今天我们来一起了解一下其中具体的原理和过程。
　　表达式一般来说有三种：前缀表达式、中缀表达式、后缀表达式，其中后缀表达式又叫做逆波兰表达式。中缀表达式是最符合人们思维方式的一种表达式，顾名思义，就是操作符在操作数的中间。而前缀表达式和后缀表达式中操作符分别在操作数的前面和操作数的后面。举个例子：
　　这个是最简单的一个中缀表达式。而其等同的前缀表达式形式为+32，后缀表达式形式为32+。
　　那么一些朋友可能会问既然中缀表达式最符合人类的思维习惯，为什么还需要前缀表达式和后缀表达式？先看一个例子，假如在前面的表达式基础上加一点东西：
　　此时的表达式很显然，如果进行计算，则先计算2*5，最后计算加法。但是如果需要先计算加法运算呢？则必须加上括号，（3+2）*5。
　　而如果用后缀表达式来表示，则为 32+5*，那么该表达式的计算顺序为3+2 && (3+2)*5。
　　区别就在这里，后缀表达式不需要用括号就能表示出 整个表达式哪部分运算先进行。同理，前缀表达式也是如此。这种表达式正好最符合计算机的处理方式，因为后缀表达式和前缀表达式求值不需要考虑优先级的问题，计算机处理起来便简单很多。
　　今天我们这里主要讲解中缀表达式和后缀表达式（前缀表达式和后缀表达式很类似，就不做过多赘述），下面是讲解大纲：
中缀表达式如何直接求值？
后缀表达式如何直接求值？
中缀表达式如何转换为后缀表达式？
1.中缀表达式直接求值
　　对于中缀表达式求值来说，一般最常见的直接解决办法就是利用栈，一个栈用来保存操作数，一个栈用来保存操作符。
　　为了简便起见，暂时表达式中只考虑简单的+，-，*，/运算，只有圆括号，并且都是整数。
　　假如有这样一个表达式：（（3+5*2）+3）/5+6/4*2+3
　　对于这样一个表达式，如果让你来设计操作数和操作符进栈的出栈的规则，你会怎么设计？
　　先不看这么复杂的表达式，考虑一下简单点的，还是前面的3+2*5，那么很显然先进行乘法运算，后进行加法运算，但是由于操作符在操作数中间，所以当一个操作符进操作符栈时，该操作符的两个操作数并没有都进入到操作数栈中，那么如何解决呢？只有在后面一个操作符进操作符栈时，前面的一个操作符所作用的两个操作数才会全部进栈。比如3+2*5,栈的变化过程为：
　　操作数栈：3&&&&& 操作数栈：3&& 操作数栈：3 2&
　　操作符栈：空&&&& 操作符栈：+& 操作符栈：+&&&&
　　注意此时遇到操作符&*&，是不是需要弹出操作数栈中的两个操作数进行运算呢，很显然不是，因为乘法运算法比操作符栈的栈顶运算符优先级高，也就是说当前的操作符在&+&前进行运算，那么还需要将当前操作符压栈，则变成：
　　操作数栈：3 2&& 操作数栈：3 2 5
　　操作符栈：+ *& 操作符栈：+ *
　　此时到了表达式的结尾，既然栈顶的操作符的优先级比栈底的操作符的优先级高，那么可以取操作符栈的栈顶操作符和操作数栈的栈顶两个元素进行计算，则得到2*5=10，（注意从操作数栈先弹出的操作数为右操作数）。此时得到10 ，则应该把10继续压到操作数栈中，继续取操作符栈的栈顶操作符，依次进行下去，则当操作符栈为空时表示计算过程完毕，此时操作数栈中剩下的唯一元素便是整个表达式的值。
　　再换个例子：2*5+3,这个表达式跟前面表达式的结果虽然相同，但是操作数和操作符入栈和出栈的顺序发生了很大变化：
　　操作数栈：2&&&& 操作数栈：2&& 操作数栈：2 5&&
　　操作符栈：空&&& 操作符栈：*& &操作符栈：*&&&&&
&　　此时遇到&+&，而操作符栈的栈顶操作符为&*&，栈顶操作符优先级更高，表示此时可以取操作符栈顶操作符进行运算，那么栈变成：
　　操作数栈：10&& 操作数栈：10 3
　　操作符栈：空&&& 操作符栈：+
　　后面的过程跟前面一个例子类似。
　　如果复杂一点，比如包含有括号，连续的乘除法这些怎么处理呢？道理是一样的，对于左括号直接入栈，碰到右括号，则一直将操作符退栈，直到碰到左括号，则括号中的表达式计算完毕。对于连续的乘除法，跟前面例子中处理过程类似。只需要记住一点：只有当前操作符的优先级高于操作符栈栈顶的操作符的优先级，才入栈，否则弹出操作符以及操作数进行计算直至栈顶操作符的优先级低于当前操作符，然后将当前操作符压栈。当所有的操作符处理完毕（即操作符栈为空时），操作数栈中剩下的唯一一个元素便是最终的表达式的值。而操作符的优先级为：+和-优先级是一样的，*和/优先级是一样的，+、-的优先级低于*、/的优先级。
　　不过需要注意的是在求值之前需要对表达式进行预处理，去掉空格、识别 负号（区分&-&是作为减号还是负号），提取操作数等。
　　对于&-&的区分，主要判别方法为：
　　1）若前一个字符为&('，则必定为负号；
　　2）若前一个字符为')'或者数字，则必定为减号；
　　3）若前面一个字符为其他运算符，如*，/，则必定是负号；
　　3）若前面没有字符，即该字符为表达式的第一个字符，则必定是负号。
　　也就是说只有一种情况下，&-&是作为减号使用的，就是前一个字符为')'或者数字的时候。
　　如果判断出&-&是作为负号使用的，这里我采用&#&来代替&-&，并将其作为一种运算（优先级最高）。比如：-3*2
　　我采取的做法是将"#"入栈，然后当遇到&*&时，由于栈顶操作符为"#"，因此取#，然后取操作数栈的栈顶元素（只取一个）进行运算，然后再把结果压栈。
　　下面是具体实现：
/* 测试环境: mingw*/
#include &iostream&
#include &vector&
#include &stack&
#include &string&
#include &cstdlib&
#include &cctype&
#include &cstring&
vector&string& preParse(char *str)
//对中缀表达式进行预处理，分离出每个token
vector&string&
int len = strlen(str);
char *p = (char *)malloc((len+1)*sizeof(char));
//注意不要用 char *p = (char *)malloc(sizeof(str))来申请空间
int i=0,j=0;
while(i&len)
//去除表达式中的空格
if(str[i]==' ')
p[j++] = str[i++];
p[j]='\0';
len = strlen(p);
while(j&len)
char temp[2];
switch(p[j])
temp[0] =p[j];
temp[1] = '\0';
tokens.push_back(token);
if(p[j-1]==')'||isdigit(p[j-1]))
//作为减号使用
temp[0] =p[j];
temp[1] = '\0';
tokens.push_back(token);
//作为负号使用
temp[0] ='#';
temp[1] = '\0';
tokens.push_back(token);
while(isdigit(p[i])&&i&len)
char *opd = (char *)malloc(i-j+1);
strncpy(opd,p+j,i-j);
opd[i-j]='\0';
tokens.push_back(token);
free(opd);
int getPriority(string opt)
if(opt=="#")
priority = 3;
else if(opt=="*"||opt=="/")
priority = 2;
else if(opt=="+"||opt=="-")
priority = 1;
else if(opt=="(")
priority = 0;
void calculate(stack&int& &opdStack,string opt)
if(opt=="#")
//进行负号运算
int opd = opdStack.top();
int result = 0-
opdStack.pop();
opdStack.push(result);
cout&&"操作符:"&&opt&&" "&&"操作数:"&&opd&&
else if(opt=="+")
int rOpd = opdStack.top();
opdStack.pop();
int lOpd = opdStack.top();
opdStack.pop();
int result = lOpd + rO
opdStack.push(result);
cout&&"操作符:"&&opt&&" "&&"操作数:"&&lOpd&&" "&&rOpd&&
else if(opt=="-")
int rOpd = opdStack.top();
opdStack.pop();
int lOpd = opdStack.top();
opdStack.pop();
int result = lOpd - rO
opdStack.push(result);
cout&&"操作符:"&&opt&&" "&&"操作数:"&&lOpd&&" "&&rOpd&&
else if(opt=="*")
int rOpd = opdStack.top();
opdStack.pop();
int lOpd = opdStack.top();
opdStack.pop();
int result = lOpd * rO
opdStack.push(result);
cout&&"操作符:"&&opt&&" "&&"操作数:"&&lOpd&&" "&&rOpd&&
else if(opt=="/")
int rOpd = opdStack.top();
opdStack.pop();
int lOpd = opdStack.top();
opdStack.pop();
int result = lOpd / rO
opdStack.push(result);
cout&&"操作符:"&&opt&&" "&&"操作数:"&&lOpd&&" "&&rOpd&&
int evaMidExpression(char *str)
//中缀表达式直接求值
vector&string& tokens = preParse(str);
int size = tokens.size();
stack&int& opdS
//存储操作数
stack&string& optS
//存储操作符
for(i=0;i&i++)
string token = tokens[i];
if(token=="#"||token=="+"||token=="-"||token=="*"||token=="/")
if(optStack.size()==0)
//如果操作符栈为空
optStack.push(token);
int tokenPriority = getPriority(token);
string topOpt = optStack.top();
int topOptPriority = getPriority(topOpt);
if(tokenPriority&topOptPriority)
optStack.push(token);
while(tokenPriority&=topOptPriority)
optStack.pop();
calculate(opdStack,topOpt);
if(optStack.size()&0)
topOpt = optStack.top();
topOptPriority = getPriority(topOpt);
optStack.push(token);
else if(token=="(")
optStack.push(token);
else if(token==")")
while(optStack.top()!="(")
string topOpt = optStack.top();
calculate(opdStack,topOpt);
optStack.pop();
optStack.pop();
//如果是操作数，直接入操作数栈
opdStack.push(atoi(token.c_str()));
while(optStack.size()!=0)
string topOpt = optStack.top();
calculate(opdStack,topOpt);
optStack.pop();
return opdStack.top();
int main(int argc, char *argv[])
char *str = "((3+5*2)+3)/5+(-6)/4*2+3";
cout&&evaMidExpression(str)&&
　　运行结果：
2.后缀表达式直接求值
　　由于后缀表达式不需要用括号来表示计算顺序，因此处理起来比较简单，具体的可以参照：
3.中缀表达式如何转为后缀
　　大部分数据结构教材在讲述 栈的时候都会涉及到中缀表达式转为后缀表达式的问题，因为这个是栈的典型应用之一。因此很多教材上都会利用栈来进行转换，这里我们来讨论一下最常见的两种转换思路和一种简便的验证方法。
利用二叉树进行转换
　　由于二叉树本身结构的特殊性，使得我们可以利用它来很轻松地将中缀表达式转变成后缀表达式，事实上，只要根据中缀表达式建立好相应的二叉树之后，直接对二叉树进行前序遍历和后序遍历便可得到前缀表达式和后缀表达式。在利用二叉树来表示表达式时，用叶子节点来存储操作数，用内部节点存储操作符，比如这样一个表达式3*5+5/2+（3+5）*2，表示成二叉树的形式（注意其有等同的其他形式）就是：
　　其实讲中缀表达式的过程转变成二叉树的形式是一个递归的过程，比如有一个表达式，其对应的的二叉树的根节点必定是优先级最低的操作符（也就是说是整个表达式中最后进行的运算操作），然后再在操作符的左部分中找出最后进行的操作符作为根节点的左孩子，在操作符的右部分中找出最后进行的操作符作为根节点的右孩子，然后知道左部分或者右部分是单纯的操作数，则作为叶子节点，直到整个二叉树建立完毕。
　　下面是具体实现：
&　　参考了一下这篇博文的实现，但是这篇博文没有考虑减号作为负号使用的情况。
测试环境：VS2010
#include &iostream&
#include &string&
#include &cctype&
#include &cstring&
#include &cstdlib&
#include &queue&
typedef struct node
struct node *
struct node *
char * preProcess(char *str)
//预处理，除去空格，将负号替代为#
int len = strlen(str);
char *p = (char *)malloc(sizeof(char)*len);
int i=0,j=0;
while(i&len)
//去除表达式中的空格
if(str[i]==' ')
p[j++] = str[i++];
p[j]='\0';
len = strlen(p);
while(j&len)
if(p[j]=='-')
if(!(p[j-1]==')'||isdigit(p[j-1])))
//作为减号使用
最后执行的操作符一定是在括号外面，也就是说brackets一定是等于0的，
int indexOfOpt(char *str,int begin ,int end)
//寻找最后执行的操作符的下标
int brackets=0;
//所在括号层次
int index = -1;
int existAddOrMinus = 0;
int existMulOrDevide = 0;
while(str[begin]=='('&&str[end]==')')
//去除最外层的括号
for(i=i&=i++)
if(str[i]=='(')
brackets++;
else if(str[i]==')')
brackets--;
else if((str[i]=='+'||str[i]=='-')&&brackets==0)
existAddOrMinus = 1;
//存在加减号
else if((str[i]=='*'||str[i]=='/')&&brackets==0&&existAddOrMinus==0)
existMulOrDevide = 1;
//存在乘除号
else if(str[i]=='#'&&brackets==0&&existAddOrMinus==0&&existMulOrDevide==0)
//用'#'代表负号
BinTree * createBinTree(char *str,int begin,int end)
BinTree *p =(BinTree *)malloc(sizeof(BinTree));;
int index = indexOfOpt(str,begin,end);
cout&&"index:"&&index&&
if(index==-1)
//表示只有操作数了
while(str[begin]=='('&&str[end]==')')
p-&data = (char *)malloc(sizeof(end-begin+2));
int i,j=0;
for(i=i&=i++)
p-&data[j++] = str[i];
p-&data[j]='\0';
p-&left = NULL;
p-&right = NULL;
cout&&"操作数:"&&p-&data&&
p-&data = (char*)malloc(2);
p-&data[0] = str[index];
p-&data[1]='\0';
cout&&"操作符:"&&p-&data&&
while(str[begin]=='('&&str[end]==')')
if(str[index]=='#')
p-&left = NULL;
p-&left = createBinTree(str,begin,index-1);
p-&right = createBinTree(str,index+1,end);
void preOrder(BinTree *root)
if(root!=NULL)
cout&&root-&data&&" ";
preOrder(root-&left);
preOrder(root-&right);
void inOrder(BinTree *root)
if(root!=NULL)
inOrder(root-&left);
cout&&root-&data&&" ";
inOrder(root-&right);
void postOrder(BinTree *root)
if(root!=NULL)
postOrder(root-&left);
postOrder(root-&right);
cout&&root-&data&&" ";
int main(void)
char *str = "((3+5*2)+3)/5+(-6)/4*2+3";
char *newStr = preProcess(str);
cout&&newStr&&
BinTree *root=createBinTree(newStr,0,strlen(newStr)-1);
inOrder(root);
postOrder(root);
system("pause");
　　上述代码在VS2010下运行是没有问题的，但是在gcc下编译运行会崩溃，调试了很久没发现原因（如果有哪位朋友知道原因的请麻烦告知）。测试结果：
利用栈进行转换
　　利用栈进行转换的思路其实跟前面直接对中缀表达式求值的过程类似，在这过程中需要一个栈用来保存操作符optStack，需要一个数组用来保存后缀表达式suffix[]，然后从头到尾扫描表达式
　　1）如果遇到操作符，则跟optStack的栈顶操作符比较优先级，如果大于栈顶操作符的优先级，则入栈，否则不断取栈顶操作符加到suffix的末尾，直到栈顶操作符优先级低于该操作符，然后将该操作符入栈；
　　2）遇到操作数，直接加到suffix的末尾
　　3）遇到左括号，入栈；
　　4）遇到右括号，则依次弹出栈顶操作符加到suffix的末尾，直到遇到左括号，然后将左括号出栈。
　　具体实现：
/* 测试环境: mingw*/
#include &iostream&
#include &vector&
#include &stack&
#include &string&
#include &cstdlib&
#include &cctype&
#include &cstring&
vector&string& preParse(char *str)
//对中缀表达式进行预处理，分离出每个token
vector&string&
int len = strlen(str);
char *p = (char *)malloc((len+1)*sizeof(char));
//注意不要用 char *p = (char *)malloc(sizeof(str))来申请空间
int i=0,j=0;
while(i&len)
//去除表达式中的空格
if(str[i]==' ')
p[j++] = str[i++];
p[j]='\0';
len = strlen(p);
while(j&len)
char temp[2];
switch(p[j])
temp[0] =p[j];
temp[1] = '\0';
tokens.push_back(token);
if(p[j-1]==')'||isdigit(p[j-1]))
//作为减号使用
temp[0] =p[j];
temp[1] = '\0';
tokens.push_back(token);
//作为负号使用
temp[0] ='#';
temp[1] = '\0';
tokens.push_back(token);
while(isdigit(p[i])&&i&len)
char *opd = (char *)malloc(i-j+1);
strncpy(opd,p+j,i-j);
opd[i-j]='\0';
tokens.push_back(token);
free(opd);
int getPriority(string opt)
if(opt=="#")
priority = 3;
else if(opt=="*"||opt=="/")
priority = 2;
else if(opt=="+"||opt=="-")
priority = 1;
else if(opt=="(")
priority = 0;
vector&string& toSuffix(char *str)
//转变为后缀形式
vector&string& tokens = preParse(str);
int size = tokens.size();
vector&string&
//存储后缀表达式
stack&string& optS
//存储操作符
for(i=0;i&i++)
string token = tokens[i];
if(token=="#"||token=="+"||token=="-"||token=="*"||token=="/")
if(optStack.size()==0)
//如果操作符栈为空
optStack.push(token);
int tokenPriority = getPriority(token);
string topOpt = optStack.top();
int topOptPriority = getPriority(topOpt);
if(tokenPriority&topOptPriority)
optStack.push(token);
while(tokenPriority&=topOptPriority)
optStack.pop();
suffix.push_back(topOpt);
if(optStack.size()&0)
topOpt = optStack.top();
topOptPriority = getPriority(topOpt);
optStack.push(token);
else if(token=="(")
optStack.push(token);
else if(token==")")
while(optStack.top()!="(")
string topOpt = optStack.top();
suffix.push_back(topOpt);
optStack.pop();
optStack.pop();
//如果是操作数，直接入操作数栈
suffix.push_back(token);
while(optStack.size()!=0)
string topOpt = optStack.top();
suffix.push_back(topOpt);
optStack.pop();
int main(int argc, char *argv[])
char *str = "((3+5*2)+3)/5+(-6)/4*2+3";
vector&string& suffix = toSuffix(str);
int size = suffix.size();
for(int i=0;i&i++)
cout&&suffix[i]&&" ";
　　测试结果：
简便验证办法
　　最后一种办法可以很快速地求出中缀表达式对应的前缀表达式和后缀表达式，就是添括号去括号法。
　　比如有表达式： （3+5*2）-2*3
　　先对每一个小部分添加括号： （（3+（5*2））-（2*3））
　　然后将每个操作符放到括号后面：（（3（52）*）+（23）*）-
　　然后去括号：352*+23*-
　　便得到了后缀表达式，前缀表达式类似（只需把操作符放到括号前面即可）。
阅读(...) 评论()&数据结构算术表达式求值实验报告
秒后自动跳转到登录页
(奖励10下载豆)
快捷登录：
举报类型：
不规范：上传重复资源
不规范：标题与实际内容不符
不规范：资源无法下载或使用
其他不规范行为
违规：资源涉及侵权
违规：含有危害国家安全等内容
违规：含有反动/色情等内容
违规：广告内容
详细原因：
任何违反下载中心规定的资源，欢迎Down友监督举报，第一举报人可获5-10下载豆奖励。
中小型计算机机房安
网页特效库特效源码
VCP 5.0实验手册（最
计算机机房安全性指
【51CTO技术公开课】
【51CTO技术公开课】
《51CTO博客月刊》总
数据结构算术表达式求值实验报告
上传时间：
技术分类：
资源评价：
（0位用户参与评价）
已被下载&3&次
数据结构算术表达式求值实验报告
本资料共包含以下附件：
数据结构算术表达式求值实验报告.txt
51CTO下载中心常见问题：
1.如何获得下载豆？
1)上传资料
2)评论资料
3)每天在首页签到领取
4)购买VIP会员服务，无需下载豆下载资源
5)更多途径：点击此处
2.如何删除自己的资料？
下载资料意味着您已同意遵守以下协议：
1.资料的所有权益归上传用户所有
2.未经权益所有人同意，不得将资料中的内容挪作商业或盈利用途
3.51CTO下载中心仅提供资料交流平台，并不对任何资料负责
4.本站资料中如有侵权或不适当内容，请邮件与我们联系（）
5.本站不保证资源的准确性、安全性和完整性, 同时也不承担用户因使用这些资料对自己和他人造成任何形式的伤害或损失
下载1965次
下载1007次
下载2488次
相关专题推荐
本专题主要收集了Auto CAD2010系列视
VideoStudio Pro X6 （会声会影 X6）
汇集各大知名厂商设备、服务器VISIO图
Dreamweaver CS6是世界顶级软件厂商a
VBA80集，是兰色幻想耗时一年精心为大
2012年，让桌面连接你我！ 51CTO将在
数字电子技术，西安电子科技大学视频
网络收集的中国科技大学龚升教授的《
收集个人认为较为经典的Selenium资料
收集个人认为教好的LoadRunner相关的
本周下载热点
意见或建议：
联系方式：
您已提交成功！感谢您的宝贵意见，我们会尽快处理