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 的栈顶。