逆波兰表达式在VB中的算法设计与实现

杨 忠

YANG Zhong

（淄博职业学院，淄博 255013）

0 引言

在高级语言中出现的算术表达式，如a+(b-c)d，其运算符一般出现在操作数之间，此为中缀表达式，而编译系统不考虑表达式的优先级别，只是对表达式从左到右进行扫描，当遇到运算符时，就把其前面的两个操作数取出进行操作。为达到上述目的，就要将中缀表达式改成abc-d+样式，操作符均在操作数的后面，此为逆波兰表达式。

在逆波兰表达式中，不再出现括号，运算符放在两个运算对象的后面，运算严格按照从左到右的顺序进行，因而计算一个后缀表达式的值，其算法要比计算一个中缀表达式简单得多。以下以VB为开发平台，用顺序栈的工作原理完成逆波兰表达式的算法设计与实现。

1 确定运算符优先级

为了正确实现中缀向逆波兰表达式转换，必须明确操作符的优先级，如表1所示。

表1 算术操作符优先级设置

如果公式中还有其他的数学函数参与运算，可以相应定义优先级，实现转换，但必须定义某种规则用一个字母代替函数且严格按照书写规范书写。比如表达式sin(a)＋b，在表达式中含有数学运算函数sin()，我们可以用S表示该函数，然后如表2 所示设置操作符和函数的优先级即可。

表2 数学函数和算术操作符优先级设置

以上表中的#作为操作符栈栈底元素，用于第一个入栈操作符。isp表示操作符或函数在栈内优先级，icp表示操作符和函数在栈外优先级。每个操作符均有栈内和栈外两种优先级，用于决定压栈还是弹栈。

2 算法设计

1）在VB中利用数组实现栈的原理应用。定义两个数组chaarr和operator，定义一个操作符结构体数组op。

chaarr用于存储表达式中所有的操作数变量和操作符，对于公式中含有常数情况本文未作考虑。

操作符栈operator用于存储操作符，根据优先级的大小，实现栈的压栈和弹栈操作。

op用于存储操作符号本身，并赋予操作符在栈内和栈外优先级，用于弹栈和压栈判断。

2）利用函数mid从表达式中分离每个元素，当判断出该元素是操作数变量时直接把该变量存入chaarr中，当分解出的是操作符时，首先定义该操作符的栈内栈外优先级，存入操作符结构体数组op，然后判断该操作符的栈外优先级和operator内栈顶元素的栈内优先级的高低，如果是大于关系则把该操作符压栈operator，如果是小于关系，则把operator栈顶元素弹栈并存入chaarr中，原分离出的操作符继续与operatro内栈顶元素比较优先级，可能要重复进行弹栈、存入chaarr、比较优先级过程，直至该操作符压栈为止。如果括号弹栈，不把它存入chaarr中，因为后缀形式已经准确的表明了公式的先后运算次序关系。

3）利用一个循环，重复执行第2步，直至公式分解完毕，此时chaarr中存储的所有字符实现连接后就是我们需要的后缀表达式。

3 程序实现

根据前面确定的运算符优先级和程序设计思想，可以如下代码实现逆波兰表达式转换为后缀表达式。为了直观的看到转换结果，简单的设计如图1所示界面。

图1 公式解释器

只要在输入公式文本框中输入公式，点击转化按钮就可以转化为逆波兰表达式。

程序实现核心代码如下，只要在转化按钮单击事件中调用该代码块即可，其中涉及到的先期部分条件不再一一列出，代码块中有部分说明。核心代码中对于不同操作符的判断部分已经删除，其编写原理与开始的“*”操作符类似，只要能合理设置操作符优先级即可保证程序的正确运行，不再赘述。

ReDim chararr(Len(strexp))

'strexp表示通过界面输入的公式，chararr()是定义的全局数组。

4 结束语

为了处理方便，编译程序常把中缀表达式首先转换成等价的逆波兰表达式。在VB中，可以利用顺序栈的工作原理使用数组实现表达式的中缀形式向逆波兰表达式转化，从而完成数值计算。

[1] 严蔚敏,吴伟民.数据结构[M].北京：清华大学出版社,2004.

[2] 林永.Visual Basic程序Widows API编程手册[M].北京：人民邮电出版社,2002.