数据结构课程设计-计算器

  数据结构课程设计报告

实验一：计算器

设计要求

1、问题描述：设计一个计算器，可以实现计算器的简单运算，输出并检验结果的正确性，以及检验运算表达式的正确性。

2、输入：不含变量的数学表达式的中缀形式，可以接受的操作符包括+、-、*、/、%、(、)。

具体事例如下：

3、输出：如果表达式正确，则输出表达式的正确结果；如果表达式非法，则输出错误信息。

具体事例如下：

   知识点：堆栈、队列

实际输入输出情况：

正确的表达式

对负数的处理

表达式括号不匹配

表达式出现非法字符

表达式中操作符位置错误

求余操作符左右出现非整数

其他输入错误

数据结构与算法描述

解决问题的整体思路：

将用户输入的中缀表达式转换成后缀表达式，再利用转换后的后缀表达式进行计算得出结果。

解决本问题所需要的数据结构与算法：

用到的数据结构是堆栈。主要算法描述如下：

A．将中缀表达式转换为后缀表达式： 

1. 将中缀表达式从头逐个字符扫描，在此过程中，遇到的字符有以下几种情况：

1）数字

2）小数点

3）合法操作符+ - * / %

4）左括号

5）右括号

6）非法字符

2. 首先为操作符初始化一个map priority，用于保存各个操作符的优先级，其中+ -为0，* / %为1

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<<"输入错误：运算符号右边缺少运算数"<                    return false;

                }

                if((*it=='*'||*it=='/')&&it==from.begin())

                {

                 cout<<"输入错误：运算符号左边缺少运算数"<                    return false;

                }

if((it+1)!=from.end()&&(*(it+1)=='+'||*(it+1)=='-'||*(it+1)=='*'||*(it+1)=='/'||*(it+1)=='%'))

                {

                 cout<<"输入错误：运算符号连续出现"<                    return false;

                }

                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<<"输入错误：表达式以左括号结尾"<                    return false;

                }

//若以+或者-开头，则按照正负号看待，向目标表达式中加入一个0

                if(*(it+1)=='-'||*(it+1)=='+')

                {

                    to=to+'0';

                }

                if((it+1)!=from.end()&&((*(it+1)=='*'||*(it+1)=='/'||*(it+1)=='%'||*(it+1)==')')))

                {

                 cout<<"输入错误：左括号右边不能为运算符号或右括号"<                    return false;

                }

                if(it!=from.begin()&&(*(it-1)!='+'&&*(it-1)!='-'&&*(it-1)!='*'&&*(it-1)!='/'&&*(it-1)!='%'&&*(it-1)!='('))

                {

                 cout<<"输入错误：左括号左边不能为运算数或右括号"<                    return false;

                }

                sym.push(*it);

                break;

            }

5.遇到“）”时，将栈中的操作符从栈顶逐个弹出并放入后缀表达式中，直到在栈中遇到“（”，并将“（”从栈中弹出：

case ')':

            {

                if((it+1)!=from.end()&&*(it+1)!='+'&&*(it+1)!='-'&&*(it+1)!='*'&&*(it+1)!='/'&&*(it+1)!='%'&&*(it+1)!=')')

                {

                 cout<<"输入错误：右括号右边不能为运算数"<                    return false;

                }

                if(it!=from.begin()&&(*(it-1)=='+'||*(it-1)=='-'||*(it-1)=='*'||*(it-1)=='/'||*(it-1)=='%'))

                {

                 cout<<"输入错误：右括号左边不能为运算符号"<                    return false;

                }

                to=to+" ";

                if(sym.empty())

                    {

                     cout<<"输入错误：表达式以右括号开始"<                        return false;

                    }

                tem=sym.top();

                while(tem!='(')

                {

                    to=to+tem+" ";

                    sym.pop();

                    if(sym.empty())

                    {

                     cout<<"输入错误：括号匹配有误"<                        return false;

                    }

                    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<                        return false;

                    }

                    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"<                    return false;

                }

                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<<"输入错误：求模操作只能作用于整数"<                    return false;

                }

            }                

3.直到后缀表达式扫描完并且堆栈numstack中只有一个数值，则此数值为计算的最终结果，否则说明输入有误。

分析与探讨：

1、测试结果分析：

测试结果见本篇开始的实际输入输出结果。

该计算器几乎实现了所有相关功能，包括简单计算、负数小数处理，容错，并且健壮性好，对于错误的表达式可以给出适当提示，不会导致程序崩溃。

2、算法分析

  1、对于中缀表达式转换成后缀表达式： 时间复杂性为O(n)

  2、对于后缀表达式的计算：时间复杂性为O(n)

综上，该程序算法的时间复杂度为O(n)

3、算法改进

  该程序存在的主要问题是命令行式的用户界面不够友好。Windows下的用户图形界面需要MFC方面的知识，因为时间关系没有进行这方面的深入学习。

附录：源代码

文件一.ExpressionHandler.h

#include

#include

#include

#include

#include

using namespace std;

class ExpressionHandler{

public:

    ExpressionHandler(string exp){

        this->exp=exp;

    }

    bool infixtoprofix(string& exp);

    bool doprofix(string profix,double &result);

private:

    string exp;

};

文件二.ExpressionHandler.cpp

//Coded By CS_Zhanglin

#include"ExpressionHandler.h"

