简介
利用 stack 适配器实现一个简单的计算机程序，此计算机支持基本的加（+）、 减（-）、乘（*）、除（/）、幂（^）运算。
code
#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;
}
计算器程序的实现流程
了解一个程序的功能，通常是从 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”为例，以上程序的计算过程如下：
- 取 5 和 2 进 operands 栈容器，同时它们之间的 - 运算符进 operators 栈容器，判断后续是否还有表达式，显然还有“*3+1”，这种情况下，取 operators 栈顶运算符 - 和后续的 * 运算符做优先级比较，由于 * 的优先级更高，此时继续将后续的 * 和 3 分别进栈；
此时，operands 中从栈顶依次存储的是 3、2、5，operators 容器中从栈顶依次存储的是 *、-。
- 继续判断后续是否还有表达式，由于还有“+1”，则取 operators 栈顶运算符 * 和 + 运算符做优先级比较，显然前者的优先级更高，此时将 operands 栈顶的 2 个元素（2 和 3）取出并弹栈，同时将 operators 栈顶元素（*）取出并弹栈，计算它们组成的表达式 2*3，并将计算结果再入 operands 栈。
计算到这里，operands 中从栈顶依次存储的是 6、5，operators 中从栈顶依次存储的是 -。
- 由于 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 的栈顶。