数据结构课程设计-表达式求值.doc

《数据结构》课程设计

表达式求值

目录
1. 课程设计的目的····························3
2. 需求分析··································3
3. 概要设计··································4
4. 详细设计··································5
5. 调试分析··································8
6. 用户手册··································9
7. 测试结果··································9
8. 程序清单···································9
9. 小结·······································13
10. 参考文献···································13

1. 课程设计的目的
1)、对数据结构基本理论和存储结构及算法设计有更加深入的理解；
2)、了解栈的特性，以便在实际问题背景下灵活运用他们；
3)、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;
4)、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;
5)、提高综合运用所学的理论知识和方法独立分析和解决问题的能力;

2. 需求分析
编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。
主要功能描述如下：
①从键盘上输入表达式;
②分析该表达式是否合法(是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中;是规定的运算符，则根据规则进行处理,在处理过程中，将计算该表达式的值;若是其它字符，则返回错误信息。
③若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。
这是一个利用栈结构完成的程序为了实现运算符优先算法，可以使用两个栈，一个操作符栈OPTR，一个操作数栈OPND。①首先置操作数栈为空栈，表达式结束符#为操作符栈的栈底元素。②依次读入表达式中的每一个字符，若是操作数则如OPND栈；若是操作符则OPTR栈的栈顶运算符比较它们的优先级然后再做相应操作。

3、概要设计
（1）主界面设计
有提示表达式输入和以#结束的信息即可。如下所示：

（2）存储结构设计
采用顺序栈结构类型存储表达式计算中的数据，程序中应该建立两个栈，一个栈存放操作数，一个存放操作符。
（3）算术优先级判断
char Precede(char op1,char op2) //操作符优先级判断处理
{
if(op2=='#') return '>';

if(op1=='+' || op1=='-')
{
if(op2=='+' || op2=='-' || op2==')')
return '>';
return '<';
}
if(op1=='*' || op1=='/')
{
if(op2=='(') return '<';
return '>';
}
if(op1=='(')
{
if(op2==')') return '=';
return '<';
}
if(op1=='')
{
if(op2=='#') return '=';
else return '<';
}
return '>';
}

4、详细设计
（1）结构定义
typedef union _Elem //栈元素类型定义，用Union可以表示运算数或运算符
{
double fval;
char cval;
}ElemType;

typedef struct _Stack //定义栈类型
{
ElemType data[MAX_LENGTH];
int cur;
}Stack;

（2）函数定义
BOOL InitStack(Stack* T) //初始化栈
{
if(T==0) return false;
T->cur = 0;
return true;
}

BOOL Push(Stack* T, ElemType e) //出栈以e返回
{
if(T==0) return false;
if(T->cur>=MAX_LENGTH-1) return false;
T->cur ++;
T->data[T->cur] = e;

return true;
}

BOOL Top(Stack* T, ElemType* e) //以e取栈顶元素
{
if(T==0 || e==0) return false;
if(T->cur<0) return false;
*e = T->data[T->cur];
return true;
}
BOOL Pop(Stack*T, ElemType* e) //出栈，以e返回
{
if(T==0) return false;
if(T->cur<0) return false;
if(e!=0) *e = T->data[T->cur];
T->cur --;
return true;
}
int GetLength(Stack* T) //得到栈的长度
{
if(T==0) return -1;
return T->cur + 1;
}
int IsOperator(int c) //判断是否为操作符
{
if(c=='+' || c=='-' || c=='*' || c=='/' || c=='(' || c==')' || c=='#') return 1;
return 0;
}
//读入表达式的下一项（运算数或运算符）
OType ReadNextTerm(ElemType* e)
{
int c = getchar();
if(c==EOF) return 0
if(IsOperator(c))
{
e->cval = c;
printf("%c",c);
return Operator;
}
if(isdigit(c))
{
double v;
ungetc(c,stdin);
scanf("%lf",&v);
e->fval = v;
printf("%f",v);
return Operand;
}
return Fail;
}
char Precede(char op1,char op2) //操作符优先级判断处理
{
if(op2=='#') return '>';

if(op1=='+' || op1=='-')
{
if(op2=='+' || op2=='-' || op2==')')
return '>';
return '<';
}
if(op1=='*' || op1=='/')
{
if(op2=='(') return '<';
return '>';
}
if(op1=='(')
{
if(op2==')') return '=';
return '<';
}
if(op1=='#')
{
if(op2=='#') return '=';
else return '<';
}
return '>';
}

5、调试分析
（1）合法数据测试

（2）非法数据测试（未以#结尾，便一直等待输入）

6、用户手册
本程序在CodeBlock上编译，若在vc6上编译可能出现错误，表达式输入时要以#结束。界面上有提示。如上截图所示。

7、测试结果
运行正常，截图如下:

8、 程序清单
/*************表达式求值*******************/
#include
#include
#include
#include

#define MAX_LENGTH 100//栈的最大长度
typedef enum {Fail = 0, Operator=1, Operand=2} OType;
typedef enum {false=0,true=1} BOOL;

typedef union _Elem //栈元素类型定义，用Union可以表示运算数或运算符
{
double fval;
char cval;
}ElemType;

typedef struct _Stack //定义栈类型
{
ElemType data[MAX_LENGTH];
int cur;
}Stack;

BOOL InitStack(Stack* T) //初始化栈
{
if(T==0) return false;
T->cur = 0;
return true;
}

BOOL Push(Stack* T, ElemType e) //出栈以e返回
{
if(T==0) return false;
if(T->cur>=MAX_LENGTH-1) return false;
T->cur ++;
T->data[T->cur] = e;

return true;
}

BOOL Top(Stack* T, ElemType* e) //以e取栈顶元素
{
if(T==0 || e==0) return false;
if(T->cur<0) return false;
*e = T->data[T->cur];
return true;
}
BOOL Pop(Stack*T, ElemType* e) //出栈，以e返回
{
if(T==0) return false;
if(T->cur<0) return false;
if(e!=0) *e = T->data[T->cur];
T->cur --;
return true;
}
int GetLength(Stack* T) //得到栈的长度
{
if(T==0) return -1;
return T->cur + 1;
}
int IsOperator(int c) //判断是否为操作符
{
if(c=='+' || c=='-' || c=='*' || c=='/' || c=='(' || c==')' || c=='#') return 1;
return 0;
}
//读入表达式的下一项（运算数或运算符）
OType ReadNextTermElemType* e)
{
int c = getchar();
if(c==EOF) return 0;
if(IsOperator(c))
{
e->cval = c;
printf("%c",c);
return Operator;
}
if(isdigit(c))
{
double v;
ungetc(c,stdin);
scanf("%lf",&v);
e->fval = v;
printf("%f",v);
return Operand;
}
return Fail;
}
char Precede(char op1,char op2) //操作符优先级判断处理
{
if(op2=='#') return '>';

if(op1=='+' || op1=='-')
{
if(op2=='+' || op2=='-' || op2==')')
return '>';
return '<';
}
if(op1=='*' || op1=='/')
{
if(op2=='(') return '<';
return '>';
}
if(op1=='(')
{
if(op2==')') return '=';
return '<';
}
if(op1=='#')
{
if(op2=='#') return '=';
else return '<';
}
return '>';
}

