C语言的基于栈实现的表达式求值

Livealone

发布日期: 2018-11-04 22:44:42 浏览量: 292
评分:
star star star star star star star star_border star_border star_border
*转载请注明来自write-bug.com

一、目的

  • 理解中缀表达式求值的过程

  • 理解中缀转后缀表达式求值的过程

  • 掌握堆栈的应用

二、问题描述

  • 缀表达式,其中包含括号,加减乘除,乘方等运算,利用中缀表达式,对表达式分析并求值

  • 入的中缀表达式转换为后缀形式,显示后缀形式,并通过后缀形式求值

三、数据结构

  1. //运算符结构体
  2. typedef struct
  3. {
  4. char OPname; //存储运算符
  5. int inOP; //存储栈内级别
  6. int outOP; //存储栈外级别
  7. }OP;
  8. //定义运算数栈
  9. typedef struct
  10. {
  11. datatype data[MAXSIZE];
  12. int top;
  13. }SeqStack;
  14. //定义运算符栈
  15. typedef struct
  16. {
  17. char data[MAXSIZE];
  18. int top;
  19. }charStack;
  20. //----------------定义运算符数组-----------------//
  21. OP OPPree[OPNUM] =
  22. {
  23. {'+',3,2},
  24. {'-',3,2},
  25. {'*',5,4},
  26. {'/',5,4},
  27. {'^',7,6},
  28. {'(',1,8},
  29. {')',0,1},
  30. {'#',-1,-1}
  31. };

四、算法设计的思想描述

建立两个栈,一个为char类型栈OPTR,另一个为int类型栈OPND,分别来存储运算符和运算数。

  1. // 函数用来判断一个字符是否为运算数
  2. int In(char x);
  3. // 函数用来判断运算符栈内和栈外级别
  4. char Precede(char x,char c);
  5. // 函数用来计算两个数
  6. int Operate(int a,char x,int b);
  7. // 函数用来计算中缀表达式
  8. int EvaluateExpression();
  9. // 函数是把中缀表达式转换后缀表达式
  10. void change(char a[],char s[]);
  11. // 函数用来计算后缀表达式
  12. int HZcalc(char s[]);

中缀表达式计算算法的基本思路如下:

  • 对象栈OPND为空,表达式起始符“#”为运算符栈OPTR的栈底元素

  • 次读入表达式中的每个字符。若是操作数,进OPND栈;若是运算符,与OPTR栈的栈顶运算符比较优先权后做相应操作:

    • 当栈内级别小于栈外级别时入栈
    • 当栈内级别大于栈外级别时出栈并做运算
    • 当栈内级别等于栈外级别时只出栈。直至整个表达式求值完毕

中缀表达式转后缀表达式的思路如下:

  • 左至右逐字符读入中缀表达式

  • 该字符是’(‘, 直接压入栈中

  • 如果该字符是’)’, 依次弹出栈中操作符并写入后缀表达式中,直至弹出’)’为止

  • 如果该字符是操作符,弹出栈上部所有优先级大于或等于该操作符的操作符并写入后缀表达式中, 然后往栈中压入该操作符

  • 如果该字符是数字, 直接写入后缀表达式中

后缀表达式计算算法的基本思路如下:

  • 运算对象时,就把它插入到数栈OPND中

  • 当遇到运算符时,就执行两次出栈的操作,对出栈的数进行该运算符指定的运算,并把计算的结果压入到数栈OPND

  • 重复上述过程,直至扫描到表达式的终止符“\0”,在数栈的栈顶得到表达式的值

五、测试数据与结果分析

录入:3*2^(4+2*2-1*3)-5#

根据(四)算法分析中的中缀表达式计算结果得91,然后用change函数把中缀表达式转换为后缀表达式,经过函数Hzcalc得结果91,与中缀表达式的计算结果一致。

六、提高

通过这次实训,使我对C语言的语法、指针、数组跟栈的结构有了更深刻的认识。可以用栈来解决一些问题。特别是其中的大部分算法都是自主完成的,这使我有了很大的提高。

由于只能计算单个数字的表达式,这是我这次实训里未能完成的功能,希望自己在以后的时间里能继续改进算法,最终使算法完美。

七、算法评价

由于没有充分利用运算符数组的下标,尤其是Precede函数(比较栈内栈外级别)中的两个for循环,导致了程序的时间复杂度增高。对于计算函数,目前还只能运算单个数字的表达式。其他算法都在老师的帮助下完成!

上传的附件 cloud_download 基于栈实现的表达式求值.7z ( 37.11kb, 18次下载 )
error_outline 下载需要3点积分

发送私信

只有过着不安稳得日子,日子才能不纠结

6
文章数
6
评论数
最近文章
eject