后缀表达式也叫逆波兰表达式，它的特点是运算符放在操作数的后面，不需要括号就能明确运算的优先级，比如中缀表达式3 + 4 * 2对应的后缀表达式是3 4 2 * +。用c++的栈结构实现后缀表达式求值，核心是利用栈的后进先出的特性处理运算过程。
实现原理
后缀表达式的求值逻辑非常清晰，整体遍历表达式的每个元素，按照以下规则处理：
- 如果当前元素是操作数，直接将其压入栈中
- 如果当前元素是运算符，从栈中弹出两个操作数，注意先弹出的是右操作数，后弹出的是左操作数，按照运算符进行计算，再将计算结果压回栈中
- 遍历完所有元素后，栈中仅剩的一个元素就是整个表达式的计算结果
代码实现步骤
1. 准备依赖和辅助函数
首先需要引入栈相关的头文件，同时写一个判断当前字符串是否为运算符的辅助函数，方便后续处理。
#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include <sstream>
// 判断是否为运算符
bool isOperator(const std::string& s) {
return s == "+" || s == "-" || s == "*" || s == "/";
}
2. 实现核心求值函数
核心函数接收拆分好的后缀表达式元素数组，按照上述原理完成计算，注意除法操作需要处理除数为0的情况。
double calculateRPN(const std::vector<std::string>& tokens) {
std::stack<double> numStack;
for (const std::string& token : tokens) {
if (isOperator(token)) {
// 弹出两个操作数，注意先弹出的是右操作数
double right = numStack.top();
numStack.pop();
double left = numStack.top();
numStack.pop();
double result = 0;
if (token == "+") {
result = left + right;
} else if (token == "-") {
result = left - right;
} else if (token == "*") {
result = left * right;
} else if (token == "/") {
// 简单处理除数为0的情况
if (right == 0) {
std::cout << "除数不能为0" << std::endl;
return 0;
}
result = left / right;
}
numStack.push(result);
} else {
// 是操作数，转换为double后入栈
numStack.push(std::stod(token));
}
}
return numStack.top();
}
3. 测试代码
写一个测试函数，拆分后缀表达式字符串并调用求值函数，验证结果是否正确。
int main() {
// 后缀表达式：3 4 2 * + 对应中缀表达式 3 + 4 * 2
std::string rpnStr = "3 4 2 * +";
std::vector<std::string> tokens;
std::stringstream ss(rpnStr);
std::string token;
while (ss >> token) {
tokens.push_back(token);
}
double result = calculateRPN(tokens);
std::cout << "后缀表达式 " << rpnStr << " 的计算结果是：" << result << std::endl;
return 0;
}
注意事项
实际使用时需要注意几个问题：
- 操作数的类型可以根据需求调整，如果是整数运算可以把栈的类型改成
int，用stoi转换字符串 - 如果后缀表达式中存在多位数或者小数，上述代码已经支持，因为
stod可以处理这两种情况 - 输入的字符串需要正确拆分，元素之间用空格分隔，否则需要额外处理拆分逻辑
- 如果表达式不合法，比如栈中操作数不足就遇到运算符，代码会出现运行时错误，实际项目中可以加额外的校验逻辑