22張圖帶你深入剖析字首、中綴、字尾表達式以及表達式求值

一、基本概念

在本篇文章當中主要跟大家介紹以下幾點

字首、中綴和字尾表達式。
如何将中綴表達式轉化成字尾表達式。
如何使用字尾表達式進行求值。

表達式求值這是一個比較經典的計算機系統基礎問題，但是整個過程比較抽象，本文主要通過圖解的方法幫助大家了解這個問題。

表達式介紹

字尾表達式也稱作逆波蘭表達式，字首表達式也稱作波蘭表達式，這個是因為這是由波蘭數學家楊-武卡謝維奇提出來的，用于簡化命題邏輯的一種方法。

中綴表達式

我們常見的數學表達式就是中綴表達式，比如說：\(1+2\)，像這種我們從小到大經常見到的表達式就叫做中綴表達式，這個表達式的特點就是将運算符（加減乘除）放在兩個操作數（數字）中間。

字尾表達式

字尾表達式和中綴表達式的最大差別就是，它不是将運算符放在操作數中間，而是将運算符放在操作數後面，比如上面的中綴表達式\(1+2\)轉化成字尾表達式就為\(12+\)。

字首表達式

字首表達式就是将運算符放在操作數的前面，比如上面的中綴表達式\(1+2\)轉化成字首表達式之後為\(+12\)。

二、人腦模拟中綴表達式轉字尾表達式

上面的表達式還是比較簡單，可能不足以幫助大家好好了解表達式之間的轉化過程。

中綴表達式：\(\large A+B∗(C−D)−E/F\)

現在我們來将上面的中綴表達式轉化成字尾表達式，我們的第一個計算的部分如下（括号裡面的優先計算）：

根據我們的轉化原理：将運算符放在操作數後面，

上面的得到的字尾表達式繼續進行轉化（現在需要計算\(B\)乘以後面的那個部分）：

繼續進行轉化（從左往後進行計算）：

繼續進行轉化（除法的優先級比減法高）：

得到最終的結果：

三、程式計算中綴表達式轉化成字尾表達式

将中綴表達式轉化成字尾表達式有以下幾條規則（下面的棧是存儲操作符的棧，而且隻存儲操作符）：

