表达式转换：中缀转后缀和前缀

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

std::vector<std::string> infixToPostfix(const std::string& infix) {
    std::stack<char> operators;
    std::vector<std::string> output;

    for (size_t i = 0; i < infix.length(); ++i) {
        char token = infix[i];

        if (isdigit(token)) {
            std::string number;
            while (i < infix.length() && isdigit(infix[i])) {
                number += infix[i++];
            }
            --i;
            output.push_back(number); // 数字输出
        } else if (token == '(') {
            operators.push(token);  // 左括号入栈(
        } else if (token == ')') {
            // 右括号弹出操作符并输出，直到遇到左括号位为止
            while (!operators.empty() && operators.top() != '(') {
                output.push_back(std::string(1, operators.top()));
                operators.pop();
            }
            operators.pop(); // Pop the '('
        } else if (token == '+' || token == '-' || token == '*' || token == '/') {
            // 栈顶优先级 >= 当前操作符，先弹出栈顶并输出，之后入栈。
            // 栈顶优先级 < 当前操作符，入栈
            while (!operators.empty() && precedence(operators.top()) >= precedence(token)) {
                output.push_back(std::string(1, operators.top()));
                operators.pop();
            }
            operators.push(token);
        }
    }
	// 将栈中所有操作符输出，即为后缀表达式
    while (!operators.empty()) {
        output.push_back(std::string(1, operators.top()));
        operators.pop();
    }

    return output;
}

int evalRPN(vector<string>& tokens) {
    // 逆波兰表示法就是符号放在右边
    stack<int> s;
    for (auto& token : tokens) {
        if (token == "+" || token == "-" || token == "*" || token == "/") {
            int r = s.top(); //右操作数
            s.pop();
            int l = s.top();
            s.pop();
            if (token == "+") s.push(l + r);
            else if (token == "-") s.push(l - r);
            else if (token == "*") s.push(l * r);
            else if (token == "/") s.push(l / r);
        } else {
            s.push(atoi(token.c_str()));
        }
    }
    return s.top();
}

// 中缀转前缀
vector<string> intopre(string s) {
    // 准备两个栈
    stack<string> symbol, num;
    vector<string> res;  // 后缀表达式
    for (int i = s.size() - 1; i >= 0; i--) {
        char ch = s[i];
        if (isdigit(ch)) { // 是数字入数字栈
            string number;
            while (i >= 0 && isdigit(s[i])) {
                number += s[i--];
            }
            reverse(number.begin(), number.end());
            num.push(number);
            i++;
        } else if (ch == ')') {
            symbol.push(string(1, ch));
        } else if (ch == '(') {
            // 左括号，符号栈弹栈, 出栈元素依次进入数字栈, 同时舍弃)
            while (!symbol.empty() && symbol.top() != ")") {
                num.push(symbol.top());
                symbol.pop();
            }
            symbol.pop();
        } else if (ch == '*' || ch == '/' ||  ch == '+' || ch == '-') {
            // 符号栈栈顶大于>当前运算符，栈顶出栈入数字栈，直到栈顶为)或者优先级小于当前
            // 可以看作)优先级最低
            while (!symbol.empty() && precedence(symbol.top()) > precedence(string(1, ch))) {
                num.push(symbol.top());
                symbol.pop();
            }
            // 符号栈栈顶小于等于<=当前运算符，入栈
            symbol.push(string(1, ch));
        }  
    }
    // 将符号栈中剩余运算符依次弹出并压入数字栈
    while (!symbol.empty()) {
        num.push(symbol.top());
        symbol.pop();
    }
    // 依次弹出数字栈即为前缀表达式
    while (!num.empty()) {
        res.push_back(num.top());
        num.pop();
    }
    return res;
}