数据结构之中缀表达式转后缀表达式

数据结构之中缀表达式转后缀表达式

ID:1212902

大小:271.21 KB

页数:11页

时间:2017-11-08

数据结构之中缀表达式转后缀表达式_第1页
数据结构之中缀表达式转后缀表达式_第2页
数据结构之中缀表达式转后缀表达式_第3页
数据结构之中缀表达式转后缀表达式_第4页
数据结构之中缀表达式转后缀表达式_第5页
资源描述:

《数据结构之中缀表达式转后缀表达式》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库

1、我们在数学中常见的计算式,例如2+(3*4)叫做中缀表达式。表达式中涉及到了多个运算符,而运算符之间是有优先级的。计算机在计算并且处理这种表达式时,需要将中缀表达式转换成后缀表达式,然后再进行计算。中缀表达式转后缀表达式遵循以下原则:1.遇到操作数,直接输出;2.栈为空时,遇到运算符,入栈;3.遇到左括号,将其入栈;4.遇到右括号,执行出栈操作,并将出栈的元素输出,直到弹出栈的是左括号,左括号不输出;5.遇到其他运算符'+''-''*''/'时,弹出所有优先级大于或等于该运算符的栈顶元素,然后将该运算符入栈;6.最终将栈中的元素依次出栈,输出。经过上面的步骤,得

2、到的输出既是转换得到的后缀表达式。举例:a+b*c+(d*e+f)*g--------->abc*+de*f+g*+遇到a,直接输出:遇到+,此时栈为空,入栈:遇到b,直接输出:遇到*,优先级大于栈顶符号优先级,入栈:遇到c,输出:遇到+,目前站内的*与+优先级都大于或等于它,因此将栈内的*,+依次弹出并且输出,并且将遇到的这个+入栈:遇到(,将其入栈:遇到d,直接输出:遇到*,由于*的优先级高于处在栈中的(,因此*入栈:遇到e,直接输出:遇到+,栈顶的*优先级高于+,但是栈内的(低于+,将*出栈输出,+入栈:遇到f,直接输出:遇到),弹出栈顶元素并且输出,直到

3、弹出(才结束,在这里也就是弹出+输出,弹出(不输出:遇到*,优先级高于栈顶+,将*入栈:遇到g,直接输出:此时已经没有新的字符了,依次出栈并输出操作直到栈为空:明白了这个过程,现在就需要用代码实现了。对于各种运算符的优先级,可以使用整数来表示运算符的级别。可以定义一个函数来返回各种符号的优先级数字:/******************************************************************根据字符该字符是否在栈中,返回该字符的优先级。*这里只处理+、-、*、/、(、)这些符号。*需要注意的是:如果(在栈中,它的优先级是最

4、低的,不在栈中则是最高的*@paramc:需要判断的字符*@paramflag:字符是否在栈中,0表示在栈中,1表示不在栈中*****************************************************************/intGetPrecedence(charc,intflag){if(c=='+'

5、

6、c=='-'){return1;}elseif(c=='*'

7、

8、c=='/'){return2;}elseif(c=='('&&flag==0){return0;}elseif(c=='('&&flag==1){return3

9、;}else{fprintf(stderr,"Inputcharisinvalid!");return-1;}}/*****************************************************************判断一个字符是不是运算符*如果是合法的运算符+、-、*、/、(、)则返回0,否则返回1****************************************************************/intIsOperator(charc){if(c=='+'

10、

11、c=='-'

12、

13、c=='*'

14、

15、c=='

16、/'

17、

18、c=='('

19、

20、c==')'){return0;}else{return1;}}/*****************************************************************完整的代码如下:****************************************************************/#include#include#defineElementTypechartypedefstructNode*PtrToNode;typedefPtrToNode

21、Stack;typedefstructNode{ElementTypeElement;PtrToNodeNext;};intIsEmpty(StackS);StackCreateStack();voidDisposeStack(StackS);voidMakeEmpty(StackS);voidPush(ElementTypeX,StackS);ElementTypeTop(StackS);voidPop(StackS);//判断栈是否为空intIsEmpty(StackS){returnS->Next==NULL;}//创建链栈StackCreateStack

22、(){StackS=ma

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。