学习Excel技术，关注微信公众号：
excelperfect
在前面的文章中，我们用VBA实现了栈数据结构，也实现了算术表达式的拆分，详见下列3篇文章：
1. 基础扩展 | 13. 使用VBA实现栈结构
2. 基础扩展 | 14. 栈结构应用基础示例
3. VBA编程练习01. 拆分算术表达式
下面，我们运用上述知识，使用VBA代码实现中缀表达式变为后缀表达式的转换。
我们平时使用的标准四则运算表达式称为“中缀表达式”，例如：
9 + (3 – 1) * 3 + 10 / 2
所有的运算符号都在两个数字的中间。转换成后缀表达式应该为：
9 3 1 – 3 * + 10 2 / +
转换规则为：从左至右遍历中缀表达式中的每个数字和符号，若是数字则直接输出；若是符号，则判断其与栈顶符号的优先级，是右括号或者优先级低于栈顶符号（乘除优先于加减），则栈顶元素依次出栈并输出，然后将当前符号入栈；直至最后全部输出为止。
为什么要用到后缀表达式呢？主要是为了方便计算机对算术表达式求值。这种表达方法是由一位波兰逻辑学家发现的，也称为逆波兰（RPN）表示法。
练习：根据上述基础知识和内容，编写实现中缀表达式转换成后缀表达式的VBA代码。
关键点：使用栈结构实现转换规则。详细的原理请参见程杰著的《大话数据结构》P108-110中的内容。
VBA代码：
'创建栈
Dim MyStack As New Stack
Sub ConvertExpress()
'声明表达式字符串
Dim strExpress As String
Dim SuffixExpress AsString
'声明放置表达式各元素的数组
Dim MidExpress() As String
Dim BackExpress() AsString
'声明其它变量
Dim i As Long, j As Long
Dim iCount As Long
Dim str
'测试表达式
strExpress ="9+(3-1)*3+10/2"
' strExpress ="9*2/3+2"
' strExpress ="9*3+(18-9)/3+2"
MidExpress =SplitExpress(strExpress)
'遍历表达式
For i = LBound(MidExpress) To UBound(MidExpress)
'如果是数字则直接放入输出数组
If IsNumeric(MidExpress(i)) Then
iCount = iCount +1
ReDim Preserve BackExpress(1 To iCount)
BackExpress(iCount) = MidExpress(i)
'如果是符号则根据括号配对或者四则运算规则
'将运算符号放入输出数组
Else
Select Case MidExpress(i)
Case"{", "[", "("
MyStack.Push MidExpress(i)
Case"}", "]", ")"
'遇到右括号,则栈顶元素出栈
'直到遇到配对的左括号
str =MyStack.StackTop
Do While((str "{") And (str "[") And (str "("))
iCount= iCount + 1
ReDim Preserve BackExpress(1 To iCount)
BackExpress(iCount) = MyStack.Pop
str =MyStack.StackTop
Loop
MyStack.Pop
'乘除优先级最大直接入栈
Case"*", "/"
str =MyStack.StackTop
MyStack.Push MidExpress(i)
'加减时遇到栈顶为乘除
'则全部出栈并将其放入输出数组
Case"+", "-"
str =MyStack.StackTop
If str = "*" Orstr = "/" Then
DoWhile Not MyStack.StackEmpty
iCount = iCount + 1
ReDim Preserve BackExpress(1 To iCount)
BackExpress(iCount) = MyStack.Pop
Loop
End If
MyStack.Push MidExpress(i)
End Select
End If
Next i
'将栈中剩余的元素全部出栈并放入输出数组
Do While NotMyStack.StackEmpty
iCount = iCount + 1
ReDim Preserve BackExpress(1 To iCount)
BackExpress(iCount) =MyStack.Pop
Loop
'联接各元素成输出的后缀表达式
str = ""
For i =LBound(BackExpress) To UBound(BackExpress)
str = str & BackExpress(i) & " "
Next i
Debug.Print str
End Sub
代码中，用到了《VBA编程练习01.拆分算术表达式》中的程序，我将其改写成了一个返回数组的函数：
Function SplitExpress(express As String) As String()
'存储表达式的每个字符
Dim var1() As String
'存储表达式中各元素(符号和数字)
Dim var2() As String
'循环变量
Dim i As Long
Dim j As Long
'计数,用来确定动态数组大小
Dim iCount As Long
'表达式长度
Dim lLen As Long
'临时变量,用来存储数字元素中单个数字数
Dim temp As Long
'将相邻的数字组合成一个数字元素
Dim str As String
lLen = Len(express)
'重定义数组大小为表达式长度
'比表达式的长度大1
'确保最后一个字符能添加到数组
ReDim var1(1 To lLen + 1)
'将表达式拆分单个字符
For i = 1 To lLen
var1(i) = Mid(express,i, 1)
Next i
temp = 0
'遍历表达式
For i = 1 To lLen + 1
'如果相邻字符是数字,则将其取出并连接成一个数字
If var1(i) Like"[0-9]" Then
temp = temp + 1
ElseIf temp > 0Then
For j = 1 To temp
str = str& var1(i - temp + j - 1)
Next j
iCount = iCount +1
ReDim Preserve var2(1 To iCount)
var2(iCount) = str
temp = 0
str = ""
End If
'如果是符号,则直接存放
Select Case var1(i)
Case"{", "[", "(", ")", "}","]", "+", "-", "*", "/"
iCount =iCount + 1
ReDim Preserve var2(1 To iCount)
var2(iCount) =var1(i)
End Select
Next i
'返回结果
SplitExpress = var2()
End Function
运行ConvertExpress过程的结果为：
![]()
下面是代码的图片版：
![]()
|
|
转播