bool ExpressionHandler::infixtoprofix(string& exp){

    string from=this->exp;

    string to="";

    stack sym;

    map pri;

    char tem;

    pri['+']=1;

    pri['-']=1;

    pri['*']=2;

    pri['/']=2;

    pri['%']=2;

    string::iterator it=from.begin();

    if(*it=='+'||*it=='-')to+='0';

    while(it!=from.end()){

        //cout<<1<        switch(*it)

        {

        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;    

            }

        case '+':case '-':case '*':case '/':case '%':

            {

                if((it+1)==from.end())

                {

                 cout<<"输入错误：运算符号右边缺少运算数"<                    return false;

                }

                if((*it=='*'||*it=='/')&&it==from.begin())

                {

                 cout<<"输入错误：运算符号左边缺少运算数"<                    return false;

                }

                if((it+1)!=from.end()&&(*(it+1)=='+'||*(it+1)=='-'||*(it+1)=='*'||*(it+1)=='/'||*(it+1)=='%'))

                {

                 cout<<"输入错误：运算符号连续出现"<                    return false;

                }

                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;

            }

        case '(':

            {

                if((it+1)==from.end())

                {

                 cout<<"输入错误：表达式以左括号结尾"<                    return false;

                }

                if(*(it+1)=='-'||*(it+1)=='+')

                {

                    to=to+'0';

                }

                if((it+1)!=from.end()&&((*(it+1)=='*'||*(it+1)=='/'||*(it+1)=='%'||*(it+1)==')')))

                {

                 cout<<"输入错误：左括号右边不能为运算符号或右括号"<                    return false;

                }

                if(it!=from.begin()&&(*(it-1)!='+'&&*(it-1)!='-'&&*(it-1)!='*'&&*(it-1)!='/'&&*(it-1)!='%'&&*(it-1)!='('))

                {

                 cout<<"输入错误：左括号左边不能为运算数或右括号"<                    return false;

                }

                sym.push(*it);

                break;

            }

        case ')':

            {

                if((it+1)!=from.end()&&*(it+1)!='+'&&*(it+1)!='-'&&*(it+1)!='*'&&*(it+1)!='/'&&*(it+1)!='%'&&*(it+1)!=')')

                {

                 cout<<"输入错误：右括号右边不能为运算数"<                    return false;

                }

                if(it!=from.begin()&&(*(it-1)=='+'||*(it-1)=='-'||*(it-1)=='*'||*(it-1)=='/'||*(it-1)=='%'))

                {

                 cout<<"输入错误：右括号左边不能为运算符号"<                    return false;

                }

                to=to+" ";

                if(sym.empty())

                    {

                     cout<<"输入错误：表达式以右括号开始"<                        return false;

                    }

                tem=sym.top();

                while(tem!='(')

                {

                    to=to+tem+" ";

                    sym.pop();

                    if(sym.empty())

                    {

                     cout<<"输入错误：括号匹配有误"<                        return false;

                    }

                    tem=sym.top();

                }

                sym.pop();

                break;

            }

        default:

            {

             cout<<"输入错误：未知符号"<                return false;

            }

        }

        ++it;

    }

    if(!sym.empty())

    {

        to=to+" ";

        tem=sym.top();

        while(!sym.empty())

        {

            if(tem=='(')

            {

             cout<<"输入错误：括号匹配有误"<                return false;

            }

            to=to+tem+" ";

            sym.pop();

            if(sym.empty())break;

            tem=sym.top();

        }

    }

    exp=to;

    return true;

}

bool ExpressionHandler::doprofix(string profix,double& result)

{

    string numtemp;

    stack numstack;

    stringstream strm;

    double d,d1,d2;

    for(string::iterator it=profix.begin();it!=profix.end();++it)

    {

        switch (*it)

        {

        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<                        return false;

                    }

                    strm.str(numtemp);

                 strm>>d;

                    numstack.push(d);

                    numtemp="";

                    strm.str("");

                    strm.clear();

                    break;

                }

                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();

                    d1=numstack.top();

                    numstack.pop();

                    numstack.push(d1*d2);

                    break;

                }

            case '/':

                {

                    d2=numstack.top();

                    numstack.pop();

                    if(fabs(d2)<0.0000001)

                    {

                     cout<<"输入错误：除数不能为0"<                        return false;

                    }

                    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<<"输入错误：求模操作只能作用于整数"<                        return false;

                    }

                }

        }

    }

    if(numtemp!="")

    {

        if(numtemp.find('.')&&numtemp.find('.',(numtemp.find('.')+1))!=string::npos)

                {

                 cout<<"输入错误：小数点数目超出："+numtemp<                    return false;

                }

                strm.str(numtemp);

             strm>>d;

                numstack.push(d);

    }

    if(numstack.empty())

    {

     cout<<"输入错误：表达式中没有合法运算数"<        return false;

    }

    result=numstack.top();

    return true;

}

文件三. Main.cpp

#include "ExpressionHandler.h"

int main()

{

    string str;

    double r;

cout<<"请输入一个含有加、减、乘、除或求模运算的表达式，中间不能有空格"< cin>>str;

cout<<"运算结果："<    ExpressionHandler eh(str);

    string result;

    if(eh.infixtoprofix(result))

    {

        if(eh.doprofix(result,r))

     cout<        else cout<<"程序终止"<    }

    else cout<<"程序终止"<    system("pause");

}