[ناجي إبراهيم]

السلام عليكم...

شكراً لأخي VB_Coder و بقية الإخوة على الإطراء.

سنبين في هذه المشاركة خوارزمية التحويل من التعبير ذي العوامل البينية (Infix) إلى التعبير ذي العوامل البعدية (Postfix). و لكن قبل ذلك سنشرح موضوعاً جانبياً لأنه مستعمل في الخوارزمية، و هو موضوع المكدس (Stack).

عندما نعالج بعض التعبيرات على مراحل فإننا غالباً ما نحتاج إلى تخزين بعض القيم بشكل مؤقت لنرجع إليها وقت الحاجة، و غالباً ما نريد تخزين تلك القيم بشكل منظم حسب الترتيب و ليس بشكل عشوائي.
يوجد لمثل هذا الأمر العديد من الأشكال التي تسمى تراكيب أو هياكل البيانات (Data Structures)، و لعل من درسوا البرمجة بشكل منهجي أو أكاديمي يعرفون ذلك. و لأن تلك التراكيب تكون عادة في شكل عام أو مجرد فإنها تسمى أنواع البيانات المجردة (Abstract Data Types = ADT). و من هذه الأنواع أو التراكيب:
1. المكدس Stack.
2. الطابور Queue.
3. القوائم المرتبطة Linked Lists.
... و العديد العديد ...
و هذه التراكيب تستعمل في مجالات برمجية كثيرة جداً مثل تحليل التعابير - كما في موضوعنا هذا - و في عمليات الفرز أو الترتيب و في معالجات النصوص و في تصميم الألعاب و الذكاء الصناعي و في تصميم لغات البرمجة و أنظمة التشغيل... إلخ.

* المكدس Stack: هو هيكل لتخزين البيانات بطريقة "الداخل أخيراً يخرج أولاً" (Last in First out = LIFO) أي أن آخر قيمة تم إدخالها أو تخزينها هي أول قيمة يمكن الوصول إليها (استخراجها) ثم القيمة التي دخلت قبلها ثم التي قبلها و هكذا. مثلاً إذا أدخلنا القيم التالية على الترتيب: 3 ثم 5 ثم 7 ثم 8 فإنه يتم استخراجها بالترتيب العكسي: 8 ثم 7 ثم 5 ثم 3.

* وظائف التعامل مع الـ Stack: توجد ثلاث وظائف أساسية:
1. الوظيفة Push لتخزين قيمة في قمة الـ Stack.
2. الوظيفة Pop لقراءة القيمة الموجودة في قمة الـ Stack و إزالة القيمة من الـ Stack.
3. الوظيفة Peek لقراءة القيمة الموجودة في قمة الـ Stack دون إزالتها.

بالإضافة إلى وظائف أخرى مثل معرفة ما إذا كانت الـ Stack فارغة أم لا، و معرفة عدد القيم في الـ Stack و كذلك وظيفة لتفريغ الـ Stack من القيم.

* في البرنامج المرفق في المشاركة الأولى هناك Class Module باسم TStack لاستعمالها في إنشاء كائن Stack، و في يلي الكود و بعض الشرح حوله:

كود :

Option Explicit

Private FValues As Collection

Private Sub Class_Initialize()
    Set FValues = New Collection
End Sub

Private Sub Class_Terminate()
    Set FValues = Nothing
End Sub

Public Sub Push(AValue As Variant)
    FValues.Add AValue
End Sub

Public Function Pop() As Variant
    If FValues.Count = 0 Then
        Err.Raise vbObjectError + 100, "TStack.Pop", "Stack is empty"
    Else
        Pop = FValues(FValues.Count)
        FValues.Remove FValues.Count
    End If
End Function

Public Function Peek() As Variant
    If FValues.Count = 0 Then
        Err.Raise vbObjectError + 100, "TStack.Peek", "Stack is empty"
    Else
        Peek = FValues(FValues.Count)
    End If
End Function

Public Function Is_Empty() As Boolean
    Is_Empty = (FValues.Count = 0)
End Function

Public Sub Make_Empty()
    Do While FValues.Count <> 0
        FValues.Remove FValues.Count
    Loop
End Sub

Public Function Count() As Long
    Count = FValues.Count
End Function

كما نرى، في بداية الكود قمنا بتعريف متغير (FValues) من النوع Collection (و هو من أنواع VB6) لتخزين قيم الـ Stack.

* الوظيفة Push:

كود :

Public Sub Push(AValue As Variant)
    FValues.Add AValue
End Sub

كما قلنا هي لتخزين قيمة في الـ Stack و لذلك تقبل بارامتراً واحداً (AValue) الذي يمثل القيمة التي نريد تخزينها. نلاحظ أننا نستعمل هنا الوظيفة Add لكائن الـ Collection، و الظيفة Add تضيف القيمة تلقائياً في نهاية الـ Collection و بالتالي فإن نهاية الـ Collection (أخر قيمة فيه) تعتبر هي القمة بالنسبة إلى الـ Stack الخاصة بنا.

