《数据结构和算法设计》实验报告

实验报告

——实验二

一、实验目的 

按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。

二、实验内容 

   简单计算器。

请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。要求：

1从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。

2输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取整。

例如，输入：4+2*5=                输出：14

      输入：(4+2)*(2-10)=            输出：-48

三、程序设计 

概要设计

1、宏定义

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

2、基本函数：

（1）void InitStack_char(SqStack *S) //char型栈初始化

（2）void InitStack_int(sqStack *S) //int型栈初始化

（3）void Push_char(SqStack *S,char ch) //char型元素进栈

（4）void Push_int(sqStack *S,int num) //int型元素进栈

（5）char GetTop_char(SqStack *S) //取char型栈顶元素

（6）int GetTop_int(sqStack *S) //取int型栈顶元素

（7）Status In(char c) //判断是否为运算符，若是运算符则返回，否则返回

（8）char Precede(char a,char b) //判断两运算符的先后次序

（9）Status Pop_char(SqStack *S,char &x) //char型栈出栈

（10）Status Pop_int(sqStack *S,int &x) //int型栈出栈

（11）int Operate(int a,char theta,int b) //计算a和b运算结果

3、流程图

详细设计

数据类型

typedef struct node             //构造char型栈

{

    char ch;

    struct node *next;

}node;         

typedef struct             

{

    struct node *base;

    struct node *top;

}SqStack;

typedef struct lnode             //构造int型栈

{

    int num;

    struct lnode *next;

}lnode;         

typedef struct             

{

    struct lnode *base;

    struct lnode *top;

}sqStack; 

操作部分

void InitStack_char(SqStack *S)

{

    S->base = (node *)malloc(sizeof(node));

    S->base->next=NULL;

    S->top = S->base;

}                                //char型栈初始化

void InitStack_int(sqStack *S)

{

    S->base = (lnode *)malloc(sizeof(lnode));

    S->base->next=NULL;

    S->top = S->base;

}                                //int型栈初始化

void Push_char(SqStack *S,char ch)

{

    node *p;

    p=(node*)malloc(sizeof(node));

    p->ch=ch;

    p->next=S->top;

    S->top=p;

}                                 //char型元素进栈

Status Push_int(sqStack *S,int num)

{

    lnode *p;

    p=(lnode*)malloc(sizeof(lnode));

    p->num=num;

    p->next=S->top;

    S->top=p;

    return OK;

}                                 //int型元素进栈

char GetTop_char(SqStack *S)

{

    return (S->top->ch);

}                                 //取char型栈顶元素

int GetTop_int(sqStack *S)

{

    return (S->top->num);

}                                  //取int型栈顶元素

Status Pop_char(SqStack *S,char &x)

{

    if(S->base == S->top)

        return ERROR;

    node *p;

    p=S->top;

    x=p->ch;

    S->top=p->next;

    free(p);

    return OK;

}                                 //char型栈出栈

Status Pop_int(sqStack *S,int &x)

{

    if(S->base == S->top)

        return ERROR;

    lnode *p;

    p=S->top;

    x=p->num;

    S->top=p->next;

    free(p);

    return OK;

}                                  //int型栈出栈

计算功能

int Operate(int a,char theta,int b)

{

    int i,z = 1;

    switch(theta)

    {

    case '+':z = (a + b);break;

    case '-':z = (a - b);break;

    case '*':z = (a * b);break;

    case '/':z = (a / b);break;

    case '^':

        for(i = 1;i<=b;i++)

            z = z*a;

        break;

    }

    return (z);

}                                  //计算a和b运算结果

Status In(char c)

{

    if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='='||c=='^')

        return OK;

    else

        return ERROR;

}                                  //判断是否为运算符

char Precede(char a,char b)

{

    if(a=='+'||a=='-')

    {

        if(b=='+'||b=='-'||b==')'||b=='=')

            return '>';

        else

            return '<';

    }

    if(a=='*'||a=='/')

    {

        if(b=='('||b=='^')

            return '<';

        else

            return '>';

    }

    if(a=='(')

    {

        if(b==')')

            return '=';

        else

            return '<';

    }

    if(a==')')

    {

        if(b!='(')

            return '>';

    }

    if(a=='#')

    {

        if(b=='=')

            return '=';

        else

            return '<';

    }

    if(a=='^')

        return ('>');

}                                  //判断两运算符的先后次序

主函数

int main()                         //主函数

{

    char c,x,theta;

    int a,b,c1;             //定义变量

    SqStack OPTR;                  //定义字符栈

    sqStack OPNR;                  //定义整型栈

    InitStack_char(&OPTR);              //初始化

    InitStack_int(&OPNR);              //初始化

    Push_char(&OPTR,'#');               //将字符型栈底设为#

    c = getchar();                 //从键盘输入得到字符    

    while(c!='='||GetTop_char(&OPTR)!='#')   //判定是否执行循环

    {

        if(!In(c))

        {

            c1 = 0;

            while(!In(c))

            {

                c1 = c1*10+c-'0';

                c = getchar();

            }

            Push_int(&OPNR,c1);

        }                             //当扫描字符不是运算符时，转化为整型数存入栈中

        else

        {

            switch(Precede(GetTop_char(&OPTR),c))    //判定运算符的优先关系

            {

            case '<':

                Push_char(&OPTR,c);c = getchar();break; //当前运算符优先级高，存入char栈

            case '=':

                Pop_char(&OPTR,c);c = getchar();break;  //运算符次序相等，存入char栈

            case '>': //当前运算符优先级低

                Pop_char(&OPTR,theta);

                Pop_int(&OPNR,b);

                Pop_int(&OPNR,a);

                Push_int(&OPNR, Operate(a,theta,b));//计算运算结果，并存入int栈

                break;                              //继续循环

            }

        }

    }

    printf("%d\\n",GetTop_int(&OPNR));                //计算完成，取出int栈顶元素，并输出

    return 0;

}四、程序调试分析

