Chuyển Đổi Trung Tố Sang Hậu Tố (Infix to Postfix)

Giới thiệu

Biểu thức trung tố (infix) dễ đọc cho con người nhưng máy tính cần hậu tố để tính toán. Sử dụng ngăn xếp để chuyển đổi, tuân theo thứ tự ưu tiên của toán tử.

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

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

Thuật toán

infixToPostfix(infix)
Begin
    push '#' vào stack
    for mỗi ký tự ch trong infix do
        nếu ch là chữ/số thì thêm vào postfix
        else nếu ch = '(' thì push '('
        else nếu ch = '^' thì push '^'
        else nếu ch = ')' thì
            pop và thêm vào postfix cho đến khi gặp '('
            pop '('
        else
            while stack không rỗng và precedence(ch) <= precedence(stack.top) do
                pop và thêm vào postfix
            done
            push ch
        done
    done
    pop phần còn lại trong stack thêm vào postfix
    return postfix
End

Ví dụ C++

#include <iostream>
#include <stack>
#include <cctype>
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(); // remove '('
        } 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;
}

int main() {
    string infix = "x^y/(5*z)+2";
    cout << "Dạng hậu tố: " << inToPost(infix) << endl;
    return 0;
}

Kết quả

Dạng hậu tố: xy^5z*/2+