[C++] Infix to Postfix Conversion

貼上我在Object Oriented C++做的project：要把四則運算式從infix轉換成postfix。教授有意識到這跟之前的兩個project難度相差太大，上週已經說過如果大部分同學做不出來，可以再延長一週。我尋思如果再拖下去都要期末考了，所以拼著這週就盡力趕出成果。

using namespace std;
int main()
{
    cout << "Please enter an valid infix expression: " << endl;
    string infix;
    getline(cin, infix);
 
    cout << infix << " is converted to " << infixToPostfix(infix, infix.length()) << endl;
 
    system("pause");
    return 0;
}

1. 以上main function，getline是參考別人的程式做的，原本沒學過（或是沒注意）。
2. header有iostream、stack和string，blogger顯示不出來就乾脆刪掉了。
3. 最後的 system("pause") 好像是Dev-C++限定？ XD

// ---------------------------------------
// distinguish the priorities of operators
// ---------------------------------------
bool priorityOf(string const theOperator, string const currentExpression)
{
    string operators = "*/+-(";
    int priority[] = {2,2,1,1,0};
    int loc = operators.find(theOperator);
    int loc2 = operators.find(currentExpression);
    return (priority[loc] >= priority[loc2]);
}

1. 教授提供，用兩個array辨識運算符號的優先順序。教授原本寫的是回傳int，我實際應用後把它修改成直接比較並回傳boolean
2. find的功能是新知。我在摸索這個project中，真的學了很多。
3. 因為project本身只要求做簡單的四則運算轉換，所以我google到的code有的用上次方(^)或餘數(%)，我沒加進去。要加的話應該是這樣吧：次方的優先值是3、餘數是2。
4. 我對const的概念還是很模糊，只停留在「如果加了才不會有錯誤訊息就加上去吧」的程度...

