Link list

โครงสร้างข้อมูลแบบ stack

          

การแปลงนิพจน์ postfix เป็น infix

การแปลงนิพจน์ postfix เป็น infix

     1   เริ่มทำจากซ้ายไปขวา

     2   ถ้าเจอ โอเปอแรนด์ให้นำไปใส่ไว้ใน Stack ไปเรื่อยๆ

     3    ถ้าเมื่อไหร่เจอตัว โอเปอเรเตอร์ จึงทำการหาผลลัพธ์
         จากคู่ของโอเปอแรนด์ที่พบก่อนหน้า

ตัวอย่าง      จงแปลงนิพจน์  postfix ต่อไปนี้ให้เป็น infix

                                   A B C + *  

  

แบบฝึกหัด

การแปลงนิพจน์ infix เป็น postfix

การแปลงนิพจน์ infix เป็น postfix

ต้องรู้ลำดับการทำงานของตัวดำเนินการก่อน

ลำดับการทำงานของตัวดำเนินการทางคณิตศาสตร์จากสูงไปต่ำ

1. เครื่องหมายวงเล็บ (ไม่ใช่ตัวดำเนินการ)

2. ตัวดำเนินการยกกำลัง (^)

3. ตัวดำเนินการคูณ (*) และหาร (/)

4. ตัวดำเนินการบวก (+) และลบ (-)

โดยตัวดำเนินการที่มีลำดับเดียวกันให้ทำงานจากซ้ายไปขวา

ยกเว้นตัวดำเนินการยกกำลังให้ทำงานจากขวามาซ้าย

ตัวอย่าง

           A+B+C     หมายถึง    (A+B)+C 

              A^B^C    หมายถึง     A^(B^C)

                 ******************************

การแปลงนิพจน์ infix เป็น postfix

จะใช้ stack ในการเก็บตัวดำเนินการ

ลำดับการแปลง infix เป็น postfix

1  ถ้าข้อมุลเป็นตัวถูกดำเนินการ (operand) ให้นำไปเป็นผลลัพธ์

2  ถ้าข้อมูลเข้าเป็นตัวดำเนินการ (operator) ให้ปฎิบัติดังนี้

      2.1  ถ้าstack ยังว่างให้ทำการ push
          ตัวดำเนินการเก็บลงstack

      2.2  ถ้าstack ไม่ว่างให้ทำการเปรียบเทียบตัวดำเนินการ

         ที่นำเข้ามากับตัวดำเนินการที่ตำแหน่ง Top ของ stack

             2.2.1 ถ้าตัวดำเนินการที่นำเข้ามีลำดับความสำคัญมากกว่า

                  ตัวดำเนินการที่ตำแหน่ง top ของ stack  ให้ทำการ

                  push ตัวเนินการนั้นเก็บลงใน stack

          2.2.2  ถ้าตัวดำเนินการที่นำเข้ามา มีลำดับความสำคัญน้อยกว่า

                   หรือเท่ากับตัวดำเนินการที่ตำแหน่ง top ของ stack  

                   ให้ทำการ pop ตัวดำเนินการที่ตำแหน่ง top ของ stack

                        นำออกไปต่อท้ายนิพจน์ผลลัพธ์ และทำการเปรียบเทียบ

                   ตัวดำเนินการที่นำเข้ามากับตัวดำเนินการที่ตำแหน่ง top

                       ของ stack ต่อไป    จนกระทั่งตัวดำเนินการที่นำเข้ามามี

                  ลำดับความสำคัญมากกว่าตัวดำเนินการที่ตำแหน่ง top ของ

                  stack จึงหยุดเปรียบเทียบและให้ทำการ pushตัวดำเนินการ

                  ที่นำเข้ามานั้นเก็บลงใน stack

3. ถ้าข้อมูลเข้าเป็นเครื่องหมายวงเล็บเปิด   ให้ทำการ push เครื่องหมาย

    วงเล็บเปิดเก็บลงใน stack

4. ถ้าข้อมูลเข้าเป็นเครื่องหมายวงเล็บปิดให้ทำการ pop ข้อมูลออกจาก

    stack นำออกไปเป็นผลลัพธ์โดยจะทำการ  pop  ต่อไปจนกว่าจะพบ

    เครื่องหมายวงเล็บเปิด หลังจากนั้นให้ทิ้งเครื่องหมายวงเล็บเปิดและ

    เครื่องหมายวงเล็บปิดคู่เดิมไป

5. ถ้าข้อมูลเข้าหมดให้ทำการ pop ข้อมูลออกจาก stack นำออกไปเป็น

    ผลลัพธ์โดยทำการ pop ต่อไปจนกระทั่ง stack ว่าง

      **********************************************************************

ตัวอย่าง 

ตัวอย่าง                จงแปลงนิพจน์  infix  เป็น  postfix
         

แบบฝึกหัด

จงแปลงนิพจน์  infix  ต่อไปนี้ให้เป็นนิพจน์ postfix  โดยใช้  stack

1       D - B + C

2      (A + B) * C -D * F + C

3      A * B - (C + D ) + E

 

ความหมายของนิพจน์ prefix, นิพจน์ infix, นิพจน์ postfix

นิพจน์  prefix    นิพจน์ infix    นิพจน์ postfix

v นิพจน์ Infix (Infix Expression) คือ

       นิพจน์ที่อยุ่ในรูปแบบ เครื่องหมายดำเนินการ (operator)

       อยู่ระหว่างตัวถูกดำเนินการ (operands) เช่น A+B

   ******************************

v   นิพจน์ Prefix (Prefix Expression) คือ

     นิพจน์ที่อยู่ในรูปแบบเครื่องหมายดำเนินการ (operator)

      อยู่หน้าตัวถูกดำเนินการ (operands) เช่น +AB

     *****************************

v   นิพจน์ Postfix (Postfix Expression) คือ

    นิพจน์ที่อยู่ในรูปแบบเครื่องหมายดำเนินการ (operator)

     อยู่หลังตัวถูกดำเนินการ (operands) เช่น AB+

    ******************************