[محمد شريقي]

[COLOR="#000080"]بسم الله الرحمن الرحيم

كنا قد تكلمنا عن

[url="http://vb4arb.com/vb/showthread.php?1075-%E5%ED%C7%DF%E1-%C7%E1%C8%ED%C7%E4%C7%CA-Data-Structures-%C7%E1%D5%DD-Queue-%C7%E1%CC%D2%C1-%C7%E1%C7%E6%E1"]هياكل البيانات Data Structures الصف Queue : الجزء الاول
[/url]
هياكل البيانات Data Structures المكدس Stack: الجزء الثاني

التعريف بـ PostFix و PreFix و InFix ومجالات استخدامهم : الجزء الثالث

سنتكلم الان عن التحويل من صيغة infix الى صيغة postfix و prefix

سأبدأ من التحويل الى postfix
قلت سابقا ان الصيغة postfix تعني ان يأتي العامل بعد المعاملان التابعين له
مثال

كود :

a+b*c-d

تكتب هكذا

كود :

abc*+d-

لا تقلق كثيرا فبعد هذه الدرس ستصبح قادرا على التحيل بنفسك ان شاء الله

سأتكلم عن خوارزمية التحويل الان
بالبداية نحن بحاجة الى مكدس لاستخدامه و سلسلة نصية فارغة لنضع فيها الناتج
ما سنقوم به هو كالتالي
1 ناخد الصيغة infix ثم ناخذها رمز رمز ونتابع
2 نتأكد من الرمز اذا كان عامل او معامل وذلك من خلال استخدام تابع بسيط(سأقوم بشرحه لاحقا)
3 اذا كان الرمز المدخل معامل نضعه في سلسلة الناتج
4 اذا كان الرمز عامل فنحن امام ثلاث خيارات
a اذا كان الرمز قوس مفتوح ) نضعه في المكدس (push)
b اذا كان قوس مغلق ( نسحب الموجود بالمكدس ونضعه بسلسلة الناتج حتى الوصول الى القوس المفتوح ) (pop)
c اذا كان عامل فنحن اما خياران ايضا (يجب فحص اولوية العوامل وهنا سنقوم بانشاء تابع بسيط سأقوم بشرحه لاحقا)
الاول هو ان تكون اولوية هذا العامل اكبر من العامل الموجود في قمة المكدس فهنا نضع العامل في المكدس (push)
الثاني هو ان تكون اولوية هذا العامل اصغر من العامل الموجود في قمة المكدس فهنا نسحب العامل الموجود في قمة المكدس ونضعه في سلسلة الناتج (pop) ثم نقارن مع قمة المكدس مرة اخرى الى ان نصل الى عامل له اولوية اصغر وهنا نضع العامل الذي لدينا في قمة المكدس (push)

وبعد المرور على جميع العناصر نخرج كل شيء موجود بالمكدس ونضعه بسلسلة الناتج


ولكي تفهم اكثر ساضع الخوارزمية بلغة مفهومة اكثر و هي اللغة الانكليزية

كود :

