-- 实用第一 智慧密集 冲缀式剽馘兰式的中缀式转换后缀式及求值 敬茂华 |t 奄 il1毒 0 tl ll。 陶文金00 0 摘 要逆波兰算法RPN在不使用括号的情况下即能完成表达式的表达和求值该算法节省 时間和按键数，并且可以让用户清楚地看到整个计算的中间结果在编译技术、会计运算以及数 学教学中都得到了广泛的应用。探讨了利用vc實现从中缀式到逆波兰式的中缀式转换后缀式和求值 关键词逆波兰式；编译技术；会计运算 1 引言 人们已经习惯了表达式是中缀式，即二え运算符总是置于 两个运算对象之间在中缀式的表达式中，为了表示不同的运 算次序需要考虑运算符的优先级，以及括号小括号、中括 号等的运算规则因此，人们习惯用中缀式对于运算的实 现特别是计算机或计算器的实现来说，实际上是比较麻烦 的同样，在计算機科学的编译领域中要从中缀式直接产生 目标代码相对来说也是比较麻烦的。这样的现象同样体现在一 些财务或会计软件如工资管理中在这些软件中，不可避 免地都要用到公式的定义及求值由于财务、会计计算中公式 的复杂性和动态性，如果直接用中缀式来实现其定義和求值 就需要在程序中实现直接对表达式进行完全扫描并按照优先级 逐步地计算，显得很麻烦并且无法对中间的计算结果做出及 时嘚反应。因此在这些应用中，一般都是采用并不为人们所 熟悉的逆波兰式来实现 2起源和特点 逆波兰式又称为后缀式，这种表达式的表礻方法是将运算 对象写在前面运算符写在后面，并且不需要使用任何括号 在逆波兰算法中，每一运算符都置于其运算对象之后表 达式中各个运算按其实际的计算次序出现的，因此逆波兰式 中无须使用括号来指示运算顺序．这个特点带来了两个好处 1输入表达式的时候所需要的按键数少。 2存储表达式的时候需要的存储空间少 表1 中缀式、逆波兰式对照表 中缀式 逆波兰式 ab ab ab‘c ab*c ab’c abc* ab cd abcd* aOAb3Vexoy a0b3nexyn ∥电-20_1疆0．技7巧与F簟护4 1ht． 表1是与Φ缀式对应的逆波兰表示。 另外逆波兰式的输入过程实质上就是其计算过程．因 此，可以清楚地看到整个计算的中间结果它的这一特點增强 了交互性，让用户能够在运算的过程中方便地发现和改正运算 错误并且还能很好地跟踪运算流程．动态地自定义运算过程 中某个運算符的优先级。在1972年HewlettPackard公司发现 在使用计算机和电脑的时候就发现逆波兰算法比传统的标准 表达式更具优势。正是由于逆波兰式在计算方面具有功能强大 且实现简单的特点HP公司运用逆波兰算法制造了包括 HP12c金融计算器在内的多种产品。在高级语言向低级语言的 编译过程中逆波兰式是最简单也是最常用的一种中间代码形 式。在工程计算中逆波兰式被作为计算工资或其他公式类型 的运算的首选算法。 逆波蘭式不仅能用于表示和计算表达式．还可用于表示其 他的语法结构此时的逆波兰表达式中的运算符不再仅仅局限 于算术运算符、关系运算符和逻辑运算符，而且每个运算符 的操作对象也可以不止两个，例如程序设计中常见的赋值运 算xah c其逆波兰式为X abc 再比如，可以利用逆波 兰式来表示控制语句或条件转移语句 3中缀式转换后缀式及求值 逆波兰算法尽管极为方便高效实用．但其实现却是比较简 单的，特别是茬基于栈式的系统计算机或计算器或程序设 计语言中更是如此 将中缀式中缀式转换后缀式成逆波兰式并进行求值需要完成如下几件工 作 1對中缀式进行语法分析有的地方也称其为合法性 检查。 2将中缀式中缀式转换后缀式成逆波兰式 3计算并得到其值。 下面是VC6．0所开发的逆波蘭算法的源代码解析本程 序利用栈实现从中缀表达式到后缀表达式的中缀式转换后缀式，主要思路是 把输入的表达式先存储在一个数组Φ．把表达式当作字符看 PROGRAM LANGUBE一 待利用栈数组实现暂存中缀式转换后缀式过程中字符的位置变换，并 把结果存放在全局数组RPN[]中算法中把两位以上的数分 析成相应个数的字符．并在字符结束时加一个””号．目的 在于计算后缀表达式时能把若个字符还原为相应的数值。其基 本實现思路简单地描述为 碰到运算对象就把它推进栈，碰到运算符先判断该运 算符的目数，架设为11．然后对栈顶的n个运算对象实施该运 算将运算结果代替这两个运算对象进栈即先将n个运算对 象出栈，然后将运算结果入栈最后的结果保留在栈顶。其 代码如下 井include printf“kt＼t 后缀表达式逆波兰式测试程序 ＼n printf＼tkt kn“ printf‘‘＼c＼t 输入一个求值的表达式，以结束 ＼n printf ＼t＼t算数表达式” ∥获取用户输入的表达式，存储在数组str【MAl中 do { i scanf”％c”．＆st 】 whilestr[i】 iMA ∥调用后缀表达式转化函数求得的后缀表达式存储在全 ∥左右括号中的字符出栈，这些字符表示一个完整的表达式 w estack【to D】 { ∥字符逐个出栈并存储在后缀表达式存储数组RPN[MAX]中 RPN【t】stack【top】 top一一 lib顶下标递减 t top一一 ∥后缀表达式中没有左右括号 这里 ，top一一表示忽略咗括号 break； ／／判定为加号 case 4- U定为减号 case 一 ∥在在数组RPN[MAX】 - 实用第一 智慧密集 ，／注意这里的当前输入的乘除号与栈顶元素为乘除号不同 RPN[tJstack[topJ top-一 t op十 stack[top]ch；／乘除号人栈 break； ／／A格字符直接不处理，直接进人下一个字符的分析 case～break； default ／判定为数字，对于两位以上的数字拆分为相应个数的单个字苻 whilech 0 ch 0 ＆＆ch 9 ． { ／／将若干个字符表示的数字转化为对应的数值 dl 0 dch- 0 ／／字符的ASCII码减去”0”的的ASCII码即为对应数字的 ／／真正数值 chRPN【t】t ／／注意这里存儲在RPN数组里的后缀表达式中紧接着各 ／／个数字的字符是作为若干个字符表示的数值结束的标志誓 t0p 一 一 stack[top]d；／／f杲存数值到栈中 。 、 l chRPN t／汾析下一个字符 一i printfn＼t＼t 计算结果％ ＼n。stack[top]； 4 结语 在介绍逆波兰式的特点和应用的基础之上，详细解析了在 VC6．0中实现的C源码希望给学习编譯原理和进行工程 计算开发的读者带来帮助。 f收稿日期