// ------------------------------------
// the conversion from infix to postfix
// ------------------------------------
string infixToPostfix(string infix, int currentIndex)
{
    stack operandStk; // stack to place operands
    stack operatorStk;// stack to place operators & compare priority
    for (int i = 0; i < currentIndex; i++)
    {
        string currentExpression;
        currentExpression = infix[i];
     
        // point a
        if (currentExpression == " ")
        {
            continue;
        }
        // point a.5
        else if (currentExpression == "(")
        {
            operatorStk.push(currentExpression);
        }

1. 來真格的(?)，我原本打算抄google到的code（有些同學這麼做）或用書上的四則運算式來修改，但試了一陣子發現，拼出個可以用卻完全不懂原理的程式感覺很虛。←其實是根本拼不出來因為不懂原理
2. 所以整個檔案的code，每個字都是我的心血啊啊
3. 整體來說我最後大概刪了四分之一的行數，都是用來debug的...現在還看得到的 //point a這種註記是我覺得還可以留著用的checkpoints。
4. 進到function後，首先定義了兩個string stack，一個放operand如abcde、一個放運算符號operator。
5. 接下來進到主要的for迴圈，loop的次數從main function抓cin的string infix.length()。
6. 第一個if，遇到space就略過。
7. else if，遇到前括號 "(" 直接推進operator stack。

        // point b
        else if (operandStk.empty() && operatorStk.empty())
        {
           // point b-1
           if (currentExpression != "+" && "-" && "*" && "/")
           {
               operandStk.push(currentExpression);
           }
           // point b-2
           else // if (currentExpression == "+" || "-" || "*" || "/")
           {
               cout << "This is not an valid expression." << endl;
               break;
           }
        }

1. 第二個else if，如果兩個stack都空空如也（代表丟進來的是第一個值），要怎麼做。
2. 如果不是運算符號，就假定是運算元。這裡的statement其實我知道有些不完整，但暫時還合用。
3. 如果一開始是運算符號，表示infix運算式本身不合邏輯，cout錯誤訊息。

        // point c
        else // assume the expression has started
        {
            // point c-1
            if (currentExpression == "+" || currentExpression == "-"
             || currentExpression == "*" || currentExpression == "/") // if is operator

1. 最外層的if statement的尾巴，也是最長的。首先是第二層if statement，先看丟進來的expression是不是operator。
2. 這邊我搞錯一個點，讓第二個以降的運算元都跑進operator stack。我把statement寫成if (currentExpression == "+" || "-" || "*" || "/")，想說這樣比較簡潔結果...

            {
                // point c-1-1
                if (operatorStk.empty())
                {
                    operatorStk.push(currentExpression);
                }
                // point c-1-2
                else // to decide base on the priority
                {
                    // point c-1-2-1
                    // if current expression is smaller, then combine the prior stacks
                    if (priorityOf(operatorStk.top(), currentExpression))
                    {
                        string s;
                        s.append(operandStk.top()); // append the operand top
                        operandStk.pop();
                        // point c-1-2-1-1
                        while (priorityOf(operatorStk.top(), currentExpression)
                            && !operatorStk.empty() && operatorStk.top() != "(")
                        {
                            s.append(operatorStk.top()); // append the operator top
                            operatorStk.pop();
                            if (operatorStk.empty()) break;
                            else continue;
                        }
                        operandStk.push(s);
                        operatorStk.push(currentExpression); // the last thing to do
                    }
                    // point c-1-2-2
                    else // if operatorStk.top() is smaller than current infix expression
                    {
                        operatorStk.push(currentExpression);
                    }
                }
            }

1. 第三層和第四層if statement...幸好排版不算難懂不然我一定會哪裡多一個或少一個 "}"，真要命寫到眼睛快凸出來 XD
2. 後來還是都標上記號debug後才比較容易懂我到底幹了什麼...
3. 首先，如果operator stack沒東西，就把新的operator推進去。
4. 如果已經有operator了，就要比較優先值。
5. 如果既有的operator比新來的大或相等（例："*" 大於 "+"），就把已有的operator附到operand裡。這個步驟還要再重複，把stack裡面大於新operator的都append到operand上，不然最後結果有誤。
6. 我在這裡一直卡到runtime error，因為沒有先檢查stack是否還有剩東西就一股腦的top()、pop()，我花了好久在這裡除錯最後才發現要加個 if 檢查（這是第幾層了...我在Inception嗎？）。
7. 搞出runtime error真的是我的強項（驕傲）。
8. 最後，如果新來的優先值較大，推進stack。

            // point c-2
            else if (currentExpression == ")")
            {
                string s;
                s.append(operandStk.top());
                operandStk.pop();
                while (operatorStk.top() != "(")
                {
                    s.append(operatorStk.top());
                    operatorStk.pop();
                }
                operatorStk.pop(); // delete "(" in stack
                operandStk.push(s);
            }
            // point c-3
            else // if is operand
            {
                // point c-3-1
                if (operatorStk.empty())
                {
                    cout << "This is not an valid expression." << endl;
                    break;
                }
                // point c-3-2
                else
                {
                    string s;
                    s = operandStk.top();
                    s.append(currentExpression);
                    operandStk.pop();
                    operandStk.push(s);
                }
            }
        }
    }

1. for迴圈的尾巴。進來的值如果是 ")"，把 "(" 之後的operator都append到operand上，並刪掉 "("。
2. 最後的 if 我不記得是在幹嘛了。果然註記還是要寫清楚點。

    string Postfix;
 
        if (!operandStk.empty())
        {
           Postfix = operandStk.top();
           operandStk.pop();
        }
        while (!operatorStk.empty())
        {
           Postfix.append(operatorStk.top());
           operatorStk.pop();
        }
 
    return Postfix;
}

1. 在for之後，所有的值都被妥當的(?)擺在該擺的stack裡。 
2. 我的設計是可以接在一起的符號和運算元都先合併了，所以operand stack只有一個整合的值。先用 if 判斷stack有沒有東西，再把operand提到string Postfix。這裡我是更早前一直遇到runtime error在debug。可見我多麼學不會教訓（驕傲）。
3. 把operator stack從最上層依序append到string Postfix。大功告成。
4. 我有幾次把string打成spring，看到除錯訊息還搞不懂哪裡有問題 XD

這個project花了一個多禮拜構思，加上三個全天火力全開的coding，能做出堪用的成果真的很開心，不過同時間的Macroeconomics quiz因此半放棄了，有點小可惜 XDrz

註：經過教授的簡單測試（只是丟幾個式子進去看結果對不對），沒什麼大問題。所以先貼出來滿足我小小的成就感 ^__^