given infix string
create empty postfix string
create operator stack S
for each symbol ch in the infix string do
if ch is an operand then
append it to the output postfix string
else if ch =  (  then
push ch onto stack S
else if S = ) then
pop and append operators to output string until the matching ( is encountered
else '(ch must be some other operator)
{ while operator stack not empty
and precedence(top(S)) ≥ precedence(ch)
and top(S)<> ‘(‘ do
pop operator
append it to the postfix string
end while
push S
}
end for


while operator stack is not empty do
pop operator
append it to the postfix string
endwhile

والان ساقوم بشرح التابعان المطلوبان
الاول هو فحص اذا كان البرمز هو عامل او معامل وهو بسيط طبعا

كود :

Private Function IsOpr(ByVal OPR As String) As Boolean
        Select Case OPR
            Case "+", "-", "*", "/", ")", "(", "^", "%"
                Return True
            Case Else
                Return False
        End Select
    End Function

هنا نفحص الرمز الممرر فاذا كان احد الرموز التالية + - * / ^ % ( ) يعيد true والا يعيد false

والثاني هو اعطاء الاولويات وهو بسيط ايضا

كود :

Private Function Prio(ByVal Sym As String) As Integer
        If Sym = "^" Or Sym = "%" Then
            Return 4
        ElseIf Sym = "*" Or Sym = "/" Then
            Return 2
        ElseIf Sym = "-" Or Sym = "+" Then
            Return 1
        Else
            Return 0
        End If
    End Function

هنا يقوم التابع بفحص الرمز المدخل فإذا كان ^ الاس او % الجذر (انا فرضت انها جذر)
يعطي الاولوية الاعلى وهي 4
واذا كان * الضرب او / القسمة يعطي الاولوية 2
واذا كان + الجمع او - الطرح يعطي الاولوية 1
وغير ذلك يعطي 0 تجنبا للاستخدام الخاطئ

والان سأتكب كود التحويل بالVB.NET

كود :

Private Function InfixToPostfix2(ByVal infix As String) As String
        Dim RESULT As String = "", S As New Stack(Of String)
        For i = 1 To infix.Length
            Dim Temp As String = Mid(infix, i, 1)
            If IsOpr(Temp) = False Then
                RESULT &= Temp & " "
            Else
                If Temp = ")" Then
                    Do Until S.Peek = "("
                        RESULT &= S.Pop & " "
                    Loop
                    S.Pop()
                ElseIf Temp = "(" Then
                    S.Push(Temp)
                Else
                    Do While S.Count > 0 AndAlso Prio(S.Peek) >= Prio(Temp) AndAlso S.Peek <> "("
                        RESULT &= S.Pop & " "
                    Loop
                    S.Push(Temp)
                End If
            End If
        Next

        Do While S.Count > 0
            RESULT &= S.Pop & " "
        Loop

        Return RESULT
    End Function

الى هنا نكون انتهينا من التحويل الى postfix

الان ساتكلم عن التحويل الى prefix

ان الصيغة prefix تعني ان يأتي العامل rقبل المعاملان التابعين له
مثال

كود :

a+b*c-d

تكتب هكذا

كود :

-+a*bcd

لا تقلق ايضا لاننا سنتعلم كيف يتم التحويل
كما فعلنا في التحويل الى postfix
سأتكلم عن خوارزمية التحويل الان
بالبداية نحن بحاجة الى مكدس لاستخدامه و سلسلة نصية فارغة لنضع فيها الناتج
ما سنقوم به هو كالتالي
1 ناخد عكس الصيغة infix ثم ناخذها رمز رمز ونتابع
2 نتأكد من الرمز اذا كان عامل او معامل وذلك من خلال استخدام تابع بسيط(قمنا بشرحه سابقاً)
3 اذا كان الرمز المدخل معامل نضعه في سلسلة الناتج
4 اذا كان الرمز عامل فنحن امام ثلاث خيارات
a اذا كان الرمز قوس مغلق ( نضعه في المكدس (push)
b اذا كان قوس مفتوح ) نسحب الموجود بالمكدس ونضعه بسلسلة الناتج حتى الوصول الى القوس مغلق ( (pop)
c اذا كان عامل فنحن اما خياران ايضا (يجب فحص اولوية العوامل كما ىشرحنا سابقا)
الاول هو ان تكون اولوية هذا العامل اكبر او تساوي العامل الموجود في قمة المكدس فهنا نضع العامل في المكدس (push)
الثاني هو ان تكون اولوية هذا العامل اصغر من العامل الموجود في قمة المكدس فهنا نسحب العامل الموجود في قمة المكدس ونضعه في سلسلة الناتج (pop) ثم نقارن مع قمة المكدس مرة اخرى الى ان نصل الى عامل له اولوية اصغر وهنا نضع العامل الذي لدينا في قمة المكدس (push)

وبعد المرور على جميع العناصر نخرج كل شيء موجود بالمكدس ونضعه بسلسلة الناتج

ثم نقوم بعكس سلسلة الناتج لنحصل على الناتج الحقيقي

المكتوب باللون الاحمر هو الفرق بين هذه الخوارزمية وخوارزمية التحويل الى postfix

وكالعادة هذه الخوارزمية بالانكليزي

كود :

reverse a given infix string
create empty reversed prefix string
create operator stack S
for each symbol ch in the reversed infix string do
if ch is an operand then
append it to the output prefix string
else if ch = ) then
push ch onto stack S
else if S = ( then
pop and append operators to output string until the matching ‘)‘ is encountered
else ' ch must be some other operator
{ while operator stack not empty
and precedence(top(S)) > precedence(ch)
and top(S)<> ) do
pop operator
append it to the reversed prefix string
end while
push S
}
end for

while operator stack is not empty do
pop operator
append it to the reversed prefix string
endwhile

reverse the reversed output prefix string

وهذا كود التحوي الى prefix بال VB.NET

كود :

Private Function InfixToPrefix(ByVal infix As String) As String
        Dim RESULT As String = "", S As New Stack(Of String)
        Dim TT As String = infix
        infix = ""
        For i = TT.Length To 1 Step -1
            infix &= Mid(TT, i, 1)
        Next
        ' reverse the infix expr

        For i = 1 To infix.Length
            Dim Temp As String = Mid(infix, i, 1)
            If IsOpr(Temp) = False Then
                RESULT &= Temp & " "
            Else
                If Temp = "(" Then
                    Do Until S.Peek = ")"
                        RESULT &= S.Pop & " "
                    Loop
                    S.Pop()
                ElseIf Temp = ")" Then
                    S.Push(Temp)
                Else
                    Do While S.Count > 0 AndAlso Prio(S.Peek) > Prio(Temp) AndAlso S.Peek <> ")"
                        RESULT &= S.Pop & " "
                    Loop
                    S.Push(Temp)
                End If
            End If
        Next

        Do While S.Count > 0
            RESULT &= S.Pop & " "
        Loop

        TT = RESULT
        RESULT = ""
        For i = TT.Length To 1 Step -1
            RESULT &= Mid(TT, i, 1)
        Next
        Return RESULT
    End Function

وهذا كود برنامج التحويل كاملا لاتنسى اضافة 2 كومند و اذاة تكست بوكس

كود :

Public Class Form1

    Private Function InfixToPostfix(ByVal infix As String) As String
        Dim RESULT As String = "", S As New Stack(Of String)
        For i = 1 To infix.Length
            Dim Temp As String = Mid(infix, i, 1)
            If IsOpr(Temp) = False Then
                RESULT &= Temp & " "
            Else
                If Temp = ")" Then
                    Do Until S.Peek = "("
                        RESULT &= S.Pop & " "
                    Loop
                    S.Pop()
                ElseIf Temp = "(" Then
                    S.Push(Temp)
                Else
                    Do While S.Count > 0 AndAlso Prio(S.Peek) >= Prio(Temp) AndAlso S.Peek <> "("
                        RESULT &= S.Pop & " "
                    Loop
                    S.Push(Temp)
                End If
            End If
        Next

        Do While S.Count > 0
            RESULT &= S.Pop & " "
        Loop

        Return RESULT
    End Function

    Private Function InfixToPrefix(ByVal infix As String) As String
        Dim RESULT As String = "", S As New Stack(Of String)
        Dim TT As String = infix
        infix = ""
        For i = TT.Length To 1 Step -1
            infix &= Mid(TT, i, 1)
        Next
        ' reverse the infix expr

        For i = 1 To infix.Length
            Dim Temp As String = Mid(infix, i, 1)
            If IsOpr(Temp) = False Then
                RESULT &= Temp & " "
            Else
                If Temp = "(" Then
                    Do Until S.Peek = ")"
                        RESULT &= S.Pop & " "
                    Loop
                    S.Pop()
                ElseIf Temp = ")" Then
                    S.Push(Temp)
                Else
                    Do While S.Count > 0 AndAlso Prio(S.Peek) > Prio(Temp) AndAlso S.Peek <> ")"
                        RESULT &= S.Pop & " "
                    Loop
                    S.Push(Temp)
                End If
            End If
        Next

        Do While S.Count > 0
            RESULT &= S.Pop & " "
        Loop

        TT = RESULT
        RESULT = ""
        For i = TT.Length To 1 Step -1
            RESULT &= Mid(TT, i, 1)
        Next
        Return RESULT
    End Function

    Private Function IsOpr(ByVal OPR As String) As Boolean
        Select Case OPR
            Case "+", "-", "*", "/", ")", "(", "^", "%"
                Return True
            Case Else
                Return False
        End Select
    End Function

    Private Function Prio(ByVal Sym As String) As Integer
        If Sym = "^" Or Sym = "%" Then
            Return 4
        ElseIf Sym = "*" Or Sym = "/" Then
            Return 2
        ElseIf Sym = "-" Or Sym = "+" Then
            Return 1
        Else
            Return 0
        End If
    End Function

    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
        MsgBox(InfixToPostfix(TextBox1.Text))
    End Sub

    Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click
        MsgBox(InfixToPrefix(TextBox1.Text))
    End Sub

End Class

والبرنامج بالمرفقات[/COLOR]