PTA（栈和队列）2-3 符号配对

2-3 符号配对

分数 6

作者 DS课程组

单位 浙江大学

请编写程序检查C语言源程序中下列符号是否配对：/*与*/、(与)、[与]、{与}。

输入格式:

输入为一个C语言源程序。当读到某一行中只有一个句点.和一个回车的时候，标志着输入结束。程序中需要检查配对的符号不超过100个。

输出格式:

首先，如果所有符号配对正确，则在第一行中输出YES，否则输出NO。然后在第二行中指出第一个不配对的符号：如果缺少左符号，则输出?-右符号；如果缺少右符号，则输出左符号-?。

输入样例1：

1
2
3
4
5
6
7
void test()
{
    int i, A[10];
    for (i=0; i<10; i++) { /*/
        A[i] = i;
}
.

输出样例1：

1
2
NO
/*-?

输入样例2：

1
2
3
4
5
6
7
void test()
{
    int i, A[10];
    for (i=0; i<10; i++) /**/
        A[i] = i;
}]
.

输出样例2：

1
2
NO
?-]

输入样例3：

1
2
3
4
5
6
7
8
void test()
{
    int i
    double A[10];
    for (i=0; i<10; i++) /**/
        A[i] = 0.1*i;
}
.

输出样例3：

1
YES
  • 这题麻烦就麻烦在处理/*和*/

我的初始错误代码

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
#include <iostream>
using namespace std;

// 定义顺序栈结构
typedef struct {
    char *elem;
    int top;
}sqStack;

// 初始化顺序栈
void initStack(sqStack &stack) {
    stack.elem = new char[100];
    stack.top = -1;
}

// 获取栈顶元素
char getTop(sqStack stack) {
     return stack.elem[stack.top];
}

// 判断栈是否为空
bool isEmpty(sqStack stack) {
    if (stack.top == -1) {
        return true;
    }
    return false;
}

// 进栈
void push(sqStack &stack, char c) {
    stack.top++;
    stack.elem[stack.top] = c;
}

// 出栈
void pop(sqStack &stack) {
    stack.top--;
}

// 符号配对
void matching(sqStack stack, string str) {
    int i = 0; // 用于遍历字符串
    int j = i+1; // 用于解决/**/的配对
    while (str[i] != '.') {
        if (str[i] == '(' || str[i] == '[' || str[i] == '{') { // 如果是左括号
            push(stack, str[i]);
        } else if (str[i] == '/' && str[j] == '*') {
            push(stack, str[i]);
            push(stack, str[j]);
            i = j;
        } else if (str[i] == ')') {
            if (isEmpty(stack)) { // 没有左括号
                cout << "NO" << endl;
                cout << "(-?";
                return; // 直接退出
            } else if (getTop(stack) == '(') { // 匹配了
                pop(stack);
            }
        } else if (str[i] == ']') {
            if (isEmpty(stack)) { // 没有左括号
                cout << "NO" << endl;
                cout << "[-?";
                return; // 直接退出
            } else if (getTop(stack) == '[') { // 匹配了
                pop(stack);
            }
        } else if (str[i] == '}') {
            if (isEmpty(stack)) { // 没有左括号
                cout << "NO" << endl;
                cout << "{-?";
                return; // 直接退出
            } else if (getTop(stack) == '{') { // 匹配了
                pop(stack);
            }
        } else if (str[i] == '*' && str[j] == '/') {
            if (stack.top < 1) { // 没有两个以上的字符，直接退出
                cout << "NO" << endl;
                cout << "/*-?";
                return;
            } else if (getTop(stack) == '*') { // 匹配了第一个*
                pop(stack);
                if (getTop(stack) == '/') {
                    pop(stack);
                } else {
                    cout << "NO" << endl;
                    cout << "?-/*";
                    return;
                }
            }
        }
        i++;
    }
    cout << "YES";
}

int main() {
    sqStack stack;
    initStack(stack);
    string str;
    cin >> str;
    matching(stack, str);
}

1.输入处理错误：

1
cin >> str;  // 错误的输入读取方式

这种方式只能读取单行输入，且会忽略空格和换行符，无法处理多行的 C 语言代码，也无法检测到单独的.作为结束标志。

改正方案：

