QT之計(jì)算器核心解析算法（十）

    上節(jié)我們說(shuō)到計(jì)算機(jī)默認(rèn)的是后綴表達(dá)式，那么中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式的過(guò)程就類似于編譯過(guò)程。

必須得注意這么幾個(gè)問(wèn)題：四則運(yùn)算表達(dá)式中的括號(hào)必須匹配；根據(jù)運(yùn)算符優(yōu)先級(jí)進(jìn)行轉(zhuǎn)換；轉(zhuǎn)換后的表達(dá)式中沒(méi)有括號(hào)；轉(zhuǎn)換后可以順序計(jì)算出最終結(jié)果。
下來(lái)我們就講下具體的轉(zhuǎn)換過(guò)程：
1、當(dāng)前元素 e 為數(shù)字：輸出
2、當(dāng)前元素 e 為運(yùn)算符時(shí)：1. 與棧頂運(yùn)算符進(jìn)行優(yōu)先級(jí)比較；2.小于等于時(shí)將棧頂元素輸出，轉(zhuǎn)1；3.大于時(shí)將當(dāng)前元素 e 入棧
3、當(dāng)前元素 e 為左括號(hào)：入棧
4、當(dāng)前元素 e 為右括號(hào)：1.彈出棧頂元素并輸出，直至棧頂元素為左括號(hào)；2.將棧頂?shù)淖罄ㄌ?hào)從棧中彈出
用偽代碼描述出來(lái)就是這樣：

其中的關(guān)鍵點(diǎn)是轉(zhuǎn)換過(guò)程中左右括號(hào)是重要的標(biāo)志，那么如何確保表達(dá)式中的括號(hào)能夠左右匹配？
那么在合法的四則運(yùn)算表達(dá)式中：括號(hào)必然是成對(duì)出現(xiàn)的，左括號(hào)必然先于右括號(hào)出現(xiàn)，可以用偽代碼進(jìn)行描述：

經(jīng)過(guò)這樣，我們就可以確保計(jì)算機(jī)正確的將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式，也就是將表達(dá)式轉(zhuǎn)換為計(jì)算機(jī)理解的行為。
那么這是計(jì)算機(jī)所轉(zhuǎn)換的三個(gè)示例：

下來(lái)我們構(gòu)建運(yùn)行下程序看看輸出是否正確執(zhí)行，我們?cè)跇?gòu)造函數(shù)這樣輸入：

輸出結(jié)果如下：

匹配函數(shù)的具體代碼如下：
bool QCalculatorDec::match(QQueue<QString>& exp)
{
bool ret = true;
int len = exp.length();
QStack<QString> stack;

                for(int i=0; i<len; i++)
                {
                        if( isLeft(exp[i]) )
                        {
                                stack.push(exp[i]);
                        }
                        else if( isRight(exp[i]) )
                        {
                                if( !stack.isEmpty() && isLeft(stack.top()) )
                                {
                                        stack.pop();
                                }
                                else
                                {
                                        ret = false;
                                        break;
                                }
                        }
                }

                return ret && stack.isEmpty();
        }

     轉(zhuǎn)換函數(shù)的具體代碼如下：
     bool QCalculatorDec::transform(QQueue<QString>& exp, QQueue<QString>& output)
    {
            bool ret = match(exp);
            QStack<QString> stack;

            output.clear();

            while( ret && !exp.isEmpty() )
            {
                    QString e = exp.dequeue();

                    if( isNumber(e) )
                    {
                            output.enqueue(e);
                    }
                    else if ( isOperator(e) )
                    {
                            while( !stack.isEmpty() && (priority(e) <= priority(stack.top())) )
                            {
                                    output.enqueue(stack.pop());
                            }

                            stack.push(e);
                    }
                    else if( isLeft(e) )
                    {
                            stack.push(e);
                    }
                    else if( isRight(e) )
                    {
                            while( !stack.isEmpty() && !isLeft(stack.top()) )
                            {
                                    output.enqueue(stack.pop());
                            }

                            if( !stack.isEmpty() )
                            {
                                    stack.pop();
                            }
                    }
                    else
                    {
                            ret = false;
                    }
            }

            while( !stack.isEmpty() )
            {
                    output.enqueue(stack.pop());
            }

            if( !ret )
            {
                    output.clear();
            }

            return ret;
    }

那么今天的學(xué)習(xí)就到這了，現(xiàn)在程序已經(jīng)能按照計(jì)算機(jī)的思維進(jìn)行四則運(yùn)算的讀取了，后面我們繼續(xù)學(xué)習(xí)相關(guān)知識(shí)。