《数据结构》算术表达式求值

1、二 课程设计 2算术表达式求值一、需求分析二、程序的主要功能三、程序运行平台四、数据结构五、算法及时间复杂度六、测试用例七、程序源代码三 感想体会与总结算术表达式求值一、需求分析一个算术表达式是由操作数 (operand) 、运算符 (operator) 和界限符 (delimiter) 组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如： #（7+15）* （23-28/4 ）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。二、程序的主要功能（ 1） 从键盘读入一个合法的算术表达式，输出正确的结果。（ 2）

2、 显示输入序列和栈的变化过程。三、程序运行平台Visual C+6.0 版本四、 数据结构本程序的数据结构为栈。（1）运算符栈部分：struct SqStack/ 定义栈char*base;/ 栈底指针char*top;/ 栈顶指针intstacksize;/ 栈的长度;int InitStack (SqStack &s)/建立一个空栈Sif (!(s.base = (char *)malloc(50 * sizeof(char)exit(0);s.top=s.base;s.stacksize=50;return OK;charGetTop(SqStack s,char &e)

3、/ 运算符取栈顶元素if (s.top=s.base)/栈为空的时候返回ERRORprintf(" 运算符栈为空 !n");return ERROR;elsee=*(s.top-1); /栈不为空的时候用 e 做返回值，返回 S 的栈顶元素，并返回 OK return OK;int Push(SqStack &s,char e) /运算符入栈if (s.top-s.base >= s.stacksize)printf(" 运算符栈满 !n");s.base=(char*)realloc (s.base,(s.stacksize+5)*siz

4、eof(char) );/ 栈满的时候，追加 5 个存储空间if(!s.base) exit (OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=5;*(s.top)+=e;/把 e 入栈return OK;int Pop(SqStack &s,char &e) /运算符出栈if (s.top=s.base)/栈为空栈的时候，返回ERRORprintf(" 运算符栈为空 !n");return ERROR;else- 2 -e=*-s.top; /栈不为空的时候用 e 做返回值，删除 S 的栈顶元素，并返回 OK

5、 return OK;int StackTraverse(SqStack &s) /运算符栈的遍历char *t;t=s.base ;if (s.top=s.base)printf(" 运算符栈为空 !n"); /栈为空栈的时候返回 ERROR return ERROR;while(t!=s.top)printf(" %c",*t); /栈不为空的时候依次取出栈内元素t+;return ERROR;（2）数字栈部分：struct SqStackn /定义数栈int*base;/栈底指针int*top;/ 栈顶指针intstacksize;/栈的长

6、度;int InitStackn (SqStackn &s)/建立一个空栈Ss.base=(int*)malloc(50*sizeof(int);if(!s.base)exit(OVERFLOW);/ 存储分配失败s.top=s.base;s.stacksize=50;return OK;intGetTopn(SqStackn s,int &e) /数栈取栈顶元素if (s.top=s.base)printf(" 运算数栈为空 !n"); / 栈为空的时候返回ERRORreturn ERROR;- 3 -elsee=*(s.top-1); / 栈不为空的时候

7、，用 e 作返回值，返回 S 的栈顶元素，并返回 OK return OK;int Pushn(SqStackn &s,int e) /数栈入栈if (s.top-s.base >=s.stacksize)printf(" 运算数栈满 !n"); / 栈满的时候，追加5 个存储空间s.base=(int*)realloc (s.base,(s.stacksize+5)*sizeof(int) );if(!s.base) exit (OVERFLOW);s.top=s.base+s.stacksize; / 插入元素 e 为新的栈顶元素 s.stacksize+

8、=5;*(s.top)+=e; / 栈顶指针变化return OK;int Popn(SqStackn &s,int &e) /数栈出栈if (s.top=s.base)printf("运算符栈为空 !n"); / 栈为空栈的视时候，返回ERRORreturn ERROR;elsee=*-s.top;/栈不空的时候，则删除S 的栈顶元素，用e 返回其值，并返回OKreturn OK;int StackTraversen(SqStackn &s) /数栈遍历int *t;t=s.base ;if (s.top=s.base)printf("

9、运算数栈为空 !n"); / 栈为空栈的时候返回 ERROR return ERROR;while(t!=s.top)- 4 -printf(" %d",*t); / 栈不为空的时候依次输出t+;return ERROR;五、算法及时间复杂度1、算法：建立两个不同类型的空栈，先把一个 #压入运算符栈。输入一个算术表达式的字符串（以 结#束），从第一个字符依次向后读，把读取的数字放入数字栈，运算符放入运算符栈。判断新读取的运算符和运算符栈顶得运算符号的优先级，以便确定是运算还是把运算符压入运算符栈。最后两个 #遇到一起则运算结束。数字栈顶的数字就是要求的结果。2、时

10、间复杂度： O(n)数据压缩存储栈，其操作主要有：建立栈 int Push(SeqStack *S, char x)入栈 int Pop(SeqStack *S, char x)出栈。以上各操作运算的平均时间复杂度为 O(n) ，其主要时间是耗费在输入操作。六、测试用例如图所示。- 5 -最终结果如图所示：七、源代码/* *第七题算术表达式求值问题描述 一个算术表达式是由操作数 (operand) 、运算符 (operator) 和界限符 (delimiter) 组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符 “#，”如： #（7+15 ）*（

11、23-28/4 ） #。引入表达式起始、结束符是为了方便。编程利用 “算符优先法 ”求算术表达式的值。基本要求 （ 1） 从键盘读入一个合法的算术表达式，输出正确的结果。（ 2） 显示输入序列和栈的变化过程。* */#include <stdio.h>#include <string.h>- 6 -#include <stdlib.h>#include <math.h>#include <conio.h>#include <ctype.h>#define OK 1#define ERROR 0#define STACK_I

12、NIT_SIZE 100/#define STACKINCREMENT 10/=/以下定义两种栈，分别存放运算符和数字/=/* 运算符栈部分 *struct SqStack/定义栈char*base;/栈底指针char*top;/栈顶指针intstacksize;/栈的长度;int InitStack (SqStack &s)/ 建立一个空栈 Sif (!(s.base = (char *)malloc(50 * sizeof(char)exit(0);s.top=s.base;s.stacksize=50;return OK;charGetTop(SqStack s,char &am

13、p;e)/运算符取栈顶元素if (s.top=s.base)/栈为空的时候返回ERRORprintf(" 运算符栈为空 !n");return ERROR;elsee=*(s.top-1);/栈不为空的时候用e 做返回值，返回S 的栈顶元素，并返回OKreturn OK;- 7 -int Push(SqStack &s,char e) /运算符入栈if (s.top-s.base >= s.stacksize)printf(" 运算符栈满 !n");s.base=(char*)realloc (s.base,(s.stacksize+5)*

14、sizeof(char) );/栈满的时候，追加 5 个存储空间if(!s.base) exit (OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=5;*(s.top)+=e;/把 e 入栈return OK;int Pop(SqStack &s,char &e) /运算符出栈if (s.top=s.base) /栈为空栈的时候，返回 ERROR printf(" 运算符栈为空 !n");return ERROR;elsee=*-s.top;/栈不为空的时候用e 做返回值，删除S 的栈顶元素，并返回 OKret

15、urn OK;int StackTraverse(SqStack &s) /运算符栈的遍历char *t;t=s.base ;if (s.top=s.base)printf(" 运算符栈为空 !n"); /栈为空栈的时候返回 ERROR return ERROR;while(t!=s.top)- 8 -printf(" %c",*t); / 栈不为空的时候依次取出栈内元素t+;return ERROR;/* 数字栈部分 *struct SqStackn / 定义数栈int*base;/栈底指针int*top;/栈顶指针intstacksize;/

16、栈的长度;int InitStackn (SqStackn &s)/建立一个空栈 Ss.base=(int*)malloc(50*sizeof(int);if(!s.base)exit(OVERFLOW);/存储分配失败s.top=s.base;s.stacksize=50;return OK;intGetTopn(SqStackn s,int &e) /数栈取栈顶元素if (s.top=s.base)printf(" 运算数栈为空 !n"); / 栈为空的时候返回 ERROR return ERROR;elsee=*(s.top-1); / 栈不为空的时候

17、，用e 作返回值，返回S 的栈顶元素，并返回 OKreturn OK;int Pushn(SqStackn &s,int e) /数栈入栈if (s.top-s.base >=s.stacksize)- 9 -printf(" 运算数栈满 !n"); / 栈满的时候，追加5 个存储空间s.base=(int*)realloc (s.base,(s.stacksize+5)*sizeof(int) ); if(!s.base) exit (OVERFLOW);s.top=s.base+s.stacksize; / 插入元素 e 为新的栈顶元素 s.stacksi

18、ze+=5;*(s.top)+=e; / 栈顶指针变化return OK;int Popn(SqStackn &s,int &e) /数栈出栈if (s.top=s.base)printf(" 运算符栈为空 !n"); / 栈为空栈的视时候，返回ERRORreturn ERROR;elsee=*-s.top;/栈不空的时候，则删除S 的栈顶元素，用e 返回其值，并返回 OKreturn OK;int StackTraversen(SqStackn &s) /数栈遍历int *t;t=s.base ;if (s.top=s.base)printf(&q

19、uot; 运算数栈为空 !n"); / 栈为空栈的时候返回 ERROR return ERROR;while(t!=s.top)printf(" %d",*t); / 栈不为空的时候依次输出t+;return ERROR;-10-/=/以下定义函数/=int Isoperator(char ch) /判断是否为运算符，分别将运算符和数字进入不同的栈switch (ch)case '+':case '-':case '*':case '/':case '(':case ')

20、9;:case '#':return 1;default:return 0;int Operate(int a, char op, int b) /运算操作int result;switch(op)case '+':result=a+b;break;case '-':result=a-b;break;case '*':result=a*b;break;case '/':result=a/b;break;return result;char Precede(char ch1, char ch2) /运算符优先级的比较

21、-11-char p;switch(ch1)case '+':case '-':if (ch2='+'|ch2='-'|ch2=')'|ch2='#')p = '>'/ch1 运算符的优先级小于ch2 运算符elsep = '<'break;case '*':case '/':if (ch2 = '(')p = '<'elsep = '>'break;case &#

22、39;(':if (ch2 = ')')p = '='else if (ch2 = '#')printf(" 表达式错误 !运算符不匹配 !n") ;exit(0);elsep = '<'break ;case ')':if (ch2 = '(')printf(" 表达式错误 !运算符不匹配 !n") ;exit(0);elsep = '>'break ;case '#':if (ch2 = ')&#

23、39;)printf(" 表达式错误 !运算符不匹配 !n") ;exit(0);-12-else if (ch2 = '#')p = '='elsep='<'break;return p;/=/以下是求值过程/=int EvaluateExpression()/参考书 p53 算法 3.4int a, b, temp, answer;char ch,op,e;char *str;intj = 0;SqStackn OPND;/OPND 为运算数字栈SqStack OPTR;/OPTR 为运算符栈InitStack(OP

24、TR);Push(OPTR,'#');/,所以此栈底是 '#'，因为运算符栈以 '#'作为结束标志InitStackn(OPND);/ printf("nn 按任意键开始求解 :nn");/ ch=getch();printf("n 请输入表达式并以 '#'结束 :n");str =(char*)malloc(50*sizeof(char);gets(str);ch=strj;/ch 是字符型的，而 e 是整型的整数j+;GetTop(OPTR,e);/e 为栈顶元素返回值while (ch

25、!='#' | e!='#')if (!Isoperator(ch)/遇到数字 ,转换成十进制并计算temp=ch-'0'/将字符转换为十进制数ch=strj;j+;while(!Isoperator(ch)-13-temp=temp*10 + ch-'0'/将逐个读入运算数的各位转化为十进制数ch=strj;j+;Pushn(OPND,temp);else if (Isoperator(ch)/ 判断是否是运算符 ,不是运算符则进栈switch (Precede(e,ch)case '<' : Push(O

26、PTR,ch);/ 栈顶元素优先权低ch = strj+;printf("nn运算符栈为： n");/输出栈，显示栈的变化StackTraverse(OPTR);printf("n 运算数栈为： n");StackTraversen(OPND);break;case '=' : Pop(OPTR,op);/ 脱括号并接收下一字符ch = strj+ ;printf("nn运算符栈为： n");StackTraverse(OPTR);printf("n 数栈为： n");StackTraversen(

27、OPND);break;case '>' : Pop(OPTR,op);/弹出最上面两个，并运算，把结果进栈Popn(OPND,b);Popn(OPND,a);Pushn(OPND,Operate(a,op,b);printf("nn运算符栈为： n");StackTraverse(OPTR);printf("n 数栈为： n");StackTraversen(OPND);elseprintf(" 您的输入有问题，请检查重新输入!");exit(0);-14-GetTop(OPTR,e);/ 取出运算符栈最上面元素是否是'#' /whileGetTopn(OPND,answer); / 已输出。数字栈最上面即是最终结果 return answer;/=/执行部分/=void ShowMenu()printf("nn");printf(" n"); printf(" n");printf(&q