【C++】中綴表達式求值前言 & 劇情

文章目錄

• 前言 & 劇情
• • 思考
• 實作方法
• 參考代碼
• 後話

前言 & 劇情

任務背景：

話說，從前計算機界有三大幫派，一個叫做字尾表達式，有一個叫做波蘭的帝國撐腰，也叫作波蘭表達式；一個叫做字首表達式，和字尾表達式是死對頭，專門和波蘭對着幹，也叫作逆波蘭表達式；還有一個小弟叫作中綴表達式的，在電腦計算中身位卑微，然而廣泛應用于一般生活中。——到現在，勝負不分。

中綴表達式在計算機界身位卑微，為了維護宇宙的秩序平衡，你決定幫TA一把……

主線任務：拯救中綴表達式 已解鎖。

NPC交流階段：

中綴表達式：大哥幫幫我，他們都說字首和字尾表達式很好算，說我除了看得懂啥用沒有，又難算，寫的還多，我該怎麼辦呐……QAQ

你：相信我，為了宇宙平衡，我一定會幫你的！！（還好隻有加減乘除）

思考

嗯，有哪些方法呢？

要麼，把中綴表達式轉成字尾或字首表達式；

要麼，就直接求值。

作為一個熱愛暴力的好青年，當然使用直接求值法。

想要康中綴轉字尾的朋友們可以康康這裡。

實作方法

學習Python。

上面那句話是誰說的？鄙視競賽中的py黨。

首先，因為要一算括号中的答案，又可能有括号套括号，很容易想到遞歸。

但是——

遞歸這種東西，是一般人的腦子想象不出來的。 ——某老師

放棄……

換個思路，俗話說得好，可以不用函數解決任何題目，（我一直認為，面向資料程式設計是最好的形式，）因為dfs是遞歸實作的，也可以用棧實作，是以——為什麼不想一想用棧實作？

立馬動手。

對一個字元，有2種情況一種是數，一種是運算符号。

數好處理，就一位一位加上。

運算符号要考慮優先級： ( , ) > ∗ , / > + , − (,)>*,/>+,- (,)>∗,/>+,−

可以考慮遇到乘除先處理連乘除的情況，遇到括号就處理這一對括号裡的所有情況。

開兩個棧，一個記錄遇到的運算符，一個記錄參與運算的數。

遇到非右括号的字元就放進運算符的棧中，讀完了一個數就放進數的棧中，然後遇到了相應的符号就處理一下就好啦。

具體實作見代碼……

參考代碼

Python newbie!!

算了這才是C++……

#define int long long
long long num;
char a[100001];
stack<long long> s1;//存運算數的棧
stack<char> s2;//存符号的棧
signed main() {
    cin >> a;
    int len = strlen(a); a[len] = ')';//在字元串兩邊加上括号友善計算
    s2.push('(');
    bool innum = 0;//是否輸入了數字
    for(int i = 0; i <= len; i++) {
        if(a[i] == ' ') continue;
        if('0' <= a[i] && a[i] <= '9') num = (num << 1) + (num << 3) + (a[i] ^ 48), innum = 1;
        //和快讀一個原理
        else {
            if(innum) s1.push(num), innum = 0;//輸入完數字後，往棧中添加這個數
            num = 0;
            if((a[i] == '+' || a[i] == '-') && !s2.empty()) {
            //因為乘法和除法的優先級僅次于括号，是以遇見加減号是先把前面的連乘計算了
                char c = s2.top();
                while((c == '*' || c == '/') && !s2.empty()) {
                    s2.pop();
                    int a = s1.top(); s1.pop();
                    int b = s1.top(); s1.pop();//抽兩個運算數出來
                    if(c == '*') s1.push(a * b);
                    if(c == '/') s1.push(a / b);
                    c = s2.top();
                }
                //計算連乘除
            }
            if(a[i] == ')') {
            //如果遇見了括号，因為其優先級最高，就把這個括号内包含的都先計算了
                char c = s2.top(); s2.pop();
                while(c != '(') {
                    int a = s1.top(); s1.pop();
                    int b = s1.top(); s1.pop();
                    if(c == '-') s1.push(b - a);//注意用的是棧，是以b在前面
                    if(c == '+') s1.push(a + b);
                    if(c == '*') s1.push(a * b);
                    if(c == '/') s1.push(a / b);
                    c = s2.top(); s2.pop();
                }
            }
            else s2.push(a[i]);//把這個運算符壓入棧中
        }
    }
    int ans = s1.top();
    cout << ans << endl;
}
           

後話

中綴表達式：感謝英雄讓我翻身了！

你：不謝不謝。

中綴表達式：那個……我還有一個要求……

你：盡管說，我随便亂虐這些水題。

（突然，你後背發涼……）

中綴表達式：那個，他們說一個數上 1 0 20000 10^{20000} 1020000，大神我該怎麼辦呐……诶诶诶大神你别暈過去了呀！！