問題描述

中綴表達(dá)式就是我們通常所書寫的數(shù)學(xué)表達(dá)式，后綴表達(dá)式也稱為逆波蘭表達(dá)式，在編譯程序?qū)ξ覀儠鴮懙某绦蛑械谋磉_(dá)式進(jìn)行語法檢查時(shí)，往往就可以通過逆波蘭表達(dá)式進(jìn)行。我們所要設(shè)計(jì)并實(shí)現(xiàn)的程序就是將中綴表示的算術(shù)表達(dá)式轉(zhuǎn)換成后綴表示，例如，將中綴表達(dá)式

創(chuàng)新互聯(lián)公司網(wǎng)站建設(shè)提供從項(xiàng)目策劃、軟件開發(fā)，軟件安全維護(hù)、網(wǎng)站優(yōu)化(SEO)、網(wǎng)站分析、效果評(píng)估等整套的建站服務(wù)，主營業(yè)務(wù)為成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè)，app軟件定制開發(fā)以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務(wù)。創(chuàng)新互聯(lián)公司深信只要達(dá)到每一位用戶的要求，就會(huì)得到認(rèn)可，從而選擇與我們長期合作。這樣，我們也可以走得更遠(yuǎn)！

(A 一 (B*C 十 D)*E) ／ (F 十 G )

轉(zhuǎn)換為后綴表示為：

ABC*D十E*--FG十／

注意：為了簡化編程實(shí)現(xiàn)，假定變量名均為單個(gè)字母，運(yùn)算符只有＋，－，＊，／ 和＾（指數(shù)運(yùn)算），可以處理圓括號(hào)（），并假定輸入的算術(shù)表達(dá)式正確。

要求：使用棧數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn) ，輸入的中綴表達(dá)式以＃號(hào)結(jié)束

輸入

整數(shù)N。表示下面有N個(gè)中綴表達(dá)式

N個(gè)由單個(gè)字母和運(yùn)算符構(gòu)成的表達(dá)式

輸出

N個(gè)后綴表達(dá)式。

解題思路

該題是典型的用到棧的一種情況，同時(shí)也體現(xiàn)了棧在處理運(yùn)算符這類優(yōu)先級(jí)等問題方面擁有的特殊功效。思路是遇到字母就直接輸出；遇到符號(hào)在進(jìn)棧處理，處理方式如下：

1）如果棧為空，或遇到的元素是'('，直接入棧；

2）如果遇到的元素是')'，將棧中'('以上的全部元素彈出并輸出，'('也彈出；

3）如果遇到其他操作符，將棧中比該操作符運(yùn)算優(yōu)先級(jí)更高的元素都彈出并輸出，直到棧為空、或者遇到'('、或者遇到更低優(yōu)先級(jí)的符號(hào)；

（這里可以吧左括號(hào)在棧中的優(yōu)先級(jí)設(shè)置為最低）

4）如果讀到輸入的末尾，棧中元素依次彈出并輸出。

在這個(gè)規(guī)則中我們需要提煉一些細(xì)節(jié)，以便于寫出簡潔和正確的代碼。比如：棧為空特別容易引起RE，這個(gè)需要就情況分析是否需要檢驗(yàn)空棧；還有優(yōu)先級(jí)判斷也可以寫成一個(gè)函數(shù)，傳入一個(gè)符號(hào)，返回一個(gè)int（代表其優(yōu)先級(jí)）。（然而題主最開始很笨，是挨個(gè)判斷的）

貼源代碼

就用一個(gè)簡單的代碼啦，優(yōu)先級(jí)可以簡化。（懶中……

#include#includeusing namespace std;

int main() {
    int N;
    cin >>N;
    getchar();
    stacksig;
    char c;
    while (N--) {
        while (1) {
            cin.get(c);

            if ('#' == c) {
                getchar();
                while (!sig.empty()) {
                    cout<< sig.top();
                    sig.pop();
                }
                cout<< endl;
                break;
            }
            else if ((c >= 'A' && c<= 'Z') || (c >= 'a' && c<= 'z')) {
                cout<< c;
            }
            //運(yùn)算符:
            else {
                if (sig.empty()) sig.push(c);

                else {
                    if (')' == c) {
                        while (sig.top() != '(') {
                            cout<< sig.top();
                            sig.pop();
                        }
                        sig.pop();//'('
                    }
                    else if ('(' == c)
                        sig.push(c);

                    else if ('^' == c)
                        sig.push(c);//'^'必然入棧

                    else if ('*' == c || '/' == c) {
                        while (!sig.empty() && '+' != sig.top() && '-' != sig.top() && '(' != sig.top()) {
                            if ('*' == sig.top() || '/' == sig.top()) {
                                cout<< sig.top();
                                sig.pop();
                            }
                            else if ('^' == sig.top()) {
                                while (!sig.empty() && '^' == sig.top()) {//注意這里用while是因?yàn)榭赡苡羞B續(xù)的'^'('^'運(yùn)算順序是從右到左)
                                    cout<< sig.top();
                                    sig.pop();
                                }
                            }
                        }
                        sig.push(c);
                    }

                    else {
                        while (!sig.empty() && '(' != sig.top()) {
                            cout<< sig.top();
                            sig.pop();
                        }
                        sig.push(c);
                    }
                }
            }
        }
    }
    return 0;
}

---

——2023.1.15

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁名稱：4.4.reverse-創(chuàng)新互聯(lián)
網(wǎng)頁URL：http://www.chinadenli.net/article40/gsiho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供建站公司、網(wǎng)站維護(hù)、網(wǎng)站策劃、App設(shè)計(jì)、企業(yè)建站、全網(wǎng)營銷推廣

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)