1
2
3
4
5
6
7
8
string line;
while (getline(cin, line)) {  // 逐行读取
    if (line == ".") {  // 检查结束标志
        foundEnd = true;
        break;
    }
    // 处理当前行内容...
}

使用getline逐行读取输入，直到遇到只包含.的行才停止，符合题目要求。

2.有右括号的情况下栈中的元素不匹配

有问题

改正1（错误）

  • 发现最后一个答案不正确，又发现把测试用例1输入对应的输出是*-?，

  • 通过在有右括号的情况下的找栈顶发现不匹配的地方，加上了：

  • 如果是*/，就判断栈中是不是*/，其他就直接输出栈顶元素-?

  • 见改正2

测试点 提示 内存(KB) 用时(ms) 结果 得分
0 484 2 答案正确 1 / 1
1 552 2 答案正确 1 / 1
2 552 2 答案正确 1 / 1
3 600 2 答案正确 1 / 1
4 564 2 答案正确 1 / 1
5 576 2 答案错误 0 / 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
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
#include <iostream>
#include <string>
#include <stack> // 使用 C++ 标准库 stack，避免手动实现和内存管理问题

using namespace std;

// 符号配对函数
void matching() {
    // 使用 std::stack<char> 存储左符号的标记
    // '(' -> '('
    // '[' -> '['
    // '{' -> '{'
    // '/*' -> 'C' (用 'C' 标记 C语言注释的开始)
    stack<char> symbolStack;
    string line;
    
    // 跟踪第一个不匹配的符号，默认为空
    string error_symbol = "";

    // 逐行读取输入
    while (getline(cin, line)) {
        if (line == ".") {
            break;
        }

        for (size_t i = 0; i < line.size(); ++i) {
            char c = line[i];
            
            // --- 1. 处理左符号 ---
            if (c == '(' || c == '[' || c == '{') {
                symbolStack.push(c);
            } 
            
            // 处理 /*
            else if (c == '/') {
                if (i + 1 < line.size() && line[i + 1] == '*') {
                    symbolStack.push('C'); // 'C' 代表 /*
                    i++; // 跳过下一个字符 '*'
                }
            }
            
            // --- 2. 处理右符号 ---
            else if (c == ')' || c == ']' || c == '}') {
                if (symbolStack.empty()) {
                    // 缺少左符号
                    error_symbol = "?-";
                    error_symbol += c;
                    goto end_of_check; // 跳转到输出结果部分
                }
                
                char top = symbolStack.top();
                symbolStack.pop();

                // 检查匹配性
                if ((c == ')' && top != '(') ||
                    (c == ']' && top != '[') ||
                    (c == '}' && top != '{')) 
                {
                    // 符号不匹配：例如 ( 遇到了 ]
                    error_symbol = top;
                    error_symbol += "-?";
                    goto end_of_check; // 跳转到输出结果部分
                }
            } 
            
            // 处理 */
            else if (c == '*') {
                if (i + 1 < line.size() && line[i + 1] == '/') {
                    // 检查栈是否为空，以及栈顶是否是 'C'
                    if (symbolStack.empty() || symbolStack.top() != 'C') {
                        // 缺少左符号 /*
                        error_symbol = "?-*/";
                        goto end_of_check;
                    }
                    symbolStack.pop(); // 弹出 'C'
                    i++; // 跳过下一个字符 '/'
                }
            }
        }
    }

    // --- 3. 循环结束后检查栈 ---
    end_of_check:; // 标签，用于 goto

    if (error_symbol != "") {
        // 发现不匹配的右符号或不匹配的左符号
        cout << "NO" << endl;
        cout << error_symbol << endl;
    } else if (symbolStack.empty()) {
        // 栈为空，全部配对成功
        cout << "YES" << endl;
    } else {
        // 缺少右符号
        cout << "NO" << endl;
        char top = symbolStack.top();
        
        if (top == 'C') {
            cout << "/*-?" << endl;
        } else {
            cout << top << "-?" << endl;
        }
    }
}

int main() {
    // 提高输入输出速度
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    matching();
    return 0;
}

改正2（错误）

  • 依旧不对？？？？？？
测试点 提示 内存(KB) 用时(ms) 结果 得分
0 552 2 答案正确 1 / 1
1 524 2 答案正确 1 / 1
2 576 2 答案正确 1 / 1
3 524 2 答案正确 1 / 1
4 584 2 答案正确 1 / 1
5 564 2 答案错误 0 / 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
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
#include <iostream>
using namespace std;

