表达式的转换

GitHub 跳转原题关系图返回列表

用运算符栈把中缀表达式转成后缀表达式，再按最左可归约位置模拟每一步计算过程。

OJ: luogu

题目 ID: P1175

难度:普及/提高-

标签:栈字符串模拟模板题

日期: 2025-12-31 12:15

题意

给定一个中缀表达式，先把它转换成后缀表达式并输出。
然后继续在这个后缀表达式上做“演示式计算”：

每次都找当前序列里最靠左的运算符；
用它前面的两个数字计算出结果；
再用这个结果替换掉这三个位置；
每做完一步就把当前序列输出出来。

题目的难点不在算值本身，而在于两件事：

中缀转后缀时要正确处理优先级、括号和 $^$ 的右结合。
输出过程时不能只保留一个求值栈，而要真的维护“当前后缀序列”。

思路

先看一个更直观的教学版写法：先递归下降建语法树，再做后序遍历得到后缀表达式。

cpp

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172#include <bits/stdc++.h>
using namespace std;

struct Token {
    int type; // 0 表示数字，1 表示运算符
    long long value;
    char op;
};

struct Node {
    int type; // 0 表示数字，1 表示运算符
    long long value;
    char op;
    int left_son;
    int right_son;
};

string expr;
int pos = 0;
Node tree_nodes[505];
int node_cnt = 0;
vector<Token> postfix_tokens;

int new_number_node(long long value) {
    ++node_cnt;
    tree_nodes[node_cnt].type = 0;
    tree_nodes[node_cnt].value = value;
    tree_nodes[node_cnt].op = 0;
    tree_nodes[node_cnt].left_son = 0;
    tree_nodes[node_cnt].right_son = 0;
    return node_cnt;
}

int new_operator_node(char op, int left_son, int right_son) {
    ++node_cnt;
    tree_nodes[node_cnt].type = 1;
    tree_nodes[node_cnt].value = 0;
    tree_nodes[node_cnt].op = op;
    tree_nodes[node_cnt].left_son = left_son;
    tree_nodes[node_cnt].right_son = right_son;
    return node_cnt;
}

long long quick_pow(long long a, long long b) {
    long long ans = 1;
    while (b > 0) {
        if (b & 1) ans *= a;
        a *= a;
        b >>= 1;
    }
    return ans;
}

long long calc(long long a, long long b, char op) {
    if (op == '+') return a + b;
    if (op == '-') return a - b;
    if (op == '*') return a * b;
    if (op == '/') return a / b;
    return quick_pow(a, b);
}

int parse_expression();

int parse_primary() {
    if (expr[pos] == '(') {
        ++pos;
        int root = parse_expression();
        ++pos; // 跳过右括号
        return root;
    }

    long long value = 0;
    while (pos < static_cast<int>(expr.size()) && isdigit(expr[pos])) {
        value = value * 10 + (expr[pos] - '0');
        ++pos;
    }
    return new_number_node(value);
}

int parse_power() {
    int left_root = parse_primary();
    if (pos < static_cast<int>(expr.size()) && expr[pos] == '^') {
        ++pos;
        int right_root = parse_power();
        left_root = new_operator_node('^', left_root, right_root);
    }
    return left_root;
}

int parse_term() {
    int left_root = parse_power();
    while (pos < static_cast<int>(expr.size()) && (expr[pos] == '*' || expr[pos] == '/')) {
        char op = expr[pos];
        ++pos;
        int right_root = parse_power();
        left_root = new_operator_node(op, left_root, right_root);
    }
    return left_root;
}

int parse_expression() {
    int left_root = parse_term();
    while (pos < static_cast<int>(expr.size()) && (expr[pos] == '+' || expr[pos] == '-')) {
        char op = expr[pos];
        ++pos;
        int right_root = parse_term();
        left_root = new_operator_node(op, left_root, right_root);
    }
    return left_root;
}

void build_postfix(int root) {
    if (tree_nodes[root].type == 0) {
        postfix_tokens.push_back({0, tree_nodes[root].value, 0});
        return;
    }
    build_postfix(tree_nodes[root].left_son);
    build_postfix(tree_nodes[root].right_son);
    postfix_tokens.push_back({1, 0, tree_nodes[root].op});
}

void print_postfix_expression(const vector<Token> &tokens) {
    if (tokens.size() == 1 && tokens[0].type == 0) {
        cout << tokens[0].value << '\n';
        return;
    }

    int n = static_cast<int>(tokens.size());
    for (int i = 0; i < n; ++i) {
        if (tokens[i].type == 0) cout << tokens[i].value;
        else cout << tokens[i].op;
        cout << ' ';
    }
    cout << '\n';
}

