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; //接受用户输入的表达式文本

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

23733.html

gohtml