題目資訊

中綴運算式就是我們通常所書寫的數學運算式，后綴運算式也稱為逆波蘭運算式，在編譯程式對我們書寫的程式中的運算式進行語法檢查時，往往就可以通過逆波蘭運算式進行，我們所要設計并實作的程式就是將中綴表示的算術運算式轉換成后綴表示，例如，將中綴運算式
(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+*-

解答

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

stack <char> s;

int main()
{
    //freopen("/Users/zhj/Downloads/test.txt","r",stdin);
    int N;
    cin >> N;
    while (N--)
    {
        string in;
        cin >> in;
        int t = 0;
        while (in[t] != '#')
        {
            if (t == 0 && in[t] == '-')
            {//第一個數就是負數
                cout << in[t];
            }
            else if (isalnum(in[t]))
            {//如果是數字字母的話就輸出
                cout << in[t];
            }
            else if (in[t] == '(')
            {//是左括號的話就壓入堆疊中
                s.push(in[t]);
            }
            else if (in[t] == ')')
            {//如果是右括號的話，堆疊元素彈出，將彈出的運算子輸出直到遇到左括號為止
                while(s.top()!='(')
                {
                    cout<<s.top();
                    s.pop();
                }
                s.pop();
            }
            else if( in[t] =='-' && ( in[t - 1] == '(' || in[t - 1] == '*' || in[t - 1] == '/' || in[t - 1] == '%' || in[t - 1] == '+' || in[t - 1] == '-') )
            {//此時是負數，且之前的是這些個符號的話，證明當前是一個負數
                cout << in[t];
            }
            else
            {//其他的運算子，從堆疊中彈出元素直到遇到發現更低優先級的元素(或者堆疊為空)為止
                if(s.empty())
                {
                    s.push(in[t]);
                }
                else
                {
                    int x, y;//x=ch,y=top of the stack
                    while (1)
                    {
                        if (s.empty())
                        {
                            s.push(in[t]);
                            break;
                        }

                        char chtmp = s.top();//chtmp此時是堆疊頂的元素
                        switch (in[t])
                        {//給此時的符號標記一個優先級
                            case '^':{ x = 7; break;}
                                //10^2^2當然便是剛輸入這個^優先級別更高，因為后面還可以繼續續上^2，變成10^2^2^2
                            case '*':{ x = 4; break;}
                            case '/':{ x = 4; break;}
                            case '+':{ x = 2; break;}
                            case '-':{ x = 2; break;}
                        }
                        switch (chtmp)
                        {//給之前的符號標記一個優先級
                            case '^':{ y = 6; break;}
                            case '*':{ y = 5; break;}
                            case '/':{ y = 5; break;}
                            case '(':{ y = 1; break;}
                            case '+':{ y = 3; break;}
                                //如果之前是一個加號，此時的ch仍然是一個加號，那么理應該輸出這個+號的，所以相應的之前的優先級大一點
                            case '-':{ y = 3; break;}
                        }

                        if (y > x || y == x)
                        {//如果原來堆疊頂的優先級大于之前的優先級，那么就輸出
                            cout<<chtmp;
                            s.pop();
                            continue;
                        }
                        else
                        {//不優先說明仍然在累計，則壓入堆疊中
                            s.push(in[t]);
                            break;
                        }
                    }
                }
            }
            t++;
        }
        while (!s.empty())
        {
            cout<<s.top();
            s.pop();
        }
        cout<<endl;
    }
}

總結

本題目主要的點也就是出現在對于負數的處理上面,以下給出一些樣例供參考

10
14*10-(10)*2#
14*10-(-10)*2#
14*10--10*2#
-14*-12#
-(1-2*-3)#
-3^-(1-2*-3)#
30/(-3+3)+1#
(-2)--3*(-8)#
-2--3*-8#
-A+B#