欢迎来到天天文库
浏览记录
ID:15684206
大小:271.21 KB
页数:11页
时间:2018-08-04
《数据结构之中缀表达式转后缀表达式》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
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=
9、=0){return0;}elseif(c=='('&&flag==1){return3;}else{fprintf(stderr,"Inputcharisinvalid!");return-1;}}/*****************************************************************判断一个字符是不是运算符*如果是合法的运算符+、-、*、/、(、)则返回0,否则返回1**************************************************************
10、**/intIsOperator(charc){if(c=='+'
11、
12、c=='-'
13、
14、c=='*'
15、
16、c=='/'
17、
18、c=='('
19、
20、c==')'){return0;}else{return1;}}/*****************************************************************完整的代码如下:****************************************************************/#include#include
21、#defineElementTypechartypedefstructNode*PtrToNode;typedefPtrToNodeStack;typedefstructNode{ElementTypeElement;PtrToNodeNext;};intIsEmpty(StackS);StackCreateStack();voidDisposeStack(StackS);voidMakeEmpty(StackS);voidPush(ElementTypeX,StackS);ElementTypeTop(StackS);voidPop(St
22、ackS);//判断栈是否为空intIsEmpty(StackS){returnS->Next==NULL;}//创建链栈StackCreateStack(){StackS=ma
此文档下载收益归作者所有