PTA（栈和队列）2-1 表达式转换

2-1 表达式转换

分数 5

作者 DS课程组

单位 浙江大学

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。

输入格式:

输入在一行中给出不含空格的中缀表达式，可包含+、-、*、/以及左右括号()，表达式不超过20个字符。

输出格式:

在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。

输入样例:

1
2+3*(7-4)+8/4

输出样例:

1
2 3 7 4 - * + 8 4 / +

  • 初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。从左到右处理各个元素，直到末尾。可能遇到三种情况:

    • 遇到==操作数==: 直接加入后缀表达式。
    • 遇到==界限符==: 遇到 ‘(’ 直接入栈; 遇到 ‘)’ 则依次弹出栈内运算符并加入后缀表达式，直到弹出 ‘(’ 为止。注意: ‘(‘ 不加入后缀表达式。
    • 遇到==运算符==: 依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到 ‘(’ 或栈空则停止。之后再把当前运算符入栈。（栈顶与读的pk，读的狠些就压栈顶，不很就出来）

  • 按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

部分正确答案

测试点 提示 内存(KB) 用时(ms) 结果 得分
0 312 5 答案正确 1 / 1
1 460 5 答案正确 1 / 1
2 448 5 答案错误 0 / 1
3 316 5 答案错误 0 / 1
4 316 5 答案正确 1 / 1

注意要处理有多位数的情况，因为每次只读取一个字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <stack>
#include <string>   
#include <cctype>

using namespace std;

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

int main() {
    string expression; // 存放表达式
    cin >> expression;
    stack<char> OPTR; // 用于存放操作数
    bool isFirst = true; // 用于输出第一个字符前无空格

    for (int i = 0; i < expression.length(); i++) { // 这样就能处理有两位数字的情况了
        char c = expression[i];
        if (isdigit(c)) {
            if (!isFirst) {
                cout << " ";
            }
            // 输出完整的数字
            while (i < expression.length() && isdigit(expression[i])) {
                cout << expression[i];
                i++;
            }
            i--; // 回退一个位置，因为for循环会再i++
            isFirst = false;
        }  else if (c == '(') { // 如果是（就直接入栈
            OPTR.push(c);
        } else if (c == ')') { // 如果是）弹出栈中元素至遇到（
            while (OPTR.top() != '(') { // 将（之前的全输出
                if (!isFirst) {
                    cout << " ";
                }
                cout << OPTR.top();
                OPTR.pop();
                isFirst = false;
            }
            // 最后将（出栈
            OPTR.pop();
        } else { // 如果是其他运算符号，先比较优先级，看是输出还是入栈
            // 栈顶的优先级大于等于读取的就一直出栈
            while (!OPTR.empty() && OPTR.top() != '(' && getPriority(OPTR.top()) >= getPriority(c)) {
                if (!isFirst) { // 如果一开始就遇到（，开头不能有空格
                    cout << " ";
                }
                cout << OPTR.top(); // 先输出
                OPTR.pop(); // 再出栈
                isFirst = false;
            }
            OPTR.push(c); // 优先级大的出栈出完了，读取的入栈
        }
    }

    // 将栈中剩余的出栈
    while (!OPTR.empty()) {
        if (!isFirst) {
            cout << " ";
        }
        cout << OPTR.top();
        OPTR.pop();
        isFirst = false;
    }
}

中缀表达式转后缀表达式 核心步骤

  1. 初始化一个操作符栈（用于存储 +、-、*、/、( 等运算符）。

  2. 从左到右扫描中缀表达式的每个字符。

  3. 如果遇到操作数（数字，支持多位数），则直接输出。

  4. 如果遇到左括号 (，则直接压入操作符栈。

  5. 如果遇到右括号 )，则不断将栈顶元素弹出并输出，直到遇到左括号 (；左括号弹出但不输出。

  6. 如果遇到运算符+、-、*、/，则按以下规则处理：

    a. 当操作符栈为空时，直接将当前运算符压入栈。

    b. 当操作符栈不为空时，比较当前运算符与栈顶运算符的优先级：

    • 若当前运算符的优先级 高于 栈顶运算符，将当前运算符压入栈。
    • 若当前运算符的优先级 低于或等于 栈顶运算符，不断弹出栈顶运算符并输出，直到栈顶运算符优先级低于当前运算符或栈为空，再将当前运算符压入栈。

  7. 当表达式扫描完毕，将操作符栈中剩余的所有运算符依次弹出并输出。