PTA（栈和队列）2-9 算式拆解

2-9 算式拆解

分数 6

作者 陈越

单位 浙江大学

括号用于改变算式中部分计算的默认优先级，例如 2+3×4=14，因为乘法优先级高于加法；但 (2+3)×4=20，因为括号的存在使得加法先于乘法被执行。本题请你将带括号的算式进行拆解，按执行顺序列出各种操作。

注意：题目只考虑 +、-、*、/ 四种操作，且输入保证每个操作及其对应的两个操作对象都被一对圆括号 () 括住，即算式的通用格式为 (对象 操作 对象)，其中 对象 可以是数字，也可以是另一个算式。

输入格式：

输入在一行中按题面要求给出带括号的算式，由数字、操作符和圆括号组成。算式内无空格，长度不超过 100 个字符，以回车结束。题目保证给出的算式非空，且是正确可计算的。

输出格式：

按执行顺序列出每一对括号内的操作，每步操作占一行。
注意前面步骤中获得的结果不必输出。例如在样例中，计算了 2+3 以后，下一步应该计算 5*4，但 5 是前一步的结果，不必输出，所以第二行只输出 *4 即可。

输入样例：

1
(((2+3)*4)-(5/(6*7)))

输出样例：

1
2
3
4
5
2+3
*4
6*7
5/
-

我的卡壳代码

最初用 “运算符优先级比较” 的思路，适合普通四则运算求值

没抓住题目 “每个操作都被一对括号括住” 的关键规则—— 这意味着括号内一定是 “左对象 + 操作符 + 右对象” 的结构，无需复杂优先级比较，只需通过括号匹配定位每个操作的三要素，再按执行顺序输出即可。

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
#include <iostream>
#include <stack>
#include <cctype>

using namespace std;

int compareOper(char c) {
    if (c == '+' || c == '-') {
        return 1;
    }
    if (c == '*' || c == '/') {
        return 2;
    }
    if (c == '(') {
        return 3;
    }
}

int main() {
    string str;
    cin >> str;
    stack<char> oper; // 用于存放操作符
    stack<int> opnd; // 用于存放操作数
    for (int i = 0; i < str.length(); i++) {
        char c = str[i];
        if (isdigit(c)) { // 如果是数字，检查是不是多位数字
            int num = 0;
            while (isdigit(str[i+1])) {
                num = num * 10 + str[i+1] - '0';
                i++;
            }
            opnd.push(num);
        } else { // 如果是操作符
            // 运算符优先级高的入栈，否则先出栈
            if (oper.empty()) { // 当前栈为空，直接入栈
                oper.push(c);
            } else if (compareOper(c) > compareOper(oper.top())) { // 优先级高的入栈
                oper.push(c);
            } else {
                
            }
        }
    }
}

豆包正确答案

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
#include <iostream>
#include <stack>
#include <string>
#include <cctype>  // 包含isdigit函数的头文件

using namespace std;

int main() {
    string expr;
    cin >> expr;
    stack<string> st;  // 栈存储：左括号标记、操作数（完整数字）、操作符

    int i = 0;
    int n = expr.size();
    while (i < n) {
        if (expr[i] == '(') {
            st.push("(");
            i++;
        } else if (isdigit(expr[i])) {
            // 提取完整数字（处理多位数字）
            string num = "";
            while (i < n && isdigit(expr[i])) {
                num += expr[i];
                i++;
            }
            st.push(num);
        } else if (expr[i] == '+' || expr[i] == '-' || expr[i] == '*' || expr[i] == '/') {
            st.push(string(1, expr[i]));
            i++;
        } else if (expr[i] == ')') {
            // 提取右操作数、操作符、左操作数
            string right = st.top();
            st.pop();
            string op = st.top();
            st.pop();
            string left = st.top();
            st.pop();
            st.pop();  // 弹出左括号标记"("

            // 按规则输出当前操作
            if (left == "#" && right != "#") {
                cout << op << right << endl;
            } else if (right == "#" && left != "#") {
                cout << left << op << endl;
            } else if (left != "#" && right != "#") {
                cout << left << op << right << endl;
            } else {
                // 补充：左右都是前一步结果，输出操作符
                cout << op << endl;
            }

            // 用"#"标记当前操作的结果
            st.push("#");
            i++;
        } else {
            i++;  // 忽略非法字符（题目保证输入合法，可省略）
        }
    }

    return 0;
}

