Convert Infix to Postfix Expression (แปลง Infix เป็น Postfix)

Infix Expression คือรูปแบบมาตรฐานที่มนุษย์อ่านง่าย (เช่น A + B * C) แต่คอมพิวเตอร์ต้องการ Postfix เพื่อคำนวณง่ายขึ้น

การแปลงใช้ **Stack** จัดการ Operator และ Parenthesis ตาม Precedence และ Associativity

Operator Precedence (ลำดับความสำคัญ)

ตัวอย่าง Input และ Output

Input: x^y/(5*z)+2
Output: Postfix Form Is: xy^5z*/2+

อัลกอริทึม Shunting Yard (Dijkstra)

ฟังก์ชัน infixToPostfix(infix)

ขั้นตอน:

1. Push # เข้า Stack (Sentinel ป้องกัน Underflow)
2. สำหรับแต่ละตัวอักษร ch ใน infix:
   • Alphanumeric: เพิ่มเข้า Postfix ทันที
   • ( : Push เข้า Stack
   • ^ : Push เข้า Stack (Right-associative ไม่ pop operator เดิม)
   • ) : Pop และเพิ่มเข้า Postfix จนกว่าจะเจอ (, แล้ว Pop ( ทิ้ง
   • Operator อื่น (+, -, *, /):
     • While Stack top มี Precedence ≥ ch: Pop และเพิ่มเข้า Postfix
     • Push ch เข้า Stack
3. จบการอ่าน: Pop ทุกตัวใน Stack (ยกเว้น #) เข้า Postfix

ตัวอย่างโค้ด C++

#include <iostream>
#include <stack>
#include <cctype>
#include <string>
using namespace std;

int preced(char ch) {
    if (ch == '+' || ch == '-') return 1;
    if (ch == '*' || ch == '/') return 2;
    if (ch == '^') return 3;
    return 0;
}

string inToPost(string infix) {
    stack stk;
    stk.push('#');
    string postfix = "";

    for (char ch : infix) {
        if (isalnum(ch)) {
            postfix += ch;
        } else if (ch == '(') {
            stk.push(ch);
        } else if (ch == '^') {
            stk.push(ch);
        } else if (ch == ')') {
            while (stk.top() != '#' && stk.top() != '(') {
                postfix += stk.top(); stk.pop();
            }
            stk.pop(); // remove '('
        } else {
            while (stk.top() != '#' && preced(ch) <= preced(stk.top())) {
                postfix += stk.top(); stk.pop();
            }
            stk.push(ch);
        }
    }

    while (stk.top() != '#') {
        postfix += stk.top(); stk.pop();
    }
    return postfix;
}

int main() {
    string infix = "x^y/(5*z)+2";
    cout << "Postfix Form Is: " << inToPost(infix) << endl;
    return 0;
}

Output

Postfix Form Is: xy^5z*/2+

ความซับซ้อน

• Time: O(n)
• Space: O(n) - Stack

การจัดการ Right-Associativity ของ ^

ในโค้ดข้างต้น ใช้ preced(ch) <= preced(stk.top()) ซึ่งทำให้ ^ เป็น Left-associative

ถ้าต้องการ Right-associative จริง: ใช้ preced(ch) < preced(stk.top()) สำหรับ ^ (strictly less)