PTA（栈和队列）1-1 括号匹配

1-1 括号匹配

分数 4

作者 黄龙军

单位 绍兴文理学院

要求实现函数，借助如下自定义栈SqStack判断一个中、小括符[、]、(、)组成的字符串中的括弧是否匹配，是则返回true，否则返回false。例如，[[()]]、([[()]])、(()[[]])是匹配的，而(((、()]、 ([(]))是不匹配的。

1
2
3
4
5
6
7
8
9
10
typedef char ElemType;                    // 为char取别名ElemType
struct SqStack{
    ElemType  *base;                      // 顺序栈的首地址，动态数组的首地址
    int top;                              // 栈顶指针，栈非空时，为栈顶元素的下标(从0开始)
    void Init( );                         // 初始化栈
    ElemType GetTop();                    // 取栈顶元素    
    void Push(ElemType e);                // 入栈
    void Pop();                           // 出栈
    bool Empty();                         // 判断空栈
};

函数接口定义：

1
bool matching(string exp);

其中参数 exp是一个仅包含中、小括符[、]、(、)的字符串。

裁判测试程序样例：

1
2
3
4
5
6
7
8
9
10
11
#include<iostream>
#include<string>
using namespace std;
int main(){
    string s;
    while(cin>>s){
        if (matching(s)) cout<<"yes\n";
        else cout<<"no\n";
    } 
    return 0;
}

输入样例：

1
2
3
4
()[]
[()]
[(()]]
[(])

输出样例：

1
2
3
4
yes
yes
no
no

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool matching(string exp) {
    struct SqStack stack;
    stack.Init(); // 初始化栈
    for (int i = 0; i < exp.size(); i++) { // 一次遍历字符串中的每个括号
        if (exp[i] == '(' || exp[i] == '[') { // 如果是左括号，则入栈
            stack.Push(exp[i]);
        } else { // 如果是读取的是右括号
            if (stack.Empty()) { // 如果当前是空栈
                return false; // 有右括号且是空栈直接错误
            } else { // 不是空栈，看里面是什么
                char topELem;
                topELem = stack.GetTop(); // 获取栈顶元素存到topElem里面
                stack.Pop(); // 栈顶元素出来

                if (exp[i] == ')' && topELem != '(') { // 左右（）不匹配
                    return false;
                } else if (exp[i] == ']' && topELem != '[') { // 左右[]不匹配
                    return false;
                }
            }
        }
    }
    return stack.Empty(); // 如果栈为空，说明里面没有左括号了，全部匹配
}

代码核心逻辑

  1. 初始化栈：用于存储遍历到的左括号。
  2. 遍历字符串：
    • 遇到左括号 ( 或 [，直接入栈；
    • 遇到右括号)或]：
      • 若栈为空，说明右括号无对应左括号，返回 false；
      • 若栈非空，弹出栈顶元素，检查是否与当前右括号匹配) 对应 (，] 对应 [，不匹配则返回 false。
  3. 遍历结束：栈为空说明所有左括号都有对应右括号，返回 true；否则返回 false。

我的错误点

修正前的代码中，匹配条件颠倒了左右括号的对应关系（如写成 exp[i] == '(' && topELem != ')'），导致逻辑判断完全错误；修正后已纠正该问题，当前代码逻辑正确。

如何遍历string

在 C++ 中，遍历 string 有多种常见方式，以下是详细说明和示例：

1. 基于下标（for 循环 + 索引）

这是最基础的方式，通过字符串的长度 size() 或 length() 来控制循环次数，通过索引访问每个字符。

1
2
3
4
5
string s = "Hello";
for (int i = 0; i < s.size(); ++i) {
    cout << s[i] << " ";
}
// 输出：H e l l o

2. 基于范围的 for 循环（C++11 及以上支持）

这是最简洁的方式，自动遍历字符串中的每个字符。

1
2
3
4
5
string s = "World";
for (char c : s) {
    cout << c << " ";
}
// 输出：W o r l d