// 定义顺序栈结构
typedef struct {
    char *elem;
    int top;
}sqStack;

// 初始化顺序栈
void initStack(sqStack &stack) {
    stack.elem = new char[100];
    stack.top = -1;
}

// 获取栈顶元素
char getTop(sqStack stack) {
     return stack.elem[stack.top];
}

// 判断栈是否为空
bool isEmpty(sqStack stack) {
    if (stack.top == -1) {
        return true;
    }
    return false;
}

// 进栈
void push(sqStack &stack, char c) {
    stack.top++;
    stack.elem[stack.top] = c;
}

// 出栈
void pop(sqStack &stack) {
    stack.top--;
}

// 符号配对
void matching(sqStack stack) {
    bool foundEnd = false;
    string line;
    while (getline(cin, line)) {
        if (line == ".") {
            foundEnd = true;
            break;
        }
        for (int i = 0; i < line.size(); i++) {
            if (line[i] == '(' || line[i] == '[' || line[i] == '{') { // 如果是左括号
                push(stack, line[i]);
            } else if (line[i] == '/' && i + 1 < line.size() && line[i + 1] == '*') {
                push(stack, line[i]);
                push(stack, line[i + 1]);
                i++;  // 跳过下一个字符
            } else if (line[i] == ')') {
                if (isEmpty(stack)) { // 没有左括号
                    cout << "NO" << endl;
                    cout << "?-)";
                    return; // 直接退出
                } else if (getTop(stack) == '(') { // 匹配了
                    pop(stack);
                } else { // 匹配到其他字符了
                    cout << "NO" << endl;
                    // 如果栈里面是/*
                    if (stack.top >= 1 && stack.elem[stack.top-1] == '/' && stack.elem[stack.top] == '*') {
                        cout << "/*-?";
                        return;
                    }
                    // 如果栈中不是/*
                    cout << getTop(stack) << "-?";
                    return;
                }
            } else if (line[i] == ']') {
                if (isEmpty(stack)) { // 没有左括号
                    cout << "NO" << endl;
                    cout << "?-]";
                    return; // 直接退出
                } else if (getTop(stack) == '[') { // 匹配了
                    pop(stack);
                } else { // 匹配到其他字符了
                    cout << "NO" << endl;
                    // 如果栈里面是/*
                    if (stack.top >= 1 && stack.elem[stack.top-1] == '/' && stack.elem[stack.top] == '*') {
                        cout << "/*-?";
                        return;
                    }
                    // 如果栈中不是/*
                    cout << getTop(stack) << "-?";
                    return;
                }
            } else if (line[i] == '}') {
                if (isEmpty(stack)) { // 没有左括号
                    cout << "NO" << endl;
                    cout << "?-}";
                    return; // 直接退出
                } else if (getTop(stack) == '{') { // 匹配了
                    pop(stack);
                } else { // 匹配到其他字符了
                    cout << "NO" << endl;
                    // 如果栈里面是/*
                    if (stack.top >= 1 && stack.elem[stack.top-1] == '/' && stack.elem[stack.top] == '*') {
                        cout << "/*-?";
                        return;
                    }
                    // 如果栈中不是/*
                    cout << getTop(stack) << "-?";
                    return;
                }

                // 处理*/
            } else if (line[i] == '*' && i + 1 < line.size() && line[i + 1] == '/') {
                if (stack.top < 1 || getTop(stack) != '*' && stack.elem[stack.top - 1] != '/') {
                    // 没有两个以上的字符，直接退出
                    cout << "NO" << endl;
                    cout << "?-*/";
                    return;
                }
                pop(stack);
                pop(stack);
                i++;
            }
        }
    }
    if (!foundEnd) {
        cout << "NO";
    }
    if (isEmpty(stack)) {
        cout << "YES";
    } else {
        cout << "NO" << endl;
        // 处理剩余的/*情况
        if (stack.top >= 1 && stack.elem[stack.top-1] == '/' && stack.elem[stack.top] == '*') {
            cout << "/*-?";
        } else {
            cout << getTop(stack) << "-?";
        }

    }
}

