2. 将表达式转换为逆波兰表示法

任务说明

本案例实现一个中缀表达式到逆波兰表示法（RPN，后缀表达式）的转换器，并对转换结果进行求值验证。输入为包含四则运算、括号和正整数的中缀表达式字符串，输出为对应的RPN序列及最终计算结果。

核心实现

// rpn_converter.h
#ifndef RPN_CONVERTER_H
#define RPN_CONVERTER_H

#include <string>
#include <vector>
#include <stdexcept>

class RPNConverter {
public:
    // 中缀表达式转RPN，返回后缀表达式序列
    static std::vector<std::string> infixToRPN(const std::string& infix);
    
    // 对RPN 序列求值，返回整数结果
    static int evaluateRPN(const std::vector<std::string>& rpn);
    
private:
    static int precedence(char op);
    static bool isOperator(char c);
    static bool isDigit(char c);
};

#endif

// rpn_converter.cpp
#include "rpn_converter.h"
#include <cctype>
#include <sstream>
#include <stack>
#include <cstdlib>

int RPNConverter::precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

bool RPNConverter::isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

bool RPNConverter::isDigit(char c) {
    return c >= '0' && c <= '9';
}

std::vector<std::string> RPNConverter::infixToRPN(const std::string& infix) {
    std::vector<std::string> output;
    std::stack<char> opStack;
    
    for (size_t i = 0; i < infix.length(); ++i) {
        char c = infix[i];
        
        if (isspace(c)) continue;
        
        // 解析多位数字
        if (isDigit(c)) {
            std::string num;
            while (i < infix.length() && isDigit(infix[i])) {
                num += infix[i];
                ++i;
            }
            --i; // 回退一位，外层循环会自增
            output.push_back(num);
        }
        else if (c == '(') {
            opStack.push(c);
        }
        else if (c == ')') {
            while (!opStack.empty() && opStack.top() != '(') {
                output.push_back(std::string(1, opStack.top()));
                opStack.pop();
            }
            if (opStack.empty()) {
                throw std::runtime_error("括号不匹配");
            }
            opStack.pop(); // 弹出 '('
        }
        else if (isOperator(c)) {
            while (!opStack.empty() && opStack.top() != '(' &&
                   precedence(opStack.top()) >= precedence(c)) {
                output.push_back(std::string(1, opStack.top()));
                opStack.pop();
            }
            opStack.push(c);
        }
        else {
            throw std::runtime_error("非法字符");
        }
    }
    
    while (!opStack.empty()) {
        if (opStack.top() == '(') {
            throw std::runtime_error("括号不匹配");
        }
        output.push_back(std::string(1, opStack.top()));
        opStack.pop();
    }
    
    return output;
}

int RPNConverter::evaluateRPN(const std::vector<std::string>& rpn) {
    std::stack<int> evalStack;
    
    for (const auto&  : rpn) {
        if (isDigit([0])) {
            evalStack.push(std::atoi(.c_str()));
        }
        else if (isOperator([0])) {
            if (evalStack.size() < 2) {
                throw std::runtime_error("表达式错误");
            }
            int b = evalStack.top(); evalStack.pop();
            int a = evalStack.top(); evalStack.pop();
            
            switch ([0]) {
                case '+': evalStack.push(a + b); break;
                case '-': evalStack.push(a - b); break;
                case '*': evalStack.push(a * b); break;
                case '/': 
                    if (b == 0) throw std::runtime_error("除零错误");
                    evalStack.push(a / b); break;
            }
        }
    }
    
    if (evalStack.size() != 1) {
        throw std::runtime_error("表达式错误");
    }
    return evalStack.top();
}

// main.cpp
#include "rpn_converter.h"
#include <iostream>

int main() {
    // 测试用例
    std::vector<std::string> testCases = {
        "3+4*2",
        "(1+2)*3",
        "10-2*3+5",
        "2*(3+4)-5/1"
    };
    
    for (const auto& expr : testCases) {
        try {
            auto rpn = RPNConverter::infixToRPN(expr);
            
            std::cout << "中缀: " << expr << std::endl;
            std::cout << "RPN:  ";
            for (const auto&  : rpn) {
                std::cout <<  << " ";
            }
            std::cout << std::endl;
            
            int result = RPNConverter::evaluateRPN(rpn);
            std::cout << "结果: " << result << std::endl;
            std::cout << "------------------------" << std::endl;
        }
        catch (const std::exception& e) {
            std::cerr << "表达式 [" << expr << "] 错误: " << e.what() << std::endl;
        }
    }
    
    return 0;
}

编译与运行

g++ -std=c++11 -o rpn_demo main.cpp rpn_converter.cpp
./rpn_demo

预期输出

中缀: 3+4*2
RPN:  3 4 2 * +
结果: 11
------------------------
中缀: (1+2)*3
RPN:  1 2 + 3 *
结果: 9
------------------------
中缀: 10-2*3+5
RPN:  10 2 3 * - 5 +
结果: 9
------------------------
中缀: 2*(3+4)-5/1
RPN:  2 3 4 + * 5 1 / -
结果: 9
------------------------

算法说明

转换采用调度场算法：扫描中缀表达式，数字直接输出；运算符与栈顶比较优先级，栈顶优先级不低于当前运算符时弹出；左括号入栈，右括号弹出至左括号。求值阶段使用栈：数字入栈，遇运算符弹出两个操作数计算后压回。

验证要点

• 测试用例覆盖了运算符优先级（3+4*2）、括号改变优先级（(1+2)*3）、多位数解析（10）和混合运算（2*(3+4)-5/1）
• 每个用例的RPN序列符合后缀表达式定义，求值结果与手工计算一致
• 错误处理：括号不匹配、非法字符、除零均会抛出异常并打印错误信息