数据结构 模拟计算器课程设计

《数据结构》课程设计 实验报告 模拟计算器 班 级： 学 号： 姓 名： 模拟计算器 1、 问题描述 对于模拟计算器的设计，实际便是利用栈对一个表达式求值的问题。 要求： 对包含加，减，乘，除，括号的任意整型表达式进行求解 2、 设计思路 表达式：任何表达式都是由操作数、运算符和界限符组成的有意义的式子。 表达式求值时一般有后缀表示、中缀表示、前缀表示。 操作数：可以是常数、变量、常量。 运算符：从运算对象上分有单目运算符、双目运算符、三目运算符。 界限符：左右括号和表达式结束符。 思  路：我们平时用到的表达式即为我们所输入的表达式（以‘ # ’结束），此表达式为中缀表达式，只要将此表达式利用栈来进出运算的符号转换为后缀表达式，之后利用栈来进出运算的数字将后缀表达式的值求出即可。 3、 数据结构定义 一般表达式的长度不会过长所以将顺序栈的容量设为100已经算是比较大了 具体数据结构如下： # define maxsize  100 typedef double datatype1; typedef char  datatype2; typedef struct stack1 { datatype1 data1[maxsize]; int top1;        /*栈顶元素*/ }seqstack1,*pseqstack1;  /*顺序栈*/ typedef struct stack2 { datatype2 data2[maxsize]; int top2;        /*栈顶元素*/ }seqstack2,*pseqstack2;  /*顺序栈*/ 4、 系统功能模块介绍 （1） 判断字符是否为操作数函数  int isnum(char) 当输入表达式时要利用栈对表达式中的数字和符号进行进栈出栈，因此要判断表达式中的内容是操作数、运算符还是界限符，给出相关信息。 （2） 求运算符优先级函数  int priority(char ) 对输入的表达式中的内容，若为运算符和界限符则要判断其优先级已完成其计算的先后顺序。 （3） 中缀表达式转换为后缀表达式函数  int infix_exp_value(char *,char *) 我们平时使用的为中缀表达式，但若利用栈则利用后缀表达式比较容易计算，因此要将中缀表达式转换为后缀表达式，具体算法步骤如下： <1>count=0，初始化运算符栈s，将结束符‘# ’加入运算符栈s中。 <2>读表达式字符=>w。 <3>当栈顶为‘# ’并且w也是‘# ’时结束；否则循环做下列步骤： <3.1>如果w是操作数 判断若count==0 直接输出,读下一个字符=>w;转<3>。 若 count!=0 追加字符’@’, 读下一个字符=>w, 转<3>。 <3.2>w若是运算符，则： count=1; <3.2.1>如果栈顶为‘（’并且w为‘）’则‘（’出栈不输出，读下一个字 符=>w，转<3>。 <3.2.1>如果栈顶为‘（’或者栈顶优先级小于w优先级，则w入栈，读下 一个字符=>w，转<3>。否则：从运算符栈中出栈并输出，转<3> （4） 后缀表达式的求值函数  double postfix_exp(char *) 使用一个操作数栈，当从左到右扫描表达式时，每遇到一个操作数就送入栈中保存， 如果操作数不止一位，则保存在operand中，遇到下一个操作数时，执行operand=operand*10+(ch-'0')，便可将操作数转化为数字。每遇到一个运算符就从栈中取出两个操作数进行当前的计算，然后把结果在入栈，直到整个表达式结束，这时送入栈顶的值就是结果。 5、 程序清单 # include # include # include # define maxsize  100 typedef double datatype1; typedef char  datatype2; typedef struct stack1 { datatype1 data1[maxsize]; int top1;        /*栈顶元素*/ }seqstack1,*pseqstack1;  /*顺序栈*/ typedef struct stack2 { datatype2 data2[maxsize]; int top2;        /*栈顶元素*/ }seqstack2,*pseqstack2;  /*顺序栈*/ /*栈的初始化*/ pseqstack1 init_seqstack1(void) { pseqstack1 S; S=(pseqstack1)malloc(sizeof(pseqstack1)); if(S) S->top1=-1; return S; } pseqstack2 init_seqstack2(void) { pseqstack2 S; S=(pseqstack2)malloc(sizeof(pseqstack2)); if(S) S->top2=-1; return S; } /*判断栈空*/ int empty_seqstack1(pseqstack1 S) { if(S->top1==-1) return 1; else return 0; } int empty_seqstack2(pseqstack2 S) { if(S->top2==-1) return 1; else return 0; } /*X入栈*/ int push_seqstack1(pseqstack1 S,datatype1 X) { if(S->top1==maxsize-1) { printf("栈满，无法入栈！\n"); return 0; } else { S->top1++; S->data1[S->top1]=X; return 1;    } } int push_seqstack2(pseqstack2 S,datatype2 X) { if(S->top2==maxsize-1) { printf("栈满，无法入栈！\n"); return 0; } else { S->top2++; S->data2[S->top2]=X; return 1;    } } /*X出栈*/ int pop_seqstack1(pseqstack1 S,datatype1 *X) { if(empty_seqstack1(S)) return 0; else { *X=S->data1[S->top1]; S->top1--; return 1;    } } int pop_seqstack2(pseqstack2 S,datatype2 *X) { if(empty_seqstack2(S)) return 0; else { *X=S->data2[S->top2]; S->top2--; return 1;    } } /*求栈顶元素*/ int gettop_seqstack1(pseqstack1 S,datatype1 *X) { if(empty_seqstack1(S)) return 0;          else *X=S->data1[S->top1]; return 1;        } int gettop_seqstack2(pseqstack2 S,datatype2 *X) { if(empty_seqstack2(S)) return 0;          else *X=S->data2[S->top2]; return 1;        } /*判断字符是否为操作数。若是返回1，否则返回0*/ int isnum(char c) { if(c>='0' && c<='9') return 1; else return 0; } /*求后缀表达式的值*/ double postfix_exp(char *A) { pseqstack1 S;    /*定义栈S*/ double operand=0; double result;    /*存放栈顶元素*/ double a;    /*运算符ch前的操作数出栈存入a*/ double b;    /*运算符ch后的操作数出栈存入b*/    double c;    /*c==a ch b*/ char ch;    /*存放读取到的表达式(A)的字符*/ ch=*A++;    /*读表达式字符=>A*/ S=init_seqstack1();    /*初始化栈*/ while(ch!='#')/*遇到元素!='#'时*/ { if(isnum(ch))/*判断ch是否为数字字符,计算出操作数*/ operand=operand*10+(ch-'0'); else    /*否则*/ { if(operand) { push_seqstack1(S,operand);/*当前字符不是数字,操作数结束,要入栈*/ operand=0; } if(ch!='@' && ch!=' ') { pop_seqstack1(S,&b);        /*运算符ch后的操作数出栈存入b*/