int main() {
    sqStack stack;
    initStack(stack);
    matching(stack);
}

正确代码

  • 正确且简化了代码逻辑
  • 把/*视为一个整体，用单个特殊字符'C'入栈
  • 匹配*/时，只需检查栈顶是否是'C'，一次出栈即可
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
#include <iostream>
using namespace std;

// 定义顺序栈结构
typedef struct {
    char *elem;
    int top;
}sqStack;

// 初始化顺序栈
void initStack(sqStack &stack) {
    stack.elem = new char[100];
    stack.top = -1;
}

// 获取栈顶元素
char getTop(sqStack stack) {
     return stack.elem[stack.top];
}

// 判断栈是否为空
bool isEmpty(sqStack stack) {
    if (stack.top == -1) {
        return true;
    }
    return false;
}

// 进栈
void push(sqStack &stack, char c) {
    stack.top++;
    stack.elem[stack.top] = c;
}

// 出栈
void pop(sqStack &stack) {
    stack.top--;
}

// 符号配对
void matching(sqStack stack) {
    string line;
    while (getline(cin, line)) {
        if (line == ".") {
            break;
        }
        for (int i = 0; i < line.size(); i++) {
            char c = line[i];

            // 1. 处理左符号
            if (c == '(' || c == '[' || c == '{') { // 如果是左括号
                push(stack, c);
            } else if (c == '/' && i + 1 < line.size() && line[i + 1] == '*') {
                push(stack, 'C');//将 /* 视为一个特殊符号 'C' (Comment) 入栈，以简化 */ 匹配
                i++;  // 跳过下一个字符
            }

            // 2. 处理右符号
            else if (c == ')' || c == ']' || c == '}') {
                char required_left = (c == ')') ? '(' : (c == ']') ? '[' : '{';
                if (isEmpty(stack)) { // 没有左括号
                    cout << "NO" << endl;
                    cout << "?-" << c;
                    return; // 直接退出
                } 
                // 获取栈顶元素
                char top = getTop(stack);

                if (top == required_left) {
                    pop(stack); // 匹配成功
                } else if (top == 'C') { // 这种情况是遇到右括号，但是栈顶是/*
                    cout << "NO" << endl;
                    cout << "/*-?";
                    return; // 直接退出
                } else  { // 栈顶是不匹配的括号
                    cout << "NO" << endl;
                    cout << getTop(stack) << "-?";
                    return; // 直接退出
                }
            }

            //  4.处理*，结束的
            else if (c == '*' && i + 1 < line.size() && line[i + 1] == '/') {
                if (isEmpty(stack)) {
                    cout << "NO" << endl;
                    cout << "?-*/"; // 缺少 /*
                    return; // 直接退出
                } else if (getTop(stack) == 'C') { // 匹配我们之前压入的 'C'
                    pop(stack);
                    i++; // 跳过下一个字符 '/'
                } else {
                    // 栈顶是普通左括号，无法匹配 */
                    cout << "NO" << endl;
                    cout << getTop(stack) << "-?";
                    return; // 直接退出
                }
            }
        }
    }
    if (isEmpty(stack)) {
        cout << "YES";
    } else { // 此时栈还是非空
        cout << "NO" << endl;
        // 处理剩余的/*情况
        char top = getTop(stack);
        if (top == 'C') {
            cout << "/*-?";
            return; // 直接退出
        } else {
            cout << getTop(stack) << "-?";
            return; // 直接退出
        }

    }
}

int main() {
    sqStack stack;
    initStack(stack);
    matching(stack);
}

核心思路：用栈（先进后出） 处理符号配对，将双字符注释/*抽象为单个标识简化逻辑，按 “左符号入栈、右符号匹配出栈” 的规则校验。

关键步骤

  1. 左符号入栈：遇到(/[/{直接入栈；遇到/*时，压入特殊字符'C'（代表注释开始，避免双字符拆分混乱）。
  2. 右符号匹配：
    • 遇到)/]/}时，检查栈顶是否为对应左符号，匹配则出栈，不匹配或栈空直接报错。
    • 遇到*/时，检查栈顶是否为'C'（对应/*），匹配则出栈，否则报错。
  3. 最终校验：所有输入处理完后，栈为空则配对成功（输出 YES），非空则存在未匹配左符号（输出对应错误）。