论中缀表达式与后缀表达式的转换
开篇：润墨网以专业的文秘视角，为您筛选了一篇论中缀表达式与后缀表达式的转换范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要：为了处理方便，编译程序常把中缀表达式首先转换成等价的后缀表达式。介绍如何使用顺序栈这样一种数据结构实现中缀表达式向后缀表达式的转换。
关键词：堆栈；中缀表达式；后缀表达式
中图分类号：G40文献标识码：A文章编号：1672-3198（2008）06-0258-02
1 中缀表达式求值
首先我们来看一下什么叫作中缀表达式？所谓中缀表达式是指：每个二目运算符在两个运算量的中间。例如：a+b。
这里假设所讨论的算术运算符包括：+ 、－、*、/和括号（）。根据算术四则运算的规则：先乘除后加减、先括号内再括号外、同级别时先左后右,可以得出运算符的优先级为：（）*、/ +、－。如：a+b×c－(d+e)。我们根据优先级，计算出d+e的值x，再计算出b×c的值y，然后从左到右计算a+x－y。
它的的求值过程为：自左向右扫描表达式，当扫描到a+b时不能马上计算，因为后面可能还有更高的运算。我们可以用两个栈来处理这样的问题：对象栈s1和算符栈s2。当自左至右扫描表达式的每一个字符时，若当前字符是运算对象，入对象栈，是运算符时，若这个运算符比栈顶运算符高则入栈，继续向后处理，若这个运算符比栈顶运算符低则从对象栈出栈两个运算量，从算符栈出栈一个运算符进行运算，并将其运算结果入对象栈，继续处理当前字符，直到遇到结束符。
2 后缀表达式求值
所谓后缀表达式，是指运算符在运算对象之后。在后缀表达式中，不再引入括号，所有的计算按运算符出现的顺序，严格从左向右进行，而不用再考虑运算规则和级别。例如：abcd/-e*+。从左向右，首先计算/，即c/d的值x，然后计算b-x的值y，再计算y*e的值z，最后计算a+z。
计算一个后缀表达式，算法上比计算一个中缀表达式简单的多。这是因为表达式中即无括号又无优先级的约束。具体做法：只使用一个对象栈，当从左向右扫描表达式时，每遇到一个操作数就送入栈中保存，每遇到一个运算符就从栈中取出两个操作数进行当前的计算，然后把结果再入栈，直到整个表达式结束，这时送入栈顶的值就是结果。
3 中缀表达式转换成后缀表达式
为了处理方便，编译程序常把中缀表达式首先转换成等价的后缀表达式。
例如：一个中缀表达式：a+（b-c/d）*e
其相应的后缀表达式为：abcd/-e*+
我们可以用栈这样一种数据结构实现中缀表达式向后缀表达式的转换，具体步骤如下：
（1）设置一个堆栈，将栈顶预设置为‘＃’；
（2）顺序读入中缀表达式。当读到的单词为操作数时将其输出，并接着读入下一个单词；当读入的单词为运算符时就赋给x2，比较x2与栈顶运算符x1的优先级：
①若x2的优先级高于x1，将x2进栈，继续读入下一个单词；
②若x2的优先级低于x1，x1退栈并作为后缀表达式的一个单词输出，然后比较x2与新的栈顶运算符x1；
③若x2的优先级等于x1，且x1为'（'，x2为'）'，则x1出栈，然后继续读下一个单词；
④若x2的优先级等于x1的，且x1为'＃'，x2也为'＃'，则算法结束。
假设中缀表达式存在字符串expression中，且堆栈采用顺序栈，进出栈算法分别为PushQstuck（）和PopQstuck（），则中缀表达式变后缀表达式的算法为：
int postfix(qstype *s,char *expression) /*中缀表达式变后缀表达式*/
{
char x1,x2,x;
int j=0;
s->stack［0］='#';
s->top=0;
x2=expression［j］;
if((x1=gettopqstack(s))==nil) /* gettopqstack（）函数取栈顶元素*/
exit(0);
while(1)
{
if(x2!='+'&&x2!='-'&&x2!='*'&&x2!='/'&&x2!='('&&x2!=')'&&x2!='#')
{
cout
x2=expression［++j］;
}
else if(proceed(x1,x2)=='
{
if(!pushqstack(s,x2))
exit(0);
if((x1=gettopqstack(s))==nil)
exit(0);
x2=expression［++j］;
}
else if(proceed(x1,x2)=='>')
{
if((x=popqstack(s))==nil)
exit(0);
cout
if((x1=gettopqstack(s))==nil)
exit(0);
}
else if(proceed(x1,x2)=='='&&x1=='('&&x2==')')
{
if(popqstack(s)==nil)
exit(0);
if((x1=gettopqstack(s))==nil)
exit(0);
x2=expression［++j］;
}
else if(proceed(x1,x2)=='='&&x1=='#'&&x2=='#')return 1;
else if(proceed(x1,x2)==' ') break;
}
cout
return 0;
}
若表达式expression为a+（b-c/d）*e则我们通过下表可以看出转换的过程：
4 总结
为了处理方便，编译程序常把中缀表达式首先转换成等价的后缀表达式。栈是限制仅在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。栈的修改是按后进先出的原则进行的。利用栈的这一特点，我们利用顺序栈这样一种数据结构来实现中缀表达式转换成后缀表达式是完全可行的。
参考文献
［1］ 严蔚敏.数据结构［M］.北京：清华大学出版社.
［2］蒋文蓉.数据结构［M］.北京：高等教育出版社.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”