算术表达式求值源码.docx
- 文档编号:16486534
- 上传时间:2023-07-14
- 格式:DOCX
- 页数:16
- 大小:149.37KB
算术表达式求值源码.docx
《算术表达式求值源码.docx》由会员分享,可在线阅读,更多相关《算术表达式求值源码.docx(16页珍藏版)》请在冰点文库上搜索。
算术表达式求值源码
哈尔滨工业大学计算机科学与技术学院
实验报告
课程名称:
数据结构与算法
课程类型:
必修
实验项目名称:
线性表实验
实验题目:
算术表达式求值
设计成绩
报告成绩
指导老师
一、实验目的
1.学会线性表这一类数据结构的用法,了解线性表的逻辑结构、顺序存储结构的描述方法。
2.掌握栈的结构特性和描述方法,熟练掌握栈的基本操作的实现方法。
3.熟练掌握中缀表达式转后缀表达式的过程,进行表达式求值运算。
4.练习程序的编写,使程序更规范。
二、实验要求及实验环境
实验要求:
输入中缀表达式,转换成后缀表达式后求值。
实验环境:
Windows下的NetBeansIDE6.9.1
三、设计思想(本程序中的用到的所有数据类型的定义,主程序的流程图及各程序模块之间的调用关系)
主程序流程图
错误
正确
各模块之间的调用关系
四、测试结果
五、系统不足与经验体会
1.对于输入的中缀表达式的一些格式错误不能反馈出来,考虑的情况不全面。
2.写程序时要及时的加上注释,便于修改。
3.运用栈时要时刻注意栈是否为空,很多时候程序debug时出现这方面的错误,且不易察觉
六、附录:
源代码(带注释)
栈的实现:
/*
*File:
STACKARRAY.h
*Author:
郝萌
*/
#ifndefSTACKARRAY_H
#defineSTACKARRAY_H
#defineSIZE2000
#include
usingnamespacestd;
template
classStack{
public:
Stack();
boolisEmpty();
Ttop();
voidpush(Tvalue);
voidpop();
private:
Ta[SIZE];
intnumber;
};
template
Stack
:
Stack(){
number=0;
}
template
boolStack
:
isEmpty(){
returnnumber==0;
}
template
TStack
:
top(){
if(number==0)
throwruntime_error("Stackisempty!
");
else
returna[number];
}
template
voidStack
:
push(Tc){
number++;
a[number]=c;
}
template
voidStack
:
pop(){
if(number==0)
throwruntime_error("Stackisempty!
");
else
number--;
}
#endif/*STACKARRAY_H*/
============================================================================================================================================
/*
*File:
main.cpp
*Author:
Administrator
*
*Createdon2011年10月31日,下午8:
34
*/
#include
#include
#include"STACKARRAY.h"
usingnamespacestd
intJudge(charcharacter)//判断操作符的优先级
{
if(character=='+'||character=='-')
return1;
elseif(character=='*'||character=='/')
return2;
elseif(character=='('||character==')')
return0;
else
return-1;
}
voidchangeFor(stringpre,charpost[],int&n){//将中缀表达式转化成后缀表达式的函数
inti=0,j=0;
Stack
stack1.push('');
if(pre[0]=='-'){//判断中缀表达式第一个数是否是负数
post[j]='0';
j++;
}
while(i!
=pre.size()){
if(pre[i]>='0'&&pre[i]<='9'||pre[i]=='.'){/*遇到数字和小数点直接写入后缀表达式*/
post[j]=pre[i];
j++;
}elseif(pre[i]=='(')//遇到“(”直接存入栈中
stack1.push(pre[i]);
elseif(pre[i]==')'){/*遇到“)”把下面的运算符依次写入后缀表达式中,直到遇到“)”为止*/
while(stack1.top()!
='('){
post[j]=stack1.top();
j++;
stack1.pop();
}
stack1.pop();//把“(”弹出栈
}elseif(Judge(pre[i])==1||Judge(pre[i])==2){//遇到运算符的情况
if(pre[i]=='-'&&pre[i-1]=='('){//判断小括号内第一个数是否为负数
post[j]='0';//后缀表达式添零
j=j+1;
}
post[j]='';
j++;
while(Judge(pre[i])<=Judge(stack1.top())){//讨论运算符的优先级
post[j++]=stack1.top();/*若当前运算符的优先级不高于栈顶运算符的优先级,则栈顶运算符写入后缀表达式*/
stack1.pop();//弹出栈顶运算符
}
stack1.push(pre[i]);//将当前运算符压入栈中
}
i++;
}
while(!
stack1.isEmpty()){//栈中运算符依次写入后缀运算符中
post[j]=stack1.top();
j++;
stack1.pop();//弹栈
}
n=j-1;
}
doublechtonum(stringstr,int&i){/*将后缀表达式中的表示数字的字符串转化成double型数据*/
doublex1=0.0;
doublex2=0.0;
intk=0;
while(str[i]>='0'&&str[i]<='9')//处理整数部分
{
x1=x1*10+(str[i]-'0');
i++;
}
if(str[i]=='.')//处理小数部分
{
i++;
while(str[i]>='0'&&str[i]<='9'){
x2=x2*10+(str[i]-'0');
i++;
k++;
}
while(k!
=0){
x2/=10.0;
k--;
}
}
returnx1+x2;//返回结果
}
doublecount_value(charpost[],int&m){
Stack
inti=0;
doublex1,x2;
while(i if(post[i]>='0'&&post[i]<='9')//将转化成的操作数压入栈中 stack2.push(chtonum(post,i)); elseif(post[i]=='') i++; elseif(post[i]=='+'){ x2=stack2.top(); stack2.pop(); x1=stack2.top(); stack2.pop(); stack2.push(x1+x2); i++; }elseif(post[i]=='-'){ x2=stack2.top(); stack2.pop(); x1=stack2.top(); stack2.pop(); stack2.push(x1-x2); i++; }elseif(post[i]=='*'){ x2=stack2.top(); stack2.pop(); x1=stack2.top(); stack2.pop(); stack2.push(x1*x2); i++; }elseif(post[i]=='/'){ x2=stack2.top(); XX文库-让每个人平等地提升自我stack2.pop(); XX文库-让每个人平等地提升自我x1=stack2.top(); stack2.pop(); XX文库-让每个人平等地提升自我stack2.push(x1/x2); i++; } } returnstack2.top();//返回后缀表达式运算结果 } voidcompare(charch[],charth[]){//将输入的中缀表达式的空格去掉 intj=strlen(th); intm=0; for(inti=0;i //如果当前字符不是空格,就放到新的字符串里面去 if(th[i]! ='') ch[m++]=th[i]; } //加上字符串结束标志 ch[m]='\0'; } intjudgeError(charth[]){//判断输入表达式的格式是否错误的函数 intj=strlen(th); intm=0,n=0; intk=1; for(inti=0;i if(th[0]=='.'){ k=0; return0; break; } if((Judge(th[i])>0||th[i]=='.')&&(Judge(th[i+1])>0||th[i+1]=='.')&&(i+1) k=0; return0; break; } if(Judge(th[i])==-1&&(th[i]<'0'||th[i]>'9')&&th[i]! ='.'){ k=0; return0; break; } if((th[i]=='('||Judge(th[i])>0||th[i]=='.')&&th[i+1]==')'&&(i+1) k=0; return0; break; } if(th[i]=='('&&((Judge(th[i+1])>0)||th[i+1]=='.')&&th[i+1]! ='-'&&(i+1) k=0; return0; break; } if((Judge(th[i])==-1||th[i]==')')&&th[i+1]=='('&&(i+1) k=0; return0; break; } if(th[i]=='(') m++; if(th[i]==')') n++; if(n>m){ k=0; return0; break; } } if((th[j-1]>'9'||th[j-1]<'0')&&Judge(th[j-1])! =0){ return0; } elseif(m! =n&&k==1){ return0; }else return1; } intmain(intargc,char**argv){ constintsize=200; intn=0; stringprefor; charpostfor[size]; charch[size]; charth[size]; while (1){ cout<<"请输入中缀表达式: "< gets(th); compare(ch,th);//去掉空格 while(judgeError(ch)==0){//判断输入格式是否错误 cout<<"输入格式错误,请重新输入! "< gets(th); compare(ch,th); } prefor=ch; changeFor(prefor,postfor,n);//将中缀表达式转换成后缀表达式 cout<<"其对应的后缀表达式为: "< for(inti=0;i cout< } cout< cout<<"由后缀表达式计算的结果为: "< cout< } return0; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算术 表达式 求值 源码
![提示](https://static.bingdoc.com/images/bang_tan.gif)