问题 M: 中缀表达式转后缀表达式

题目描述

      输入一个中缀表达式，编程输出其后缀表达式，要求输出的后缀表达式的运算次序与输入的中缀表达式的运算次序相一致。为简单起见，假设输入的中缀表达式由＋（加）、－（减）、×（乘）、／（除）四个运算符号以及左右圆括号和英文字母组成，其中算术运算符遵守先乘除后加减的运算规则。假设输入的中缀表达式长度不超过300个字符，且都是正确的，即没有语法错误，并且凡出现括号其内部一定有表达式，即内部至少有一个运算符号。

中缀表达式转后缀表达式的方法：
1.遇到操作数：直接输出（添加到后缀表达式中）
2.栈为空时，遇到运算符，直接入栈
3.遇到左括号：将其入栈
4.遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，括号不输出。
5.遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈
6.最终将栈中的元素依次出栈，输出。

输入

只有一行，为中缀表达式

输出

只有一行，为转换后的后缀表达式

样例输入 Copy

X+A*(Y-B)-Z/F

样例输出 Copy

XAYB-*+ZF/-

参考代码：

#include <iostream>
#include <stack>
#include <string>

// 获取运算符的优先级
int getPriority(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

// 将中缀表达式转换为后缀表达式
std::string infixToPostfix(const std::string& infix) {
    std::stack<char> stack;
    std::string postfix;

    for (char ch : infix) {
        if (isalpha(ch)) {
            // 1. 遇到操作数：直接输出
            postfix += ch;
        }
        else if (ch == '(') {
            // 2. 遇到左括号：将其入栈
            stack.push(ch);
        }
        else if (ch == ')') {
            // 3. 遇到右括号：执行出栈操作，直到弹出左括号
            while (!stack.empty() && stack.top() != '(') {
                postfix += stack.top();
                stack.pop();
            }
            stack.pop(); // 弹出左括号
        }
        else {
            // 4. 遇到运算符：弹出优先级大于或等于该运算符的栈顶元素，然后将该运算符入栈
            while (!stack.empty() && getPriority(stack.top()) >= getPriority(ch)) {
                postfix += stack.top();
                stack.pop();
            }
            stack.push(ch);
        }
    }

    // 5. 最终将栈中的元素依次出栈，输出
    while (!stack.empty()) {
        postfix += stack.top();
        stack.pop();
    }

    return postfix;
}

int main() {
    std::string infix;
    std::cin >> infix;

    std::string postfix = infixToPostfix(infix);
    std::cout << postfix << std::endl;

    return 0;
}

本题就是把运算符与操作符进行互换，与问题 L: 后缀表达式求值问题不同的是将操作符加入栈中，然后根据题意进行操作。

祝各位逸夫楼坐牢顺利