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

ตัวอย่างขั้นตอน:

Infix:     x^y/(5*z)+2
Reverse:   2+ )z*5( /y^x
Swap ():   2+ (z*5) /y^x
Postfix:   2 5 z * / x y ^ +
Reverse:   + ^ y x / * z 5 2  →  +/^xy*5z2

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

#include <iostream>
#include <stack>
#include <cctype>
#include <string>
#include <algorithm>
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();
        } 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;
}

string inToPre(string infix) {
    reverse(infix.begin(), infix.end());
    for (char &ch : infix) {
        if (ch == '(') ch = ')';
        else if (ch == ')') ch = '(';
    }
    string prefix = inToPost(infix);
    reverse(prefix.begin(), prefix.end());
    return prefix;
}

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

Output

Prefix Form Is: +/^xy*5z2

ความซับซ้อน

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

วิธีอื่น: Direct Infix to Prefix

Scan จากขวาไปซ้าย ใช้ Stack คล้าย Infix-to-Postfix แต่กลับด้าน (จัดการ precedence และ parentheses อย่างถูกต้อง)