STL實踐專案之用stack實現計算器（含實現程式碼）

前面章節中，已經對 stack 容器介面卡及其用法做了詳細的講解。本節將利用 stack 介面卡實現一個簡單的計算機程式，此計算機支援基本的加（+）、 減（-）、乘（*）、除（/）、冪（^）運算。

這裡，先給大家展示出完整的實現程式碼，讀者可先自行思考該程式的實現流程。當然，後續也會詳細的講解：

#include <iostream>
#include <cmath>       // pow()
#include <stack>       // stack<T>
#include <algorithm>   // remove()
#include <stdexcept>   // runtime_error
#include <string>      // string
using std::string;

// 返回運算子的優先順序，值越大，優先順序越高
inline size_t precedence(const char op)
{
    if (op == '+' || op == '-')
        return 1;
    if (op == '*' || op == '/')
        return 2;
    if (op == '^')
        return 3;
    throw std::runtime_error{ string {"表達中包含無效的運算子"} +op };
}

// 計算
double execute(std::stack<char>& ops, std::stack<double>& operands)
{
    double result{};
    double rhs{ operands.top() }; // 得到右運算元
    operands.pop();                                   
    double lhs{ operands.top() }; // 得到做運算元
    operands.pop();                                    

    switch (ops.top()) // 根據兩個運算元之間的運算子，執行相應計算
    {
    case '+':
        result = lhs + rhs;
        break;
    case '-':
        result = lhs - rhs;
        break;
    case '*':
        result = lhs * rhs;
        break;
    case '/':
        result = lhs / rhs;
        break;
    case '^':
        result = std::pow(lhs, rhs);
        break;
    default:
        throw std::runtime_error{ string{"invalid operator: "} +ops.top() };
    }
    ops.pop(); //計算完成後，該運算子要彈棧
    operands.push(result);//將新計算出來的結果入棧
    return result;
}

int main()
{
    std::stack<double> operands; //儲存表示式中的運算子
    std::stack<char> operators; //儲存表示式中的數值
    string exp;  //接受使用者輸入的表示式文字
    try
    {
        while (true)
        {
            std::cout << "輸入表示式(按Enter結束):" << std::endl;
            std::getline(std::cin, exp, 'n');
            if (exp.empty()) break;

            //移除使用者輸入表示式中包含的無用的空格
            exp.erase(std::remove(std::begin(exp), std::end(exp), ' '), std::end(exp));

            size_t index{};

            //每個表示式必須以數位開頭,index表示該數位的位數
            operands.push(std::stod(exp, &index)); // 將表示式中第一個數位進棧
            std::cout << index << std::endl;
            while (true)
            {
                operators.push(exp[index++]); // 將運算子進棧

                size_t i{};
                operands.push(std::stod(exp.substr(index), &i));  //將運算子後的數位也進棧,並將數位的位數賦值給 i。
                index += i;  //更新 index

                if (index == exp.length())                  
                {
                    while (!operators.empty())  //如果 operators不為空，表示還沒有計算完
                        execute(operators, operands);
                    break;
                }
                //如果表示式還未遍歷完，但子表示式中的運算子優先順序比其後面的運算子優先順序大，就先計算當前的子表示式的值
                while (!operators.empty() && precedence(exp[index]) <= precedence(operators.top()))
                    execute(operators, operands);
            }
            std::cout << "result = " << operands.top() << std::endl;
        }
    }
    catch (const std::exception& e)
    {
        std::cerr << e.what() << std::endl;
    }
    std::cout << "計算結束" << std::endl;
    return 0;
}

下面是一些範例輸出：

輸入表示式(按Enter結束):
5*2-3
result = 7
輸入表示式(按Enter結束):
4+4*2
result = 12
輸入表示式(按Enter結束):↙   <--鍵入Enter

計算結束

計算器程式的實現流程

了解一個程式的功能，通常是從 main() 函數開始。因此，下面從 main() 函數開始，給大家講解程式的整個實現過程。

首先，我們建立 2 個 stack 介面卡，operands 負責將表示式中的運算子逐個壓棧，operators 負責將表示式的數值逐個壓棧，同時還需要一個 string 型別的 exp，用於接收使用者輸入的表示式。

