2013年2月8日金曜日

逆ポーランド記法による演算

.NETならReflectionなどを使って解決する方法もあるけど、
もっと軽量なものがほしいなと思って、逆ポーランド記法による演算をやってみた。
どのようなものができたかというと、基本的な四則演算と、括弧による優先度、変数を扱えるようなもの。

ポイントは3つ。
・括弧内演算は、再帰処理によって実現した。
・四則演算は、優先度を設けて「+-」は最後、「*/」は最初に演算するようにした。
・変数は、逆ポーランドで演算前に、デコード処理を行うようにした。


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

どっちがいいかは不明。

Androider