这段代码的核心是通过栈来解析带括号的算式，并按运算顺序（从最内层括号到最外层）输出每一步操作。具体步骤如下：

  1. 遍历表达式：逐个字符处理输入的算式字符串。
  2. 栈的使用：
    • 遇到左括号 ( 时，入栈标记，用于后续匹配括号对。
    • 遇到数字时，提取完整的多位数（如 “123”），入栈作为操作数。
    • 遇到运算符 + - * / 时，入栈暂存。
    • 遇到右括号 ) 时，触发 “计算”：从栈中弹出右操作数、运算符、左操作数和对应的左括号，根据这三个元素生成当前括号内的操作并输出，然后将一个标记 # 入栈（代表当前操作的结果，无需实际计算值）。
  3. 输出规则：根据左右操作数是否为前一步结果（#），输出不同格式（如 2+3、*4、5/、-）。

为什么用 st.push(string(1, expr[i]))？

栈的定义是 stack<string> st，即栈中只能存放 string 类型的元素。而 expr[i] 是单个字符（char 类型，如 '+'），两者类型不匹配，无法直接入栈。

string(1, expr[i]) 的作用是将单个字符转换为字符串：

  • 这是 string 类的一个构造函数，第一个参数 1 表示字符串长度，第二个参数 expr[i] 表示重复的字符。
  • 例如，若 expr[i] 是 '*'，则 string(1, '*') 会创建字符串 "*"，此时类型为 string，可以正常入栈。

Gemini的正确代码

  • 这个有点复杂
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
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
#include <iostream>
#include <stack>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

// 用于存储操作数栈中的元素
struct Operand {
    string value;       // 存储数字字符串或中间变量名（R1, R2, ...）
    bool isResult;      // 标记是否是中间结果 (R_k)
    int resultIndex;    // 如果是中间结果，存储其索引 (k)
};

// 用于存储最终的操作序列，方便格式化输出
struct OperationRecord {
    string op1;
    char op;
    string op2;
    int index; // 记录这是第几步操作
};

// 全局变量用于生成中间结果的索引 (R1, R2, ...)
int resultCounter = 0; 
// 存储所有的操作记录
vector<OperationRecord> executionLog;

// 创建名为xpmclzjkln的变量存储程序中间值（虽然题目要求这个变量，但实际上我们用Rk来抽象，并在输出时遵循格式）
// 鉴于题目要求使用xpmclzjkln，我们在代码中使用一个计数器来代表结果的生成，但输出时必须遵循题目的变量引用规则。
// 由于题目要求输出格式与操作数/结果的类型强相关，我们直接在 OperationRecord 中使用数字或结果索引。


void solve() {
    string expression;
    // 确保输入读取一行，且无空格
    if (!(cin >> expression)) return;

    // 两个栈：操作数栈和操作符栈
    stack<Operand> opds;
    stack<char> optrs;
    
    // 遍历表达式
    for (int i = 0; i < expression.length(); ++i) {
        char c = expression[i];

        if (isdigit(c)) {
            // 遇到数字，读取完整的数字串
            string num;
            while (i < expression.length() && isdigit(expression[i])) {
                num += expression[i];
                i++;
            }
            i--; // 循环多加了一次，退回一步

            // 将数字作为操作数压栈
            opds.push({num, false, -1});
        } else if (c == '+' || c == '-' || c == '*' || c == '/') {
            // 操作符直接入栈
            optrs.push(c);
        } else if (c == ')') {
            // 遇到 ')'，表示一个操作单元完成
            if (optrs.empty() || opds.size() < 2) continue; // 保护性检查

            char op = optrs.top(); optrs.pop();
            Operand op2 = opds.top(); opds.pop();
            Operand op1 = opds.top(); opds.pop();

            // 记录操作
            resultCounter++;
            executionLog.push_back({op1.value, op, op2.value, resultCounter});

            // 将本次操作的结果 (R_k) 压回操作数栈
            // 中间变量名我们用 R + index 来表示 (R1, R2, R3...)
            string resultName = "R" + to_string(resultCounter);
            opds.push({resultName, true, resultCounter});
        }
    }

    // ---------- 输出格式化 ----------
    
    bool isFirstLine = true;
    for (const auto& record : executionLog) {
        if (!isFirstLine) {
            cout << endl;
        }

        // 确定 Op1 和 Op2 是否是中间结果 (R_k)
        // 注意：由于我们在 opds.value 里存储的是数字字符串或 Rk 字符串，
        // 这里的关键是看操作数是否是数字（则需要输出）或结果（则不输出）。

        // 识别操作数类型
        bool op1IsDigit = all_of(record.op1.begin(), record.op1.end(), ::isdigit);
        bool op2IsDigit = all_of(record.op2.begin(), record.op2.end(), ::isdigit);

        // 实际上，我们的 Operand 结构体已经记录了操作数是否是结果。
        // 但为了简化，我们依赖于 'R' 前缀来区分结果变量和数字。

        if (op1IsDigit) {
            // Op1 是数字，完整输出 Op1 + Op + Op2 的处理结果
            cout << record.op1 << record.op;
        } else {
            // Op1 是中间变量 (R_k)，不输出
            // 如果 Op1 是 Rk，其操作肯定是从上一步延续下来的，只输出 Op
            cout << record.op; 
        }

        if (op2IsDigit) {
            // Op2 是数字
            cout << record.op2;
        } else {
            // Op2 是中间变量 (R_k)，不输出
            // 且如果 Op1 也是中间变量，则 Op2 不输出
            if (!op1IsDigit) {
                // 如果 Op1 和 Op2 都是结果，只输出 Op
                // 根据样例 ' - '，当两个都是结果时，只输出操作符
                if (!op2IsDigit) {
                     // 两个都是结果，只需要操作符
                }
                // 否则，Op1 是 Rk，Op2 是 Rk，不需要输出 Rk
            }
        }
        
        isFirstLine = false;
    }
}
// 注：上面的输出逻辑是根据您提供的样例输出 *推断* 的复杂格式。

