简易计算器栈与队列实验报告

1、 第三组专题二栈与队列实验报告 -简易计算器一.（1）问题描述通过模拟一个简单的计算器来进行+、-、*、/、%、（乘方）等运算，从键盘上输入一算术表达式（一般为中缀表达式），计算出表达式的值。（2）基本要求编写程序，要求可对一实数算术表达式进行简单的数学运算。可以识别带加减乘除等运算符及括号的中缀表达式。a. 按照四则运算规则，求表达式的值。一般规则如下：1）先括号内，再括号外。2）先乘方，再乘除，后加减。b. 同级运算从左到右顺序执行。c如表达式有误，应给出相应的提示信息。（3）数据结构与算法分析解决表达式求值问题的方法之一是：第一步将中缀表达式转换为后缀表达式，第二步按后缀表达式求值。解题

2、时可以结合字符串的相关知识。（4）测试 4.5+5+6.5*1.06=16.39二.（1）问题分析： 计算机要计算一个式子，不能像我们一样计算，它需要把表达式由中缀表达式转换成后缀表达式，即逆波兰表达式。 将一般中缀表达式转换为逆波兰表达式有如下转换过程：(1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。(2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“=”。(3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。 (4)如果不是数字，该字符则是运算符，此

3、时需比较优先关系。做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将栈顶的运算符从栈中弹出，直到栈顶运算符的优先级低于当前运算符，将该字符入栈。(5)重复上述操作(3)-(4)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。（2）问题实现及代码。 1.菜单函数：使用switch函数根据输入的数字选择是否进入计算器2.检测非法输入函数：3.双目运算符定义函数：完成对+，-，*，/,的定义：4.判断运算符的优先级，决定是压栈或者弹

4、栈运用到计算中：5.括号匹配检测函数：6.运算栈：分为运算符栈和运算数栈：7.算式计算函数（最关键函数）：用于对用户输入的算式进行计算，给出最后结果：三.程序运行演示：括号检测：非法输入检测：四.MFC界面介绍.我们不满足于DC限制的黑框框界面，所以我们运用了MFC界面。（1） 界面初步简介：（2） 对程序的改动：（3） 对c+程序的改进： 加、减、乘、除、退格键的报错提示：五.优势与不足：优势：（1）做出了界面，不再是黑框框（2）报错系统完善，基本不会出错。（3）结果显示正确，不会出现多余的0。不足：（1）虽然做出了界面，但是还不是很优美。（2）功能还不是很强大，不能进行三角函数的运算及其他

5、运算。这些缺点我们都会再以后的学习中克服掉！源代码：#include<iostream>#include<cmath>#include<string>#include<iomanip>using namespace std;void menu();/位于calculate函数后面的菜单函数声明double D_Operate(double x,char op,double y)/双目运算符的运算定义 double a;/计算结果 switch(op) case'+': a=x+y;break; case'-': a

6、=x-y;break; case'*': a=x*y;break; case'/': a=x/y;break; case'': a=pow(x,y);break;/幂运算包括乘方和开方 /因为都是利用double进行运算 因此不定义取模运算 return a;char Precede(char op1,char op2) /判断符号的优先级 op1在返回的结果符的左边 op2在右边/用于判定运算符的优先级 以决定是把运算符压栈 还是把栈内的运算符弹出来进行计算 if(op1='+'|op1='-')&&am

7、p;(op2='+'|op2='-'|op2=')'|op2='=')| (op1='*'|op1='/')&&(op2='+'|op2='-'|op2='*'|op2='/'|op2=')'|op2='=') |(op1=''&&(op2='+'|op2='-'|op2='*'|op2='/'

8、|op2=')'|op2='=') return '>'/上述情况下 栈顶运算符优先级高于待定运算符 需弹栈 if(op1='('&&op2=')')|(op1='='&&op2='=') return '=' else return '<'int illegal_char(string s,int i)/非法输入字符判定函数 int j=0; while(j<i) if(sj>='0&#

9、39;&&sj<='9') j+; else if(sj='+'|sj='-'|sj='*'|sj='/'|sj='.'|sj='('|sj=')'|sj='') j+; /以上都是标准的数字字符和运算符 如若存在其他形式的字符 则是非法输入 else cout<<"程序终止，存在非法的字符输入！"<<endl; return 0; return 1;/没有非法字符 返回1 否则返回0i

10、nt match(string s)/栈结构的括号匹配检测函数 int i=0,top=0; char stack50; while(si!='0') if(si='(') stacktop=si;top+; /push 左括号压入栈内 if(si=')') if(stacktop-1='(') int a=i+1; stacktop-1=NULL; top-; /把与右括号匹配的左括号弹掉 else cout<<"括号输入有误"<<endl; return 0;/多了右括号 括号失陪

11、返回非法 /pop'(' i+; if (top!=0) cout<<"括号输入有误"<<endl; return 0;/多了左括号 括号失陪 返回非法 return 1;/返回合法class NUMstack/运算数栈 public: double num1000; int top; void start()/初始化栈清空栈顶指针置底 for(int i=0;i<1000;i+) numi=0; top=0; void push(char a)/因为有多位数的运算因此不能一压栈就提升栈顶指针 numtop=numtop*10+

12、(a-'0');/把字符转成数因为每次入栈之前要乘10 所以初始化要清0double pop() top-; double number=numtop; numtop=0; return number; /弹栈函数 弹掉栈顶元素 栈顶归0 top指针下降 double getTop()/取栈顶元素但不必弹栈 return numtop-1; void lift()/提升top指针的函数 top+;class OPERstack/运算符栈 public: char oper1000; int top; void start()/初始化函数栈清空栈底放一"="用

13、于判定算式结束 oper0='=' for(int i=1;i<1000;i+) operi=NULL; top=1;/栈顶指针置于栈底的上一位 void push(char a) opertop=a; top+;/与数字栈不同一压栈就可以提升指针 char pop() top-; char op=opertop; opertop=NULL; return op;/弹出计算符 用于计算 char getTop() return opertop-1;/取栈顶符号 但不弹栈 可用于判定优先级 ;void calculate(string equation)/算式计算函数（关键

14、函数） NUMstack number;/定义运算数栈变量number OPERstack oper;/定义运算符栈变量oper number.start(); oper.start();/把两个栈初始化 int i=0,len=0,k; char p,sig; double yuan1,yuan2; while(equationi!='0') len+; i+; /计算等式长度len if(equationlen-1!='=') cout<<"输入有误！没有输入终止符号-等号“=”"<<endl; return;/检

15、测有没有结束符等号"=" int le; le=illegal_char(equation,len-1); if(le=0) return;/有非法字符 不进行后续计算 le=match(equation); if(le=0) return;/括号匹配非法 不进行后续计算 for(i=0;i<len;i+)/初步确定合法后开始计算算式 if(equationi>='0'&&equationi<='9') number.push(equationi);/压数字字符入栈 if(equationi+1<

16、9;0'|equationi+1>'9')&&equationi+1!='.') number.lift();/当整个多位运算数读取完毕后，运算数栈栈顶指针才能提升 else if(equationi='.')/小数压栈代码 int x=1; while(equationi+x>='0'&&equationi+x<='9') number.numnumber.top+=(equationi+x-'0')/pow(10,x);/第x位小数入栈

17、x+; x-; number.lift(); i=i+x; else if(equationi='(') oper.push(equationi);/左括号无条件压栈 else/数 乘方左括号判断完毕后其他运算符的分类讨论 if(oper.top=1)/运算符栈为空运算符可以无条件入栈 oper.push(equationi); else/运算符栈不为空则要进行优先级判断 char temp1=oper.getTop();/取出栈顶符号 char temp2;/待入栈符号 temp2=equationi; p=Precede(temp1,temp2); if(p='&l

18、t;') oper.push(temp2);/栈顶符优先级较低现在待定的运算符就可以入栈了 if(p='>'|p='=') char rep=p;/当栈顶符优先级不低于待入栈的符号 则运算符栈不停地弹栈 /进行运算直到低于待入栈符号为止 rep用于记录比较结果 要多次进行判断 while(rep='>'|p='=')&&(oper.top-1>0) sig=oper.pop(); yuan1=number.pop(); yuan2=number.getTop();/靠前的一个运算数只要取得

19、不要弹出来 if(sig='/'&&yuan1=0)/yuan1是双目运算符后面的第二运算元 cout<<"错误！除数为0！"<<endl; return; if(sig='+'|sig='-'|sig='*'|sig='/'|sig='') number.num(number.top)-1=D_Operate(yuan2,sig,yuan1); temp1=oper.getTop(); rep=Precede(temp1,temp2);/

20、双目运算符的计算 if(equationi=')')/如果栈外符是右括号要把与之匹配的左括号弹出栈外 oper.pop(); else oper.push(equationi); if(number.num0=ceil(number.num0) cout<<equation<<number.num0<<endl; else cout<<equation<<fixed<<setprecision(8)<<number.num0<<endl;/输出结果控制精度8位小数 /调试时检查运算结束后站内情况的代码段void menu()/