void simulate_reduction() {
    print_postfix_expression(postfix_tokens);

    while (postfix_tokens.size() > 1) {
        int pos_op = -1;
        int n = static_cast<int>(postfix_tokens.size());
        for (int i = 0; i < n; ++i) {
            if (postfix_tokens[i].type == 1) {
                pos_op = i;
                break;
            }
        }

        long long left_value = postfix_tokens[pos_op - 2].value;
        long long right_value = postfix_tokens[pos_op - 1].value;
        char op = postfix_tokens[pos_op].op;
        long long result = calc(left_value, right_value, op);

        postfix_tokens[pos_op - 2] = {0, result, 0};
        postfix_tokens.erase(postfix_tokens.begin() + pos_op - 1, postfix_tokens.begin() + pos_op + 1);
        print_postfix_expression(postfix_tokens);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> expr;

    int root = parse_expression();
    build_postfix(root);
    simulate_reduction();

    return 0;
}

这题数据范围其实很小，brute.cpp 这种“先建树、再后序遍历、最后顺序模拟”的写法已经可以通过。
正式代码改成经典的“运算符栈 + 后缀序列”模板，原因是它更贴近常见做法，也更方便以后复用。

核心分两步。

第一步：中缀转后缀

扫描原串时分三类处理：

数字：直接放进后缀序列。
左括号：直接入栈。
右括号：一直弹栈，直到遇到左括号。
普通运算符：比较它和栈顶运算符的优先级。

对于左结合运算符 $+ - * /$ ，如果栈顶优先级更高，或者相同，就要先把栈顶弹出。
但 $^$ 是右结合，所以当前运算符也是 $^$ 时，遇到同优先级的 $^$ 不能弹。

右结合为什么要特判

这张表展示样例 $2^2^3$ 在转后缀时，运算符栈和后缀序列的变化。

读入内容	运算符栈	后缀序列
`2`	空	`2`
$^$	$^$	`2`
`2`	$^$	`2 2`
$^$	$^ ^$	`2 2`
`3`	$^ ^$	`2 2 3`
扫描结束	空	$2 2 3 ^ ^$

如果这里把“同优先级也弹出”写死，那么会得到 $2 2 ^ 3 ^$ ，含义就变成了 $(2^2)^3$ 。
所以 $^$ 必须单独按右结合处理，这是这题最容易写错的地方。

第二步：按题意模拟每一步计算

后缀表达式求值本来只要一个栈，但那样只能得到最终答案，不能输出中间序列。
因此这里要维护一个数组，表示“当前还没完全化简完的后缀表达式”。

每次操作：

从左到右找到第一个运算符；
它前面两个位置一定是本次要参与运算的数字；
算出结果后，用结果替换这三个位置；
输出替换后的整个序列。

为什么“第一个运算符”一定可算？
因为合法的后缀表达式里，最左边第一个出现的运算符，前面必然已经形成了两个完整操作数。这正好对应一次最早能发生的归约。

中缀转后缀这一部分的栈处理思路，可以参考 rbook 里的文章：表达式求值。

代码

cpp

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154#include <bits/stdc++.h>
using namespace std;

struct Token {
    int type; // 0 表示数字，1 表示运算符
    long long value;
    char op;
};

string expr;
vector<Token> infix_tokens;
vector<Token> postfix_tokens;
stack<char> op_stack;

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

bool is_right_associative(char op) {
    return op == '^';
}

long long quick_pow(long long a, long long b) {
    long long ans = 1;
    while (b > 0) {
        if (b & 1) ans *= a;
        a *= a;
        b >>= 1;
    }
    return ans;
}

long long calc(long long a, long long b, char op) {
    if (op == '+') return a + b;
    if (op == '-') return a - b;
    if (op == '*') return a * b;
    if (op == '/') return a / b;
    return quick_pow(a, b);
}

void split_infix_tokens() {
    int n = static_cast<int>(expr.size());
    for (int i = 0; i < n;) {
        if (isdigit(expr[i])) {
            long long value = 0;
            while (i < n && isdigit(expr[i])) {
                value = value * 10 + (expr[i] - '0');
                ++i;
            }
            infix_tokens.push_back({0, value, 0});
        } else {
            infix_tokens.push_back({1, 0, expr[i]});
            ++i;
        }
    }
}

void convert_to_postfix() {
    int m = static_cast<int>(infix_tokens.size());
    for (int i = 0; i < m; ++i) {
        Token cur = infix_tokens[i];
        if (cur.type == 0) {
            postfix_tokens.push_back(cur);
            continue;
        }

        if (cur.op == '(') {
            op_stack.push(cur.op);
            continue;
        }

        if (cur.op == ')') {
            while (!op_stack.empty() && op_stack.top() != '(') {
                postfix_tokens.push_back({1, 0, op_stack.top()});
                op_stack.pop();
            }
            if (!op_stack.empty()) op_stack.pop();
            continue;
        }

        while (!op_stack.empty() && op_stack.top() != '(') {
            char top_op = op_stack.top();
            int top_pri = get_priority(top_op);
            int cur_pri = get_priority(cur.op);
            if (top_pri > cur_pri || (top_pri == cur_pri && !is_right_associative(cur.op))) {
                postfix_tokens.push_back({1, 0, top_op});
                op_stack.pop();
            } else {
                break;
            }
        }
        op_stack.push(cur.op);
    }

    while (!op_stack.empty()) {
        postfix_tokens.push_back({1, 0, op_stack.top()});
        op_stack.pop();
    }
}

void print_postfix_expression(const vector<Token> &tokens) {
    if (tokens.size() == 1 && tokens[0].type == 0) {
        cout << tokens[0].value << '\n';
        return;
    }

    int n = static_cast<int>(tokens.size());
    for (int i = 0; i < n; ++i) {
        if (tokens[i].type == 0) cout << tokens[i].value;
        else cout << tokens[i].op;
        cout << ' ';
    }
    cout << '\n';
}

void simulate_reduction() {
    print_postfix_expression(postfix_tokens);

    while (postfix_tokens.size() > 1) {
        int pos = -1;
        int n = static_cast<int>(postfix_tokens.size());
        for (int i = 0; i < n; ++i) {
            if (postfix_tokens[i].type == 1) {
                pos = i;
                break;
            }
        }

        long long left_value = postfix_tokens[pos - 2].value;
        long long right_value = postfix_tokens[pos - 1].value;
        char op = postfix_tokens[pos].op;
        long long result = calc(left_value, right_value, op);

        postfix_tokens[pos - 2] = {0, result, 0};
        postfix_tokens.erase(postfix_tokens.begin() + pos - 1, postfix_tokens.begin() + pos + 1);
        print_postfix_expression(postfix_tokens);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> expr;

    split_infix_tokens();
    convert_to_postfix();
    simulate_reduction();

    return 0;
}

复杂度

设拆分后的记号个数为 m。
中缀转后缀只扫描一遍，时间复杂度是 $O(m)$ 。
模拟输出阶段每次删除 3 个记号、插回 1 个记号，需要在线性表里移动元素，总复杂度是 $O(m^2)$ 。
空间复杂度是 $O(m)$ 。

总结

这题真正要掌握的是两个点：

中缀转后缀时， $^$ 和其他运算符的结合性不同。
题目要求输出每一步过程，所以不能只做“普通后缀求值”，还要显式维护当前序列。

如果以后再遇到“表达式转换”类题目，中缀转后缀的部分几乎可以直接复用。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P1175 表达式的转换

题目描述

平常我们书写的表达式称为中缀表达式，因为它将运算符放在两个操作数中间，许多情况下为了确定运算顺序，括号是不可少的，而后缀表达式就不必用括号了。

后缀标记法：书写表达式时采用运算紧跟在两个操作数之后，从而实现了无括号处理和优先级处理，使计算机的处理规则简化为：从左到右顺序完成计算，并用结果取而代之。

例如：8-(3+2*6)/5+4 可以写为：8 3 2 6 * + 5 / - 4 +

其计算步骤为：

text

1
2
3
4
5
68 3 2 6 * + 5 / - 4 +
8 3 12 + 5 / - 4 +
8 15 5 / - 4 +
8 3 - 4 +
5 4 +
9

编写一个程序，完成这个转换，要求输出的每一个数据间都留一个空格。

输入格式

就一行，是一个中缀表达式。输入的符号中只有这些基本符号 0123456789+-*/^()，并且不会出现形如 2*-3 的格式。

表达式中的基本数字也都是一位的，不会出现形如 12 形式的数字。

所输入的字符串不要判错。

输出格式

若干个后缀表达式，第 $i + 1$ 行比第 $i$ 行少一个运算符和一个操作数，最后一行只有一个数字，表示运算结果。

输入输出样例 #1

输入 #1

text

18-(3+2*6)/5+4

输出 #1

text

1
2
3
4
5
68 3 2 6 * + 5 / - 4 + 
8 3 12 + 5 / - 4 + 
8 15 5 / - 4 + 
8 3 - 4 + 
5 4 + 
9

输入输出样例 #2

输入 #2

text

12^2^3

输出 #2

text

说明/提示

运算的结果可能为负数，/ 以整除运算。并且中间每一步都不会超过 $2^{31}$ 。字符串长度不超过 $100$ 。

注意乘方运算 ^ 是从右向左结合的，即 2 ^ 2 ^ 3 为 2 ^ (2 ^ 3)，后缀表达式为 2 2 3 ^ ^。

其他同优先级的运算是从左向右结合的，即 4 / 2 / 2 * 2 为 ((4 / 2) / 2) * 2，后缀表达式为 4 2 / 2 / 2 *。

保证不会出现计算乘方时幂次为负数的情况，故保证一切中间结果为整数。

表达式的转换

目录

题意

思路

第一步：中缀转后缀

右结合为什么要特判

第二步：按题意模拟每一步计算

代码

复杂度

总结

一图流解析