* الوظيفة Pop:

كود :

Public Function Pop() As Variant
    If FValues.Count = 0 Then
        Err.Raise vbObjectError + 100, "TStack.Pop", "Stack is empty"
    Else
        Pop = FValues(FValues.Count)
        FValues.Remove FValues.Count
    End If
End Function

تقوم الوظيفة Pop بقراءة و إزالة آخر قيمة في الـ Stack (الموجودة عند القمة). نلاحظ أن الوظيفة Pop تتأكد أولاً من أن الـ Stack تحتوي فعلاً على قيم. فإذا كان عدد القيم صفراً فإنها تتسبب في حدوث خطأ. أما إذا كانت هناك قيم فإنها تعيد آخر قيمة ثم تقوم بإزالتها من الـ Stack.

* الوظيفة Peek:

كود :

Public Function Peek() As Variant
    If FValues.Count = 0 Then
        Err.Raise vbObjectError + 100, "TStack.Peek", "Stack is empty"
    Else
        Peek = FValues(FValues.Count)
    End If
End Function

الوظيفة Peek تشبه الوظيفة Pop في أنها تعيد القيمة الموجودة عند قمة الـ Stack لكنها تختلف عنها في أنها لا تقوم بحذف أو إزالة تلك القيمة من الـ Stack.

* الوظيفة Is_Empty:

كود :

Public Function Is_Empty() As Boolean
    Is_Empty = (FValues.Count = 0)
End Function

هذه الوظيفة (Is_Empty) للتأكد من كون الـ Stack فارغة أم لا. تعيد True إذا كانت الـ Stack فارغة (لا تحتوي على قيم)، و تعيد False بخلاف ذلك.

* الوظيفة Make_Empty:

كود :

Public Sub Make_Empty()
    Do While FValues.Count <> 0
        FValues.Remove FValues.Count
    Loop
End Sub

نستعمل الوظيفة Make_Empty لإفلراغ الـ Stack، أي حذف كافة القيم منها.

* الوظيفة Count:

كود :

Public Function Count() As Long
    Count = FValues.Count
End Function

تعيد الوظيفة Count عدد القيم في الـ Stack.

*** نأتي الآن إلى خوارزمية التحويل:
= نفرض أن التعبير الأصلي مخزن في متغير اسمه Infix و أن الناتج سيكون في متغير اسمه Posfix.
= الخوارزمية تستعمل الـ Stack من أجل التخزين المؤقت للعوامل (الإشارات الحسابية) و الأقواس اليسرى ")".
= التعبير الناتج (Postfix) يتم تكوينه من اليسار إلى اليمين باستعمال القيم من التعبير الأول (Infix) و العوامل (الإشارات) المخزنة في الـ Stack.
= العملية تبدأ بوضع قوس أيسر على الـ Stack و إضافة قوس أيمن إلى نهاية التعبير الأصلي (Infix).
= تنتهي الخوارزمية عندما تصبح الـ Stack فارغة.

الخطوة 1: ضع (خزن) قوساً أيسر ")" في الـ Stack و أضف قوساً أيمن "(" إلى نهاية الـ Infix.
الخطوة 2: تتبع الـ Infix من اليسار (البداية) إلى اليمين (النهاية) و كرر الخطوات من 3 إلى 6 لكل عنصر في التعبير Infix إلى أن تصبح الـ Stack فارغة.
الخطوة 3: إذا التقيت بمعامل (قيمة أو عدد) أضفه إلى Postfix.
الخطوة 4: إذا التقيت بقوس أيسر ")" ضعه على الـ Stack.
الخطوة 5: إذا التقيت بعامل (إشارة حسابية) إذن:
- أ. قم بالسحب (Pop) المتكرر من الـ Stack و الإضافة إلى Postfix لكل عامل (إشارة) موجود عند قمة الـ Stack و له أسبقية مساوية أو أعلى من العامل الذي التقيت به في Infix.
- ب. أضف العامل الذي التقيت به في Infix إلى الـ Stack.
الخطوة 6: إذا التقيت بقوس أيمن "(" إذن:
- أ. قم بالسحب (Pop) المتكرر من الـ Stack و الإضافة إلى Postfix لكل عامل (إشارة) موجود عند قمة الـ Stack إلى أن تلتقي بقوس أيسر عند قمة الـ Stack.
- ب. أزل القوس الأيسر من الـ Stack (و لكن لا تضفه إلى Postfix).
الخطوة 7: النهاية (اخرج).

* في المشاركة القادمة سنشرح كود VB الذي يستند على الشرح المذكور أعلاه.

نرجو الاستفادة و السلام.