数据结构课程设计计算器Word格式文档下载.docx

1、主要算法描述如下：A将中缀表达式转换为后缀表达式：1. 将中缀表达式从头逐个字符扫描，在此过程中，遇到的字符有以下几种情况：1）数字2）小数点3）合法操作符+ - * / %4）左括号5）右括号6）非法字符2. 首先为操作符初始化一个map priority，用于保存各个操作符的优先级，其中+ -为0，* / %为13. 对于输入的字符串from和输出的字符串to，采用以下过程：初始化遍历器 std:string:iterator it=infix.begin（） 在当it!=from.end（），执行如下操作4. 遇到数字或小数点时将其加入到后缀表达式：case 123case4567890

2、. to=to+*it; break; 5. 遇到操作符（+，-，*，/，%）时，如果此时栈顶操作符的优先级比此时的操作符优先级低，则将其入栈，否则将栈中的操作符从栈顶逐个加入到后缀表达式，直到栈空或者遇到左括号，并将此时的操作符加入到栈中，在此过程中需判断表达式中是否出现输入错误：+-*/% if（it+1）=from.end（） cout输入错误：运算符号右边缺少运算数endl; return false; if（*it=|*it=）&it=from.begin（）运算符号左边缺少运算数 if（it+1）!=from.end（）&（*（it+1）=|*（it+1）=）运算符号连续出现 to

3、=to+ ; if（sym.empty（） sym.push（*it）; break; tem=sym.top（）; while（pri*it=pritem&!sym.empty（）&tem!=（） to=to+tem+ sym.pop（）; if（sym.empty（）break; tem=sym.top（）; sym.push（*it）; 6. 遇到“（”时，直接将其加入操作符栈，并且检测输入错误，并且当括号后的第一个符号为-时，说明用户试图输入负号，这种情况我们向目标表达式输出一个0，以达到处理负号的目的：表达式以左括号结尾/若以+或者-开头，则按照正负号看待，向目标表达式中加入一个0

4、if（*（it+1）= to=to+ if（it+1）!（*（it+1）=）左括号右边不能为运算符号或右括号 if（it!=from.begin（）&（*（it-1）!*（it-1）!左括号左边不能为运算数或右括号5.遇到“）”时，将栈中的操作符从栈顶逐个弹出并放入后缀表达式中，直到在栈中遇到“（”，并将“（”从栈中弹出：*（it+1）!右括号右边不能为运算数（*（it-1）=|*（it-1）=右括号左边不能为运算符号 cout表达式以右括号开始 return false; tem=sym.top（）; while（tem! if（sym.empty（）括号匹配有误 sym.pop（）;B计算

5、后缀表达式的主要思想：逐个字符的扫描后缀表达式，遇到单个数字或小数点时则先将其将其存到一个字符串中，当遇到后缀表达式中的分隔符（这里使用空格）时，则将这个字符串转化为数字放到堆栈numstack中； numtemp+=*it; case if（numtemp!= if（numtemp.find（numtemp.find（,（numtemp.find（）+1）!=string:npos）小数点数目超出：+numtempd; numstack.push（d）; numtemp= strm.str（）; strm.clear（）;2.遇到操作符+，-，*，/，%时，将堆栈numstack中的栈顶的两

6、个数取出来，进行相应操作的运算，并将结果加入到堆栈numstack中； d2=numstack.top（）; numstack.pop（）; d1=numstack.top（）; numstack.push（d1+d2）; numstack.push（d1-d2）; numstack.push（d1*d2）; if（fabs（d2）0.0000001）除数不能为0 numstack.push（d1/d2）; if（fabs（d2-（int）d2）0.0000001&（fabs（d1-（int）d1） int n1=（int）d1; int n2=（int）d2; numstack.push（d

7、ouble）（n1%n2）; else cerr求模操作只能作用于整数 3.直到后缀表达式扫描完并且堆栈numstack中只有一个数值，则此数值为计算的最终结果，否则说明输入有误。分析与探讨：1、测试结果分析：测试结果见本篇开始的实际输入输出结果。该计算器几乎实现了所有相关功能，包括简单计算、负数小数处理，容错，并且健壮性好，对于错误的表达式可以给出适当提示，不会导致程序崩溃。2、算法分析 1、对于中缀表达式转换成后缀表达式： 时间复杂性为O（n） 2、对于后缀表达式的计算：时间复杂性为O（n）综上，该程序算法的时间复杂度为O（n）3、算法改进 该程序存在的主要问题是命令行式的用户界面不够友好

8、。Windows下的用户图形界面需要MFC方面的知识，因为时间关系没有进行这方面的深入学习。附录：源代码文件一.ExpressionHandler.h#includemapstackiostreamsstreamusing namespace std;class ExpressionHandlerpublic: ExpressionHandler（string exp） this-exp=exp; bool infixtoprofix（string& exp）; bool doprofix（string profix,double &result）;private: string exp;文件

9、二.ExpressionHandler.cpp/Coded By CS_Zhanglin#includeExpressionHandler.hbool ExpressionHandler:infixtoprofix（string& exp） string from=this-exp; string to= stack sym; map pri; char tem; pri=1;=2; string:iterator it=from.begin（）; if（*it=）to+= while（it!=from.end（） /cout1 switch（*it） default: cout numstack; stringstream strm; double d,d1,d2; for（string:iterator it=profix.begin（）;it!=profix.end（）;+it） switch （*it） case d2=numstack.top（）; numstack.pop（）; d1=numstack.top（）; numstack.push（d1+d2）; numstack.push（d1-d2）; numstack.push（d1*d2）; numstac