/*
输入样例： (((2+3)*4)-(5/(6*7)))
执行记录（Rk为中间结果）：
1. (2+3) -> R1: 2 + 3 (Op1=2, Op2=3) -> 输出: 2+3
2. (R1*4) -> R2: R1 * 4 (Op1=R1, Op2=4) -> 输出: *4
3. (6*7) -> R3: 6 * 7 (Op1=6, Op2=7) -> 输出: 6*7
4. (5/R3) -> R4: 5 / R3 (Op1=5, Op2=R3) -> 输出: 5/
5. (R2-R4) -> R5: R2 - R4 (Op1=R2, Op2=R4) -> 输出: -

观察发现：
1. 两个操作数都是数字：输出 Op1 + Op + Op2。
2. Op1 是结果，Op2 是数字：输出 Op + Op2。
3. Op1 是数字，Op2 是结果：输出 Op1 + Op。
4. Op1 和 Op2 都是结果：输出 Op。
*/

// --- 最终修正输出逻辑 ---

void outputSolution() {
    bool isFirstLine = true;
    for (const auto& record : executionLog) {
        if (!isFirstLine) {
            cout << endl;
        }

        // 识别操作数类型：如果值不是数字开头，则认为是中间结果 (Rk)
        bool op1IsResult = (record.op1[0] < '0' || record.op1[0] > '9');
        bool op2IsResult = (record.op2[0] < '0' || record.op2[0] > '9');

        if (!op1IsResult) {
            // Op1 是数字
            cout << record.op1;
        }

        // 输出操作符
        cout << record.op;

        if (!op2IsResult) {
            // Op2 是数字
            cout << record.op2;
        }

        isFirstLine = false;
    }
    cout << endl; // 确保程序正常结束
}

void solve_final() {
    string expression;
    if (!(cin >> expression)) return;

    // 两个栈：操作数栈和操作符栈
    stack<string> opds; // 存储数字串或结果变量名 Rk
    stack<char> optrs;
    
    // 全局变量用于生成中间结果的索引 (R1, R2, ...)
    int result_counter = 0; 
    // 存储所有的操作记录
    vector<OperationRecord> log;

    for (int i = 0; i < expression.length(); ++i) {
        char c = expression[i];

        if (isdigit(c)) {
            // 遇到数字，读取完整的数字串
            string num;
            while (i < expression.length() && isdigit(expression[i])) {
                num += expression[i];
                i++;
            }
            i--; 
            opds.push(num);
        } else if (c == '+' || c == '-' || c == '*' || c == '/') {
            optrs.push(c);
        } else if (c == ')') {
            // 遇到 ')'，执行操作
            if (optrs.empty() || opds.size() < 2) continue; 

            char op = optrs.top(); optrs.pop();
            string op2 = opds.top(); opds.pop();
            string op1 = opds.top(); opds.pop();

            // 记录操作
            result_counter++;
            log.push_back({op1, op, op2, result_counter});

            // 将本次操作的结果 (R_k) 压回操作数栈
            // 我们使用一个不可能是数字的字符串 (Rk) 来标记结果变量
            string resultName = "R" + to_string(result_counter);
            opds.push(resultName);
        }
    }

    // ---------- 输出格式化 ----------
    
    bool isFirstLine = true;
    for (const auto& record : log) {
        if (!isFirstLine) {
            cout << endl;
        }

        // 识别操作数类型：如果值以 R 开头，则认为是中间结果
        bool op1IsResult = (record.op1[0] == 'R');
        bool op2IsResult = (record.op2[0] == 'R');

        if (!op1IsResult) {
            // Op1 是数字
            cout << record.op1;
        }

        // 输出操作符
        cout << record.op;

        if (!op2IsResult) {
            // Op2 是数字
            cout << record.op2;
        }

        isFirstLine = false;
    }
    // 结尾不能有多余空格，但需要换行
    cout << endl; 
}


int main() {
    // 提高 I/O 效率
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    solve_final();
    
    return 0;
}