编写程序的过程中遇到了很多的问题，最突出的两个问题就是整数和两位数的运算处理，一开始修改了主函数部分之后，原来可以执行一位数运算的程序出现了error，由于没有及时保存，并且之前的代码无法恢复，只得重新编写一次。第二次编写理清思路之后，在课本和网上资料的辅助下，终于成功的编出了程序并且可以完美执行。经验告诉了我在编程的时候一定要注意经常进行调试，只有学会调试才能处理好大程序的编写，否则极其容易出错。

五、用户使用说明 

1.运行程序，

2.将整个表达式从键盘键入，以“=”结束，回车可得到结果。

六、程序运行结果

（1）输入：（11+3）*5=                输出：70

（2）输入：(31-13)/(9-3)=        输出：6

七、程序清单

#include

#include

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

typedef int Status;

typedef struct node             //构造char型栈

{

    char ch;

    struct node *next;

}node;         

typedef struct             

{

    struct node *base;

    struct node *top;

}SqStack;

typedef struct lnode             //构造int型栈

{

    int num;

    struct lnode *next;

}lnode;         

typedef struct             

{

    struct lnode *base;

    struct lnode *top;

}sqStack; 

void InitStack_char(SqStack *S)

{

    S->base = (node *)malloc(sizeof(node));

    S->base->next=NULL;

    S->top = S->base;

}                                //char型栈初始化

void InitStack_int(sqStack *S)

{

    S->base = (lnode *)malloc(sizeof(lnode));

    S->base->next=NULL;

    S->top = S->base;

}                                //int型栈初始化

void Push_char(SqStack *S,char ch)

{

    node *p;

    p=(node*)malloc(sizeof(node));

    p->ch=ch;

    p->next=S->top;

    S->top=p;

}                                 //char型元素进栈

Status Push_int(sqStack *S,int num)

{

    lnode *p;

    p=(lnode*)malloc(sizeof(lnode));

    p->num=num;

    p->next=S->top;

    S->top=p;

    return OK;

}                                 //int型元素进栈

char GetTop_char(SqStack *S)

{

    return (S->top->ch);

}                                 //取char型栈顶元素

int GetTop_int(sqStack *S)

{

    return (S->top->num);

}                                  //取int型栈顶元素

Status Pop_char(SqStack *S,char &x)

{

    if(S->base == S->top)

        return ERROR;

    node *p;

    p=S->top;

    x=p->ch;

    S->top=p->next;

    free(p);

    return OK;

}                                 //char型栈出栈

Status Pop_int(sqStack *S,int &x)

{

    if(S->base == S->top)

        return ERROR;

    lnode *p;

    p=S->top;

    x=p->num;

    S->top=p->next;

    free(p);

    return OK;

}                                  //int型栈出栈

int Operate(int a,char theta,int b)

{

    int i,z = 1;

    switch(theta)

    {

    case '+':z = (a + b);break;

    case '-':z = (a - b);break;

    case '*':z = (a * b);break;

    case '/':z = (a / b);break;

    case '^':

        for(i = 1;i<=b;i++)

            z = z*a;

        break;

    }

    return (z);

}                                  //计算a和b运算结果

Status In(char c)

{

    if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='='||c=='^')

        return OK;

    else

        return ERROR;

}                                  //判断是否为运算符

char Precede(char a,char b)

{

    if(a=='+'||a=='-')

    {

        if(b=='+'||b=='-'||b==')'||b=='=')

            return '>';

        else

            return '<';

    }

    if(a=='*'||a=='/')

    {

        if(b=='('||b=='^')

            return '<';

        else

            return '>';

    }

    if(a=='(')

    {

        if(b==')')

            return '=';

        else

            return '<';

    }

    if(a==')')

    {

        if(b!='(')

            return '>';

    }

    if(a=='#')

    {

        if(b=='=')

            return '=';

        else

            return '<';

    }

    if(a=='^')

        return ('>');

}                                  //判断两运算符的先后次序

int main()                         //主函数

{

    char c,x,theta;

    int a,b,c1;             //定义变量

    SqStack OPTR;                  //定义字符栈

    sqStack OPNR;                  //定义整型栈

    InitStack_char(&OPTR);              //初始化

    InitStack_int(&OPNR);              //初始化

    Push_char(&OPTR,'#');               //将字符型栈底设为#

    c = getchar();                 //从键盘输入得到字符    

    while(c!='='||GetTop_char(&OPTR)!='#')   //判定是否执行循环

    {

        if(!In(c))

        {

            c1 = 0;

            while(!In(c))

            {

                c1 = c1*10+c-'0';

                c = getchar();

            }

            Push_int(&OPNR,c1);

        }                             //当扫描字符不是运算符时，转化为整型数存入栈中

        else

        {

            switch(Precede(GetTop_char(&OPTR),c))    //判定运算符的优先关系

            {

            case '<':

                Push_char(&OPTR,c);c = getchar();break; //当前运算符优先级高，存入char栈

            case '=':

                Pop_char(&OPTR,c);c = getchar();break;  //运算符次序相等，存入char栈

            case '>': //当前运算符优先级低

                Pop_char(&OPTR,theta);

                Pop_int(&OPNR,b);

                Pop_int(&OPNR,a);

                Push_int(&OPNR, Operate(a,theta,b));//计算运算结果，并存入int栈

                break;                              //继续循环

            }

        }

    }

    printf("%d\\n",GetTop_int(&OPNR));                //计算完成，取出int栈顶元素，并输出

    return 0;

}