數據結構 - 棧 - 從中綴向後綴轉換表達式

數據結構 – 棧 – 從中綴向後綴轉換表達式

2022 年 3 月 31 日
筆記
數據結構 - 棧

用棧來實現中綴表達式向後綴表達式的轉換。

從中綴向後綴轉換表達式

中綴表達式就是我們通常所書寫的數學表達式，後綴表達式也稱為逆波蘭表達式，在編譯程式對我們書寫的程式中的表達式進行語法檢查時，往往就可以通過逆波蘭表達式進行。我們所要設計並實現的程式就是將中綴表示的算術表達式轉換成後綴表示，例如，將中綴表達式(A-(B*C+D)*E)/(F+G)轉換為後綴表示為：ABC*D+E*-FG+/。

注意：為了簡化編程實現，假定變數名均為單個字母，運算符只有＋，－，＊，／ 和^（指數運算），可以處理圓括弧()，並假定輸入的算術表達式正確。

要求：使用棧數據結構實現，輸入的中綴表達式以＃號結束。

輸入格式

整數 \(N\)，表示下面有 \(N\) 個中綴表達式。
\(N\) 個由單個字母和運算符構成的表達式。

輸出格式

\(N\) 個後綴表達式。

輸入輸出樣例

樣例 1

輸入

1
(A-(B*C+D)*E)/(F+G)#

輸出

ABC*D+E*-FG+/

樣例 2

輸入

2
a+b*c-d#
a-b*(c+d)#

輸出

abc*+d-
abcd+*-

注意輸入輸出的每一行都有換行符\n。

題解

考慮此問題時，先將問題進行簡化。比如假設一個表達式中只要運算符，沒有左右括弧()，此時我們只需對運算符以優先順序的高低維護一個單調棧（棧中運算符元素嚴格單調遞增）。

考慮括弧時，對左右括弧按括弧匹配的思路，在括弧對的內部對運算符進行的單調棧維護。每次匹配到一對括弧就在進行下一次操作前，就將此對括弧內的所有運算符全部歸約完即可（一次歸約即一次兩個操作數與一個操作符的匹配過程）。

當然還有另一種思路，就是將括弧本身視為運算符，為左括弧(賦予最低優先順序，為右括弧)賦予最高優先順序，也可以完成中綴表達式向後綴表達式的轉換。

為清晰期間，我們使用前一種思路，即對左右括弧按括弧匹配的同時，在括弧對內部對運算符進行單調棧維護。

題解程式碼

程式碼如下：

#include <cstdio>
#include <cstdlib>
#include <stack>
#include <iostream>

using namespace std;

bool isalpha(char ch)
{
    if (('a' <= ch && ch <= 'z') || ('A' <= ch && ch <= 'Z')) return true;
    else return false;
}

int order(char op)
{
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    if (op == '^') return 3;
}
int main()
{
    // 不考慮括弧時，只需對運算符以優先順序維護一個單調棧（棧中元素嚴格單調遞增）
    // 考慮括弧時，對左右括弧按括弧匹配的思路，在括弧對內部對運算符進行的單調棧維護
    // 將一對括弧對視為一個字母變數
    int n; cin >> n;
    while (n--) {
        char ch;
        stack<char> op;
        ch = getchar();
        while ((ch = getchar()) && ch != '#') {
            if (isalpha(ch)) {
                printf("%c", ch);
            }
            else if (ch == ')') {
                // 匹配到右括弧，直接將這對括弧內的所有運算都進行歸約
                while (!op.empty() && op.top() != '(') {
                    char tmp = op.top();
                    op.pop();
                    printf("%c", tmp);
                }
                if (!op.empty()) op.pop();
            }
            else if (ch == '(') {
                op.push('(');
            }
            else {
                // 維持棧的嚴格單調遞增性質
                // while ((!op.empty() && op.top() != '(') && (((op.top() == ch) && (ch == '^')) ? (order(op.top()) > order(ch)) : (order(op.top()) >= order(ch)))) {
                while (!op.empty() && op.top() != '(') {
                    if (order(op.top()) >= order(ch)) {
                        printf("%c", op.top());
                        op.pop();
                    }
                    else break;
                }
                op.push(ch);
            }
        }
        while (!op.empty()) {
            printf("%c", op.top());
            op.pop();
        }
        printf("\n");
    }

    return 0;
}

這裡提醒一點，我完成此題是在北理的樂學網站上進行的提交，上述程式碼會有兩個測試用例無法通過，後面我通過在網上查找到了其他人寫的能通過的程式碼，通過與我自己的程式碼比對，發現是指數運算的問題。當給定的輸入為

1
a^b^c^d#

通過程式碼的輸出為

abcd^^^

我自己的程式碼的輸出為

ab^c^d^

但根據後綴表達式的定義（也許是我搞錯了？），貌似後一個輸出才是正確的。也就是說北理的那道題的給的「正確輸出」可能有問題，導致有兩個測試用例（應該是關於指數運算的）通過不了。能通過北理測試用例的程式碼如下：

#include <cstdio>
#include <cstdlib>
#include <stack>
#include <iostream>

using namespace std;

bool isalpha(char ch)
{
    if (('a' <= ch && ch <= 'z') || ('A' <= ch && ch <= 'Z')) return true;
    else return false;
}

int order(char op)
{
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    if (op == '^') return 3;
}
int main()
{
    // 對運算符以優先順序維護一個單調棧（棧中元素嚴格單調遞增，除非有左右括弧規定運算順序）
    int n; cin >> n;
    while (n--) {
        char ch;
        stack<char> op;
        ch = getchar();
        while ((ch = getchar()) && ch != '#') {
            if (isalpha(ch)) {
                printf("%c", ch);
            }
            else if (ch == ')') {
                // 匹配到右括弧，直接將這對括弧內的所有運算都進行歸約
                while (!op.empty() && op.top() != '(') {
                    char tmp = op.top();
                    op.pop();
                    printf("%c", tmp);
                }
                if (!op.empty()) op.pop();
            }
            else if (ch == '(') {
                op.push('(');
            }
            else {
                while ((!op.empty() && op.top() != '(') && (((op.top() == ch) && (ch == '^')) ? (order(op.top()) > order(ch)) : (order(op.top()) >= order(ch)))) {
                    //while (!op.empty() && op.top() != '(') {
                        //if (order(op.top()) >= order(ch)) {
                    printf("%c", op.top());
                    op.pop();
                    //}
                    //else break;
                }
                op.push(ch);
            }
        }
        while (!op.empty()) {
            printf("%c", op.top());
            op.pop();
        }
        printf("\n");
    }

    return 0;
}

Tags: 數據結構 - 棧