もっと軽量なものがほしいなと思って、逆ポーランド記法による演算をやってみた。
どのようなものができたかというと、基本的な四則演算と、括弧による優先度、変数を扱えるようなもの。
ポイントは３つ。
・括弧内演算は、再帰処理によって実現した。
・四則演算は、優先度を設けて「＋－」は最後、「＊／」は最初に演算するようにした。
・変数は、逆ポーランドで演算前に、デコード処理を行うようにした。
Public Sub New()
Console.WriteLine(Calc("1+2-3"))
Console.WriteLine(Calc("1+2*3"))
Console.WriteLine(Calc("(1+2)*3"))
Console.WriteLine(Calc("(1+2)/3"))
End Sub
Module ReversePolishNotation
Private param As New Dictionary(Of String, Integer) '変数
Private dat As String = "" '計算する文字データ
Private idx As Integer = 0 '解析インデックス
Private stk As New Queue(Of String) '後置記法バッファ
Public Function Calc(ByVal data As String) As Integer
dat = data
idx = 0
stk.Clear()
INtoPN() '中置記法→後置記法へ変換
Return RPN() '逆ポーランド記法による演算
End Function
Private Sub INtoPN()
'中置記法→後置記法へ変換
Dim L1 As New Queue(Of String) '後置記法確定バッファ
Dim R1 As New Stack(Of String) '符号格納バッファ
Dim wrd As String = "" '切り出した文字列
Dim hugo As String = "" '優先される符号格納（「*、/」）
While dat.Length > idx
Dim tmp As String = CStr(dat(idx)) 'データ読み出し
idx += 1
Select Case tmp
Case "("
INtoPN() '括弧内優先で演算する
Case ")"
Exit While
Case "+", "-"
'優先度の低い演算子は最後に計算
If wrd <> "" Then L1.Enqueue(wrd)
If hugo <> "" Then L1.Enqueue(hugo)
R1.Push(tmp)
hugo = ""
wrd = ""
Case "*", "/"
'優先度の高い演算子は最初に計算
If wrd <> "" Then L1.Enqueue(wrd)
If hugo <> "" Then L1.Enqueue(hugo)
hugo = tmp
wrd = ""
Case " ", "\t"
'無視するキーワード
Case Else
'演算する文字列
wrd += tmp
End Select
End While
If wrd <> "" Then L1.Enqueue(wrd)
If hugo <> "" Then L1.Enqueue(hugo)
While 0 < L1.Count : stk.Enqueue(L1.Dequeue()) : End While
While 0 < R1.Count : stk.Enqueue(R1.Pop()) : End While
End Sub
Private Function RPN() As Integer
'逆ポーランド記法による演算
Dim dat As New Stack(Of Integer)
While 0 < stk.Count
Dim tmp As String = stk.Dequeue()
Dim R As Integer = stk.Pop()
Dim L As Integer = stk.Pop()
Select Case data
Case "+" : stk.Push(L + R)
Case "-" : stk.Push(L - R)
Case "*" : stk.Push(L * R)
Case "/" : stk.Push(L \ R)
Case Else : dat.Push(Decoder(tmp))
End Select
End While
Return dat.Pop()
End Function
Private Function Decoder(ByVal data As String) As Integer
'変数→数字変換
Dim ret As Integer = 0
If Int32.TryParse(data, ret) Then Return ret
Return param(data)
End Function
End Module
無駄なバッファが多いので、後値記法へ変換しながら演算するようにしてみた。Module ReversePolishNotation
Private param As New Dictionary(Of String, Integer) '変数
Private dat As String = "" '計算する文字データ
Private idx As Integer = 0 '解析インデックス
Private stk As New Stack(Of Integer) '演算バッファ
Public Function Calc(ByVal data As String) As Integer
dat = data
idx = 0
stk.Clear()
RPN() '演算
Return stk.Pop() '結果を返す
End Function
Private Sub RPN()
'中置記法→後置記法へ変換しながら演算を行う
Dim R1 As New Stack(Of String) '符号格納バッファ
Dim wrd As String = "" '切り出した文字列
Dim hugo As String = "" '優先される符号格納（「*、/」）
While dat.Length > idx
Dim tmp As String = CStr(dat(idx)) 'データ読み出し
idx += 1
Select Case tmp
Case "(" : RPN() '括弧内優先で演算する
Case ")" : Exit While
Case "+", "-" '優先度の低い演算子は最後に計算
If wrd <> "" Then stk.Push(Decoder(wrd))
If hugo <> "" Then enzan(hugo)
R1.Push(tmp)
hugo = ""
wrd = ""
Case "*", "/" '優先度の高い演算子は最初に計算
If wrd <> "" Then stk.Push(Decoder(wrd))
If hugo <> "" Then enzan(hugo)
hugo = tmp
wrd = ""
Case " ", "\t" '無視するキーワード
Case Else '演算する文字列
wrd += tmp
End Select
End While
If wrd <> "" Then stk.Push(Decoder(wrd))
If hugo <> "" Then enzan(hugo)
While 0 < R1.Count : enzan(R1.Pop()) : End While
End Sub
Private Sub enzan(ByVal data As String)
Dim R As Integer = stk.Pop()
Dim L As Integer = stk.Pop()
Select Case data
Case "+" : stk.Push(L + R)
Case "-" : stk.Push(L - R)
Case "*" : stk.Push(L * R)
Case "/" : stk.Push(L \ R)
End Select
End Sub
Private Function Decoder(ByVal data As String) As Integer
Dim ret As Integer = 0
If Int32.TryParse(data, ret) Then Return ret
Return param(data)
End Function
End Module
どっちがいいかは不明。