int main(int argc,char* argv[])
{
Stack operatorStack;//运算符栈
Stack operandStack;//运算数栈
InitStack(&operatorStack);
InitStack(&operandStack);
printf("\n/********************欢迎使用表达式求值程序**********************/\n\n");
printf("请输入一个算术表达式(以#结束)，如:(3+2)*4/6-3#\n");

ElemType e;
e.cval = '#';
Push(&operatorStack,e);
int atype = ReadNextTerm(&e);
ElemType top;
Top(&operatorStack,&top);
while(e.cval != '#'|| top.cval!='#')
{
if(atype==Operator)
{
switch(Precede(top.cval,e.cval))
{
case '<':
{
Push(&operatorStack,e); //将操作符压栈
atype = ReadNextTerm(&e);
break;
}
case '>':
{
ElemType v1,v2;
Pop(&operandStack,&v1); //将两个操作数出栈
Pop(&operandStack,&v2);
Pop(&operatorStack,0);
switch(top.cval)
{
case '+': v2.fval += v1.fval;break;
case '-' : v2.fval -= v1.fval; break;
case '*' : v2.fval *= v1.fval; break;
case '/' : v2.fval /= v1.fval; break;
}
Push(&operandStack,v2);//将操作数压栈
break;
}
case '=':
{
Pop(&operatorStack,0);
atype = ReadNextTerm(&e);
break;
}
}
}
else
{
Push(&operandStack,e); //将操作数压栈
atype = ReadNextTerm(&e);
}
Top(&operatorStack,&top);
}

Top(&operandStack,&e);
printf("=");
printf("%f\n",e.fval);
printf("谢谢使用\n");
return 0;
}
9、 小结
通过对本程序的编写，我对栈的应用更加的了解了，同时又是对原来知识的一种温习、巩固和提高。是将理论化为实践的一个过程。虽然设计的过程中吃了不少苦，但是我觉得这一切都是值得的。设计时使我充分认识到了自己的不足，完成后的成就感又大大增加了我的自信心。
10、 参考文献
严蔚敏，吴伟民 编著. 数据结构(C 语言版)-- 清华大学出版社；
严蔚敏，吴伟民 米宁 编著. 数据结构题集(C 语言版)-- 清华大学出版社； 参考以前数据结构课上老师讲解的四则运算程序。