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

本文标题:STL实践项目之用stack实现计算器(含实现代码)

本文地址:https://www.hosteonscn.com/7674.html

评论

0条评论

发表评论

邮箱地址不会被公开。 必填项已用*标注