從左到右進行周遊。
遇到操作數，直接加入到字尾表達式當中。
遇到界限符。遇到“(”直接入棧，遇到“)”則依次彈出棧内運算符并加入字尾表達式，直到彈出“(” 為止，注意:“(” 不加入字尾表達式。
遇到運算符。依次彈出棧中優先級高于或等于目前運算符的所有運算符，并加入字尾表達式，若碰到“(”或棧空則停止。之後再把目前運算符入棧。

現在我們根據上面的規則來将上文當中的中綴表達式轉化成字尾表達式。

周遊到\(A\)，根據第二條規則，将A加入到字尾表達式當中，目前的字尾表達式為：\(A\)。

現在周遊到加号，根據前面的規則需要彈出棧裡面優先級大的運算符，再将加号加入到棧中，目前的字尾表達式為\(A\)。

周遊到\(B\)，直接加入到字尾表達式當中，目前的字尾表達式為\(AB\)。

周遊到∗，根據規則直接将其加入到棧中，目前字尾表達式為\(AB\)。

周遊到\((\)，根據規則直接将其加入到棧中，目前字尾表達式為\(AB\)。

周遊到\(C\)，則直接将其加入到字尾表達式當中，目前字尾表達式為\(ABC\)。
周遊到\(−\)，根據規則将其加入到棧中，目前字尾表達式為\(ABC\)。

周遊到\(D\)，則将其直接加入到字尾表達式當中，目前的字尾表達式為\(ABCD\)。
周遊到\()\)，則需要将棧中的符号彈出，直到遇到\((\)，目前的字尾表達式為\(ABCD−\)。

周遊到\(−\)，需要将棧中優先級大于等于\(−\)的運算符彈出，則目前的字尾表達式為\(ABCD−∗+\)，再将\(−\)壓入棧中。

周遊到\(E\)，直接将數字加入到字尾表達式當中，則目前的字尾表達式為\(ABCD−∗+E\)。
周遊到\(/\)，将棧中優先級大于等于\(/\)的運算符，再将\(/\)壓入到棧中，目前的字尾表達式為\(ABCD−∗+E\)。

周遊到F，直接将其加入到字尾表達式當中，則目前的字尾表達式為\(ABCD−∗+EF\)。
最終将棧中所有的運算符都彈出，得到的字尾表達式為\(ABCD−∗+EF/−\)

經過上面的過程就可以将一個中綴表達式轉成字尾表達式了，大家如果想要代碼實作，隻需要在周遊資料的時候根據上面四個規則一個個進行判斷即可，程式并不困難，就是邏輯稍微有點多，需要考慮更多的問題，在寫代碼的時候需要細緻一點。

三、程式計算字尾表達式求值

在前文當中我們已經得到了表達式\(A+B∗(C−D)−E/F\)的字尾表達式為\(ABCD−∗+EF/−\)。現在我們需要将這個字尾表達式進行求值。根據字尾表達式求值主要有以下兩條規則：

如果遇到數字直接将其加入到數字棧。
如果遇到操作符直接從操作數棧彈出兩個資料進行對應的運算，再将運算結果加入到棧中。

現在我們進行字尾表達式的求值過程;

首先前面四個\(ABCD\)都是數字，根據上面提到的第一條規則，我們都需要将數字壓入到棧當中，是以周遊四個數字之後，情況如下：

現在周遊到\(−\)，我們需要将\(D\)和\(C\)彈出，然後進行\(−\)操作的運算，再将結果壓入棧中。

現在周遊到\(∗\)，我們需要将\(C−D=M\)和\(B\)彈出，進行乘法運算，然後将結果壓入棧中。

現在我們周遊到\(+\)，需要将棧中剩餘的兩個數彈出，進行加法運算，在将結果壓棧。

周遊\(EF\)都需要将這兩個數壓入到棧當中。

現在周遊到\(/\)，需要進行除法運算，在将得到的結果壓入到棧中。

最後周遊到\(−\)，将棧中的兩個數彈出棧，進行減法運算得到最後的結果。

五、計算表達式的值

#include <bits/stdc++.h>

using namespace std;

/*
測試用例I：
(2+2)*(1+1)

答案：8

測試用例II：注意：不能在輸入中帶空格，會算錯！！！
2+(3*4)-((5*9-5)/8-4)

答案：13
*/

stack<int> num; //數字棧
stack<char> op; //操作符棧

//優先級表
unordered_map<char, int> h{{'+', 1},
                           {'-', 1},
                           {'*', 2},
                           {'/', 2}};

/**
 * 功能：計算兩個數的和差積商
 */
void eval（) {
    int a = num.top(); //第二個操作數
    num.pop();

    int b = num.top(); //第一個操作數
    num.pop();

    char p = op.top(); //運算符
    op.pop();

    int r = 0; //結果
    //計算結果
    if (p == '+')
        r = b + a;
    else if (p == '-')
        r = b - a;
    else if (p == '*')
        r = b * a;
    else if (p == '/')
        r = b / a;
    //結果入棧
    num.push(r);
}

//讀取連續的數字
void readNum(string s, int &pos, int &x) {
    while (pos < s.size() && isdigit(s[pos])) {
        x = x * 10 + s[pos] - '0';
        pos++;
    }
    //在循環裡加冒了，需要傳回一步,友善下一個人開始
    pos--;
}

int main() {
    //讀入表達式
    string s;
    cin >> s;
    //周遊字元串的每一位
    for (int i = 0; i < s.size(); i++) {
        // 1、數字則入棧
        if (isdigit(s[i])) {
            //讀出完整的數字
            int x = 0;
            readNum(s, i, x);
            num.push(x); //數字入棧
        }
        // 2、左括号無優先級，直接入棧
        else if (s[i] == '(')
            op.push(s[i]);
        // 3、右括号計算最近一對括号裡面的
        else if (s[i] == ')') {
            //一直找到到左括号
            while (op.top() != '(') eval（); //将左右括号之間的計算完，維護回棧裡
            //左括号出棧
            op.pop();
        } else { // 4、運算符
            //如果待入棧運算符優先級低，則先計算
            while (op.size() && h[op.top()] >= h[s[i]]) eval（);
            op.push(s[i]); //操作符入棧
        }
    }
    // 5、//剩餘的進行計算
    while (op.size()) eval（);
    // 6、輸出結果
    cout << num.top() << endl;
    return 0;
}

22張圖帶你深入剖析字首、中綴、字尾表達式以及表達式求值