1.手動實現中綴轉字尾

2.程式碼實現中綴轉字尾並計算表示式結果

為了簡化問題，假設算術運運算元僅由加、減、乘、除4種運運算元和左、右括號組成。

step1: 宣告棧結構

#include <iostream>
#include <string>
using namespace std;

#define MaxSize 100
template <class DataType>
struct SeqStack
{
    DataType data[MaxSize];
    DataType *top;
};

step2: 定義函數TranslateInfixExp實現中綴表示式轉字尾表示式

/* 中綴表示式轉字尾表示式 */
void TranslateInfixExp(string exp, string &result)
{
    if (exp.empty())
        return;
    // step1: 定義操作符棧並初始化棧
    struct SeqStack<char> opStack;
    opStack.top = opStack.data;

    // step2: 遍歷中綴表示式
    char cur;
    for (int i = 0; i < exp.size(); i++)
    {
        cur = exp[i];
        switch (cur)
        {
        // 遇到 '(' ，入棧
        case '(':
            *(opStack.top++) = cur;
            break;
        // 遇到 ')' ，依次將棧中的運運算元出棧並加入字尾表示式中，直至棧頂元素為 '(' ，'(' 出棧
        case ')':
            while (*(opStack.top - 1) != '(')
            {
                result.push_back(*(--opStack.top));
                result.push_back(' ');
            }
            opStack.top--;
            break;
        // 遇到 '+' 或 '-'，依次將優先順序不低於所讀運運算元的棧頂元素出棧並加入字尾表示式，然後將所讀運運算元入棧
        case '+':
        case '-':
            while ((opStack.top != opStack.data) && *(opStack.top - 1) != '(')
            {
                result.push_back(*(--opStack.top));
                result.push_back(' ');
            }
            *(opStack.top++) = cur;
            break;
        // 遇到 '*' 或 '/' ，依次將優先順序不低於所讀運運算元的棧頂元素出棧並加入字尾表示式，然後將所讀運運算元入棧
        case '*':
        case '/':
            while ((opStack.top != opStack.data) && (*(opStack.top - 1) == '*') || (*(opStack.top - 1) == '/'))
            {
                result.push_back(*(--opStack.top));
                result.push_back(' ');
            }
            *(opStack.top++) = cur;
            break;
        // 遇到數位字元，直接入棧
        default:
            while (cur >= '0' && cur <= '9')
            {
                result.push_back(cur);
                cur = exp[++i];
            }
            result.push_back(' ');
            i--; // 回退至後續首個尚未進行優先順序判斷的操作字元
            break;
        }
    }
    // step3: 將棧內剩餘元素依次出棧
    while (opStack.top != opStack.data)
    {
        result.push_back(*(--opStack.top));
        result.push_back(' ');
    }
    return;
}

注意：

1. 在將中綴表示式轉字尾表示式過程中，每輸出一個數位字元，需要在其後補一個空格（與其他相鄰數位字元隔開），否則一連串數位字元放在一起無法區分是一個數位還是兩個數位。
2. 遇到數位字元入棧時，若當前運算項位數>1時，需要在當前數位字元入棧後後移一位並重復入棧（程式碼中switch的default段程式碼），並在運算項入棧完畢之後需要將索引i回退至後續首個尚未進行優先順序判斷的運運算元上（即非數位字元）。

step3: 定義函數CaculatePostFixExp實現字尾表示式結果計算

/* 計算字尾表示式結果 */
float CaculatePostFixExp(string exp)
{
    float result = 0;
    if (exp.empty())
    {
        cout << "The expression is wrong!\n";
        exit(-1);
    }

    // step1 : 定義一個資料字元棧，並初始化
    struct SeqStack<float> numStack;
    numStack.top = numStack.data;

    // step2 : 遍歷字尾表示式
    char cur;
    for(int i=0; i<exp.size(); i++)
    {
        cur = exp[i];
        if (cur >= '0' && cur <= '9') // 若當前字元為數位字元
        {
            float value = 0;
            while (cur != ' ')
            {
                value = value * 10 + cur - '0';
                cur = exp[++i];
            }
            *(numStack.top++) = value;
        }
        else if(cur != ' ') // 若當前字元是運運算元（空格直接忽略）
        {
            float num1 = *(--numStack.top);
            float num2 = *(--numStack.top);
            switch (cur)
            {
            case '+':
                *(numStack.top++) = num2 + num1;
                break;
            case '-':
                *(numStack.top++) = num2 - num1;
                break;
            case '*':
                *(numStack.top++) = num2 * num1;
                break;
            case '/':
                *(numStack.top++) = num2 / num1;
                break;
            default:
                break;
            }
        }
    }
    // step3 : 棧中最終元素出棧，即為所求表示式的值 
    if (numStack.top != numStack.data)
    {
        result = *(--numStack.top);
        return result;
    }
    else
    {
        cout << "The expression is wrong!\n";
        exit(-1);
    }
}

注意：

若當前字元為運運算元且為減號'-'時，先出棧的為減數，後出棧的為被減數；對於除法'/'也一樣。

step4: main函數呼叫

int main()
{
    string infixExp;   // 儲存使用者輸入的中綴表示式
    string postfixExp; // 儲存轉換後的字尾表示式
    double result;     // 儲存字尾表示式計算機結果
    cout << "Please enter an infix expression:\n";
    cin >> infixExp; // 6+(7-1)*3+10/2
    cout << "The infix expression is:  " << infixExp << endl;
    TranslateInfixExp(infixExp, postfixExp);
    cout << "The postfix expression is:  " << postfixExp << endl;
    result = CaculatePostFixExp(postfixExp);
    cout << "The postfix expression calculation result is:  " << result << endl;
    return 0;
}

輸出：

Please enter an infix expression:
6+(7-1)*3+10/2
The infix expression is:  6+(7-1)*3+10/2
The postfix expression is:  6 7 1 - 3 * + 10 2 / +
The postfix expression calculation result is:  29