如图, 如何用递归算法实现将中缀表达式转为后缀表达式,要求用c++编写
递归体现在如果表达式中有括号,将括号中的式子看做一个新的表达式再次调用函数
请在使用递归算法的代码处作出注释
如图, 如何用递归算法实现将中缀表达式转为后缀表达式,要求用c++编写
递归体现在如果表达式中有括号,将括号中的式子看做一个新的表达式再次调用函数
请在使用递归算法的代码处作出注释
#include <iostream>
#include <string>
std::string infixToPostfixRecursive(std::string s, size_t& index) {
std::string result;
bool innerExpression = false; // 用于检测是否我们在处理一个内部表达式(例如,在括号内)
for (; index < s.length(); ++index) {
if (s[index] == ' ') {
continue; // 跳过空格
}
if (isdigit(s[index]) || isalpha(s[index])) { // 如果是数字或字母
result += s[index];
} else if (s[index] == '(') { // 如果遇到左括号,开始递归
innerExpression = true;
++index; // 移动到下一个字符,跳过当前的左括号
result += infixToPostfixRecursive(s, index) + ","; // 添加逗号以区分不同的表达式或数字
} else if (s[index] == ')') { // 如果遇到右括号,结束递归
return result; // 返回当前的结果,不包括当前的右括号
} else { // 对于其他字符,假设它们是运算符
result += s[index];
if (!innerExpression) { // 如果不是内部表达式,则添加逗号
result += ",";
}
innerExpression = false; // 重置内部表达式标志
}
}
return result; // 返回构建的后缀表达式
}
std::string infixToPostfix(std::string s) {
size_t index = 0;
return infixToPostfixRecursive(s, index);
}
int main() {
std::string exp;
std::cout << "中缀表达式: ";
std::getline(std::cin, exp);
std::string postfix = infixToPostfix(exp);
// 删除最终结果中的所有逗号
postfix.erase(std::remove(postfix.begin(), postfix.end(), ','), postfix.end());
std::cout << "后缀表达式: " << postfix << std::endl;
return 0;
}