C++基礎(chǔ)中綴轉(zhuǎn)后綴表達(dá)式

對(duì)于一個(gè)中綴表達(dá)式 a+b*c*(d-e/f) 轉(zhuǎn)換成后綴是這樣的形式 abc*def/-+
    后綴表達(dá)式是相當(dāng)有用處的,轉(zhuǎn)換成后綴表達(dá)式后求值會(huì)簡(jiǎn)單很多.那么該如何轉(zhuǎn)換呢?
    網(wǎng)上關(guān)于這方面的資料一搜一大把,每本數(shù)據(jù)結(jié)構(gòu)的書(shū)中都會(huì)提及這個(gè)算法,在這個(gè)算法中,用到 棧 這個(gè)數(shù)據(jù)結(jié)構(gòu).
    1,關(guān)鍵是比較運(yùn)算符的優(yōu)先級(jí),誰(shuí)的優(yōu)先級(jí)高,誰(shuí)就出現(xiàn)在前面上面的表達(dá)式中,有括號(hào)的時(shí)候括號(hào)優(yōu)先級(jí),*/次之,+-最后. 在上面的表達(dá)式中+的優(yōu)先級(jí)不如*的高,因此,在后綴表達(dá)式中*出現(xiàn)在+前面,
    2,遇到操作數(shù)的時(shí)候總是直接輸出,不做任何比較
    3,遇到左括號(hào)總是直接入棧,遇到右括號(hào)的時(shí)候總是彈棧,一直彈到遇到一個(gè)左括號(hào)
    4,遇到操作符的時(shí)候就先將這個(gè)操作符和它前面的操作符比較優(yōu)先級(jí),假如高于前面的優(yōu)先級(jí),先將它壓棧,假如低于或等于前面的操作符的優(yōu)先級(jí),就把前面的優(yōu)先級(jí)比它高的或相等的順序彈出來(lái), 一直彈到遇到優(yōu)先級(jí)比它還低的或者到了棧頂
    好了就是上面的幾種情況,然后就可以寫代碼了....
    先規(guī)定一些優(yōu)先級(jí)
    enum{FLAG = -1,
    L_BRCAKET = 0,
    PLUS = 1,MINUS = 1,
    MULTIPLY = 2, DIVISON = 2}; // FLAG為棧頂標(biāo)志,優(yōu)先級(jí)最低
    Examda提示: 分別為左括號(hào),加減乘除的優(yōu)先級(jí)定義,這兒有一個(gè) FLAG = -1.是做什么咧?
    假如分析上面的4點(diǎn)就會(huì)發(fā)現(xiàn),有一些特例,比如第一個(gè)操作符入棧之前要跟前面的操作符比較優(yōu)先級(jí),但是前面還沒(méi)有操作符,就只好當(dāng)做一個(gè)特例特別處理,先判斷是否棧為空,然后操作, 假如我們先將 一個(gè)標(biāo)志符號(hào)壓入棧,并讓它的優(yōu)先級(jí)低于其他所有的操作符的優(yōu)先級(jí),這樣它就永遠(yuǎn)不會(huì)被彈出, 而且消除了特例的判斷,這是技巧
    另外注意,把左括號(hào)的優(yōu)先級(jí)定義的很低,這也是有道理的.因?yàn)槲覀兛偸钱?dāng)遇到右括號(hào)的時(shí)候才把左括號(hào)彈出來(lái)..
    stack opt;
    opt.push('#');
    int len = infix.length();
    for (int i = 0; i < len; i++)
    {
    char ch = infix.at(i);
    if (isalnum(ch))// 數(shù)字直接輸出
    {
    cout<    }
    else // 操作符就判斷并壓棧
    {
    if (ch == '(') // 左括號(hào)直接壓棧
    opt.push(ch);
    else if (ch == ')') // 有括號(hào)就彈棧到直到遇到左括號(hào)
    {
    ch = opt.top(); // 取得棧頂操作符
    while(ch != '(') // 直到彈出左括號(hào)
    {
    cout<    opt.pop();
    ch = opt.top();
    }
    opt.pop(); // 彈出左括號(hào)
    }
    else
    {
    int thisPri = GetPri(ch); // 當(dāng)前操作符優(yōu)先級(jí)
    char prevOpt = opt.top(); // 上一個(gè)操作符
    int prevPri = GetPri(prevOpt); // 上一個(gè)操作符優(yōu)先級(jí)
    while (thisPri <= prevPri)
    { //輸出棧中的操作符直到遇到比當(dāng)前的操作符優(yōu)先級(jí)更低的
    cout<    opt.pop(); // 輸出后就彈出
    prevOpt = opt.top();
    prevPri = GetPri(prevOpt);
    }
    opt.push(ch); //當(dāng)前操作符壓棧
    }
    }
    }
    char ch = opt.top(); // Examda提示: 表達(dá)式掃描完后把棧中剩余的操作符全部輸出
    while (ch != '#')
    {
    cout<    opt.pop();
    ch = opt.top();
    }
    cout<