递归实现中缀表达式转换成后缀表达式

Question

如图， 如何用递归算法实现将中缀表达式转为后缀表达式，要求用c++编写
递归体现在如果表达式中有括号，将括号中的式子看做一个新的表达式再次调用函数

请在使用递归算法的代码处作出注释

Answer 1

基于Monster 组和GPT的调写：

#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;
}