正如上面程式碼中所有看到的，所有的實現程式碼都包含在一個由 try 程式碼塊包裹著的 while 迴圈中，這樣既可以實現使用者可以多次輸入表示式的功能（當輸入的表示式為一個空字串時，迴圈結束），還可以捕獲程式執行過程中丟擲的任何異常（在 catch 程式碼塊中，呼叫異常物件的成員函數 what() 會將錯誤資訊輸出到標準錯誤流中）。

當使用者輸入完要計算的表示式之後，由於整個表示式是以字串的形式接收的，考慮到字串中可能摻雜空格，影響後續對字串的處理，因此又必須借助 remove() 函數來移除輸入表示式中的多餘空格（第 70 行程式碼處）。

得到統一格式的表示式之後，接下來才是實現計算功能的核心，其實現思路為：
1) 因為所有的運算子都需要兩個運算元，所以有效的輸入表示式格式為“運算元 運算子 運算元 運算子 運算元...”，即序列的第一個和最後一個元素肯定都是運算元，每對運算元之間有一個運算子。由於有效表示式總是以運算元開頭，所以第一個運算元在分析表示式的巢狀迴圈之前被提取出來。

2) 在迴圈中，輸入字串的運算子會被壓入 operators 棧。在確認沒有到達字串末尾後，再從 exp 提取第二個運算元。這時 stod() 的第一個引數是從 index 開始的 exp 字串，它是被壓入 operators 棧的運算子後的所有字元。此時字串中第一個運算子的索引為 i，因為 i 是相對於 index 的，所以我們會將 index 加上 i 的值，使它指向運算元後的一個運算子（如果是 exp 中的最後一個運算元，它會指向字串末尾的下一個位置）。

3) 當 index 的值超過 exp 的最後一個字元時，會執行 operators 容器中剩下的運算子。如果沒有到達字串末尾，operators 容器也不為空，我們會比較 operators 棧頂運算子和 exp 中下一個運算子的優先順序。如果棧頂運算子的優先順序高於下一個運算子，就先執行棧頂的運算子。否則，就不執行棧頂運算子，在下一次迴圈開始時，將下一個運算子壓入 operators 棧。通過這種方式，就可以正確計算出帶優先順序的表示式的值。

以“5-2*3+1”為例，以上程式的計算過程如下：
1) 取  5 和 2 進 operands 棧容器，同時它們之間的 - 運算子進 operators 棧容器，判斷後續是否還有表示式，顯然還有“*3+1”，這種情況下，取 operators 棧頂運算子 - 和後續的 * 運算子做優先順序比較，由於 * 的優先順序更高，此時繼續將後續的 * 和 3 分別進棧；

此時，operands 中從棧頂依次儲存的是 3、2、5，operators 容器中從棧頂依次儲存的是 *、-。

2) 繼續判斷後續是否還有表示式，由於還有“+1”，則取 operators 棧頂運算子 * 和 + 運算子做優先順序比較，顯然前者的優先順序更高，此時將 operands 棧頂的 2 個元素（2 和 3）取出並彈棧，同時將 operators 棧頂元素（*）取出並彈棧，計算它們組成的表示式 2*3，並將計算結果再入 operands 棧。

計算到這裡，operands 中從棧頂依次儲存的是 6、5，operators 中從棧頂依次儲存的是 -。

3) 由於 operator 容器不空，因此繼續取新的棧頂運算子“-”和“+”做優先順序比較，由於它們的優先順序是相同的，因為繼續將 operands 棧頂的 2 個元素（5 和 6）取出並彈棧，同時將 operators 棧頂元素（-） 取出並彈棧，計算它們組成的表示式“5-6”，並將計算結果 -1 再入 operands 棧。

此時，operands 中從棧頂依次儲存的是 -1，operator 為空。

4）由於此時 operator 棧為空，因此將後續“+1”表示式中的 1 和 + 分別進棧。由於後續再無其他表示式，此時就可以直接取 operands 位於棧頂的 2 個元素（-1 和 1），和 operator 的棧頂運算子（+），執行 -1+1 運算，並將計算結果再入 operands 棧。

通過以上幾步，最終“5-2*3+1”的計算結果 0 位於 operands 的棧頂。