数据结构课程设计报告
实验一：计算器
设计要求
1、问题描述：设计一个计算器，可以实现计算器的简单运算，输出并检验结果的正确性，以及检验运算表达式的正确性。
2、输入：不含变量的数学表达式的中缀形式，可以接受的操作符包括+、-、*、/、%、(、)。
具体事例如下：
3、输出：如果表达式正确，则输出表达式的正确结果；如果表达式非法，则输出错误信息。
具体事例如下：
知识点：堆栈、队列
实际输入输出情况：
正确的表达式
对负数的处理
表达式括号不匹配
表达式出现非法字符
表达式中操作符位置错误
求余操作符左右出现非整数
其他输入错误
数据结构与算法描述
解决问题的整体思路：
将用户输入的中缀表达式转换成后缀表达式，再利用转换后的后缀表达式进行计算得出结果。
解决本问题所需要的数据结构与算法：
用到的数据结构是堆栈。主要算法描述如下：
A．将中缀表达式转换为后缀表达式：
1. 将中缀表达式从头逐个字符扫描，在此过程中，遇到的字符有以下几种情况：
1）数字
2）小数点
3）合法操作符+ - * / %
4）左括号
5）右括号
6）非法字符
2. 首先为操作符初始化一个map 3. 对于输入的字符串from和输出的字符串to，采用以下过程： 初始化遍历器 std::string::iterator it=infix.begin() 在当it!=from.end()，执行如下操作 4. 遇到数字或小数点时将其加入到后缀表达式： case '1':case '2':case '3':case'4':case '5':case '6':case'7':case '8':case'9':case '0':case '.': { to=to+*it; break; } 5. 遇到操作符（+，-，*，/，%）时，如果此时栈顶操作符的优先级比此时的操作符优先级低，则将其入栈，否则将栈中的操作符从栈顶逐个加入到后缀表达式，直到栈空或者遇到左括号，并将此时的操作符加入到栈中，在此过程中需判断表达式中是否出现输入错误： case '+':case '-':case '*':case '/':case '%': { if((it+1)==from.end()) { cout<<"输入错误：运算符号右边缺少运算数"< } if((*it=='*'||*it=='/')&&it==from.begin()) { cout<<"输入错误：运算符号左边缺少运算数"< } if((it+1)!=from.end()&&(*(it+1)=='+'||*(it+1)=='-'||*(it+1)=='*'||*(it+1)=='/'||*(it+1)=='%')) { cout<<"输入错误：运算符号连续出现"< } to=to+" "; if(sym.empty()) { sym.push(*it); break; } tem=sym.top(); while(pri[*it]<=pri[tem]&&!sym.empty()&&tem!='(') { to=to+tem+" "; sym.pop(); if(sym.empty())break; tem=sym.top(); } sym.push(*it); break; } 6. 遇到“（”时，直接将其加入操作符栈，并且检测输入错误，并且当括号后的第一个符号为-时，说明用户试图输入负号，这种情况我们向目标表达式输出一个0，以达到处理负号的目的： case '(': { if((it+1)==from.end()) { cout<<"输入错误：表达式以左括号结尾"< } //若以+或者-开头，则按照正负号看待，向目标表达式中加入一个0 if(*(it+1)=='-'||*(it+1)=='+') { to=to+'0'; } if((it+1)!=from.end()&&((*(it+1)=='*'||*(it+1)=='/'||*(it+1)=='%'||*(it+1)==')'))) { cout<<"输入错误：左括号右边不能为运算符号或右括号"< } if(it!=from.begin()&&(*(it-1)!='+'&&*(it-1)!='-'&&*(it-1)!='*'&&*(it-1)!='/'&&*(it-1)!='%'&&*(it-1)!='(')) { cout<<"输入错误：左括号左边不能为运算数或右括号"< } sym.push(*it); break; } 5.遇到“）”时，将栈中的操作符从栈顶逐个弹出并放入后缀表达式中，直到在栈中遇到“（”，并将“（”从栈中弹出： case ')': { if((it+1)!=from.end()&&*(it+1)!='+'&&*(it+1)!='-'&&*(it+1)!='*'&&*(it+1)!='/'&&*(it+1)!='%'&&*(it+1)!=')') { cout<<"输入错误：右括号右边不能为运算数"< } if(it!=from.begin()&&(*(it-1)=='+'||*(it-1)=='-'||*(it-1)=='*'||*(it-1)=='/'||*(it-1)=='%')) { cout<<"输入错误：右括号左边不能为运算符号"< } to=to+" "; if(sym.empty()) { cout<<"输入错误：表达式以右括号开始"< } tem=sym.top(); while(tem!='(') { to=to+tem+" "; sym.pop(); if(sym.empty()) { cout<<"输入错误：括号匹配有误"< } tem=sym.top(); } sym.pop(); break; } B．计算后缀表达式的主要思想： 逐个字符的扫描后缀表达式，遇到单个数字或小数点时则先将其将其存到一个字符串中，当遇到后缀表达式中的分隔符（这里使用空格）时，则将这个字符串转化为数字放到堆栈numstack中； case '1':case '2':case '3':case'4':case '5':case '6':case'7':case '8':case'9':case '0':case '.': { numtemp+=*it; break; } case ' ': { if(numtemp!="") { if(numtemp.find('.')&&numtemp.find('.',(numtemp.find('.')+1))!=string::npos) { cout<<"输入错误：小数点数目超出："+numtemp< } strm.str(numtemp); strm>>d; numstack.push(d); numtemp=""; strm.str(""); strm.clear(); break; } break; } 2.遇到操作符+，-，*，/，%时，将堆栈numstack中的栈顶的两个数取出来，进行相应操作的运算，并将结果加入到堆栈numstack中； case '+': { d2=numstack.top(); numstack.pop(); d1=numstack.top(); numstack.pop(); numstack.push(d1+d2); break; } case '-': { d2=numstack.top(); numstack.pop(); d1=numstack.top(); numstack.pop(); numstack.push(d1-d2); break; } case '*': { d2=numstack.top(); numstack.pop(); d1=numstack.top(); numstack.pop(); numstack.push(d1*d2); break; } case '/': { d2=numstack.top(); numstack.pop(); if(fabs(d2)<0.0000001) { cout<<"输入错误：除数不能为0"< } d1=numstack.top(); numstack.pop(); numstack.push(d1/d2); break; } case '%': { d2=numstack.top(); numstack.pop(); d1=numstack.top(); numstack.pop(); if((fabs(d2-(int)d2))<0.0000001&&(fabs(d1-(int)d1))<0.0000001) { int n1=(int)d1; int n2=(int)d2; numstack.push((double)(n1%n2)); break; } else { cerr<<"输入错误：求模操作只能作用于整数"< } } 3.直到后缀表达式扫描完并且堆栈numstack中只有一个数值，则此数值为计算的最终结果，否则说明输入有误。 分析与探讨： 1、测试结果分析： 测试结果见本篇开始的实际输入输出结果。 该计算器几乎实现了所有相关功能，包括简单计算、负数小数处理，容错，并且健壮性好，对于错误的表达式可以给出适当提示，不会导致程序崩溃。 2、算法分析 1、对于中缀表达式转换成后缀表达式： 时间复杂性为O(n) 2、对于后缀表达式的计算：时间复杂性为O(n) 综上，该程序算法的时间复杂度为O(n) 3、算法改进 该程序存在的主要问题是命令行式的用户界面不够友好。Windows下的用户图形界面需要MFC方面的知识，因为时间关系没有进行这方面的深入学习。 附录：源代码 文件一.ExpressionHandler.h #include #include
