Chuyển Đổi Trung Tố Sang Tiền Tố (Infix to Prefix)

Giới thiệu

Chuyển biểu thức trung tố sang tiền tố (prefix) bằng cách: đảo ngược chuỗi, đổi ngoặc đơn, chuyển sang hậu tố, rồi đảo ngược kết quả.

Đầu vào và Đầu ra

Đầu vào: "x^y/(5*z)+2"
Đầu ra: "+/^xy*5z2"

Thuật toán

infixToPrefix(infix)
Begin
    đảo ngược infix
    for mỗi ký tự ch trong infix đảo ngược do
        nếu ch = '(' thì đổi thành ')'
        else nếu ch = ')' thì đổi thành '('
    done
    postfix := infixToPostfix(infix_đã_đảo)
    prefix := đảo ngược postfix
    return prefix
End

Ví dụ C++

#include <iostream>
#include <stack>
#include <cctype>
#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('(');
        else if (ch == '^') stk.push('^');
        else if (ch == ')') {
            while (stk.top() != '#' && stk.top() != '(') {
                postfix += stk.top(); stk.pop();
            }
            stk.pop();
        } else {
            if (preced(ch) > preced(stk.top())) stk.push(ch);
            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 << "Dạng tiền tố: " << inToPre(infix) << endl;
    return 0;
}

Kết quả

Dạng tiền tố: +/^xy*5z2