QT之計算器核心解析算法（十）

    上節我們說到計算機默認的是后綴表達式，那么中綴表達式轉后綴表達式的過程就類似于編譯過程。

必須得注意這么幾個問題：四則運算表達式中的括號必須匹配；根據運算符優先級進行轉換；轉換后的表達式中沒有括號；轉換后可以順序計算出最終結果。
下來我們就講下具體的轉換過程：
1、當前元素 e 為數字：輸出
2、當前元素 e 為運算符時：1. 與棧頂運算符進行優先級比較；2.小于等于時將棧頂元素輸出，轉1；3.大于時將當前元素 e 入棧
3、當前元素 e 為左括號：入棧
4、當前元素 e 為右括號：1.彈出棧頂元素并輸出，直至棧頂元素為左括號；2.將棧頂的左括號從棧中彈出
用偽代碼描述出來就是這樣：

其中的關鍵點是轉換過程中左右括號是重要的標志，那么如何確保表達式中的括號能夠左右匹配？
那么在合法的四則運算表達式中：括號必然是成對出現的，左括號必然先于右括號出現，可以用偽代碼進行描述：

經過這樣，我們就可以確保計算機正確的將中綴表達式轉換成后綴表達式，也就是將表達式轉換為計算機理解的行為。
那么這是計算機所轉換的三個示例：

下來我們構建運行下程序看看輸出是否正確執行，我們在構造函數這樣輸入：

輸出結果如下：

匹配函數的具體代碼如下：
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();
        }

     轉換函數的具體代碼如下：
     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;
    }

那么今天的學習就到這了，現在程序已經能按照計算機的思維進行四則運算的讀取了，后面我們繼續學習相關知識。