VBA编程练习02. 中缀表达式转换成后缀表达式

学习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过程的结果为：

下面是代码的图片版：