
## 1. 括号匹配
时间限制：1秒        内存限制：128M
## 题目描述

假设表达式中允许包含圆括号和方括号两种括号，其嵌套的顺序随意，如([]())或[([][])]等为正确的匹配，[(])或([]()或(()))均为错误的匹配 
本题的任务是检验一个给定的表达式中的括号是否匹配正确 
输入一个只包含圆括号和方括号的字符串，判断字符串中的括号是否匹配，匹配就输出“OK”，不匹配就输出“Wrong”
## 输入描述

一行字符，只含有圆括号和方括号，个数小于255
## 输出描述

匹配就输出一行文本“OK“，不匹配就输出一行文本”Wrong”
## 样例

## 输入

```bash
[(])
```
## 输出

```bash
Wrong
```
## 解题思路：
**【题目分析】**
利用**数组模拟栈的 “****后进先出****” 特性**，完美契合了 “括号匹配需左括号与最近右括号成对” 的核心逻辑：
- 入栈过程：遇到左括号就入栈，保证 “后入栈的左括号先参与匹配”。
- 出栈校验：遇到右括号就检查栈顶左括号是否匹配，匹配则出栈，不匹配则直接判定错误。
- 通过栈的栈顶指针`top`（也就是数组的下标）管理元素的入栈、出栈操作。

**【讲解步骤】**
- 整体解题分为 3 个核心步骤：
	- **我们采用数组模拟栈的方式实现括号匹配**
		1. 数组 `stack` 对应栈的存储空间，每个元素存储左括号`[` 或 `(`
		2. 变量 `top` 作为 “栈顶指针”，存储当前栈顶的下标
	- ** 初始 “栈结构” 构建（左括号****入栈****）**
		1. 每次遇到左括号，先执行 `++top`（栈顶指针上移），再将左括号存入 `stack[top]`。
		2. 例如输入 `[(])`，遍历到 `'['` 时，`top` 从 0 变为 1，`stack[1] = '['`；遍历到 `'('` 时，`top` 变为 2，`stack[2] = '('`。
	- **匹配操作（右括号****出栈****校验）**
		1. 遇到右括号`)` 或 `]`时，需校验**栈顶左括号**是否与之匹配（这是 “出栈 + 校验” 的核心操作）：
		2. 若遇到 `')'`，则检查栈顶元素 `stack[top]` 是否为 `'('`：
			- 若匹配，执行 `--top`（栈顶指针下移，模拟出栈）；
			- 若不匹配，直接判定括号不合法，输出 `Wrong`。
		3. 若遇到 `']'`，则检查栈顶元素 `stack[top]` 是否为 `'['`：
			- 若匹配，执行 `--top`；
			- 若不匹配，直接判定括号不合法，输出 `Wrong`
	- **结果判定**
		    遍历结束后，通过 `top` 的值判断括号是否完全匹配：
		1. 若 `top == 0`，说明所有左括号都有对应的右括号匹配，输出 `OK`；
		2. 若 `top != 0`，说明存在未匹配的左括号，输出 `Wrong`。

## 参考代码
```cpp
#include <iostream>
using namespace std;

int n, top;          // n：没用上的变量；top：栈顶指针（指向栈最上面的元素）
string s;             // 存储输入的括号字符串
char stack[260];      // 栈数组，用来存放左括号 [ (

int main(){
    cin >> s;        // 输入括号字符串，例如："([])"  "[(])"
    int len = s.size();  // 获取字符串长度

    // 遍历字符串的每一个字符
    for(int i = 0; i < len; i++){

        // ======================
        // 情况1：遇到左括号 [ ( → 入栈
        // ======================
        if(s[i] == '[' || s[i] == '('){
            stack[++top] = s[i];  // top先+1，再把左括号存入栈
        }

        // ======================
        // 情况2：遇到右括号 ) → 匹配
        // ======================
        if(s[i] == ')'){
            // 检查栈顶是不是对应的左括号 (
            if(stack[top] == '('){
                --top;  // 匹配成功，栈顶出栈（指针减1）
            }else{
                cout << "Wrong";  // 不匹配，直接输出错误
                return 0;         // 结束程序
            }
        }

        // ======================
        // 情况3：遇到右括号 ] → 匹配
        // ======================
        if(s[i] == ']'){
            // 检查栈顶是不是对应的左括号 [
            if(stack[top] == '['){
                --top;  // 匹配成功，栈顶出栈
            }else{
                cout << "Wrong";  // 不匹配，输出错误
                return 0;
            }
        }
    }

    // ======================
    // 遍历完所有字符后
    // 如果栈空（top=0）→ 所有括号都匹配成功
    // 如果栈不空 → 有多余左括号，匹配失败
    // ======================
    if(top == 0){
        cout << "OK";    // 完全匹配
    }else{
        cout << "Wrong"; // 有剩余左括号
    }

    return 0;
}
```

# 二、 铁轨问题

时间限制：1秒        内存限制：128M
## 题目描述

每辆火车都从A方向驶入车站C，再从B方向驶出车站C，同时它的车厢可以进行某种形式的重新组合。组合方式为：最晚驶入车站C的车厢停在最前边，可以在任意时间将停在最前边的车厢驶出车站C。假设从A方向驶来的火车有n节车厢(n<1000)，分别按顺序编号为1，2，......n。假设在进入车站之前每节车厢之间都是不连着的，并且他们可以自由移动，直接倒出在B方向的铁轨上。另外假设车站C里可以停放任意多节车厢。但是一旦当一节车厢进入车站C，它就不能再回到A方向的铁轨上，并且一旦当它进入B方向的铁轨后，它就不能再回到车站C。负责车厢调度的工作人员需要知道能否使用它以a1, a2, ......an的顺序从B方向输出，请写一个程序，用来判断能否得到指定的车厢顺序。
## 输入描述

第一行，一个整数n,表示有n节车厢；接下来一行有n个整数，表示对应顺序
## 输出描述

输出仅1行。若可以，则输出“Possible”否则输出“Impossible”
 
## 样例

## 输入

```bash
5
3 5 4 2 1
```
## 输出

```bash
Possible
```

## 解题思路：
【题目剖析】
- **A 方向铁轨**：
	- 对应 “按 1~n 顺序排列的待入栈车厢”，用变量 `c` 标记 “下一个要进入车站 C 的车厢编号”（初始 `c=1`，即先调度 1 号车厢）。
- **车站 C**：
	- 用静态数组 `stack` 模拟（栈的核心特性：最晚进入的车厢在最前，符合题目 “后进先出” 的调度规则），`top` 为栈顶指针（`top=0` 表示栈空，即车站 C 无车厢）。
- **B 方向铁轨**：
	- 对应 “目标输出顺序”，用数组 `a` 存储（`a[i]` 表示第 `i` 个需要从 B 方向驶出的车厢编号）。
- **调度规则**：
	- 车厢从 A→C 后不能回 A，从 C→B 后不能回 C，本质是 “栈的入栈不可逆、出栈不可逆”

![image](https://developer.qcloudimg.com/http-save/yehe-2641126/0569d9c1cdd0e615385926e8d264c1a7.png)
![image](https://developer.qcloudimg.com/http-save/yehe-2641126/1f18cc3f1dd95afb768536cb9bc621c1.png)
【讲解步骤】
这个题目详细讲解 “遍历目标序列 `a`，通过栈的入栈 / 出栈操作，验证能否依次匹配每个目标车厢”。
1. 历目标序列，逐个匹配车厢

外层循环 `for(i：1~n)` 遍历目标数组 `a`，每次要匹配 “第 `i` 个需要驶出到 B 的车厢 `a[i]`”。
1. 入栈操作 —— 补充车厢到车站 C
	  当 “车站 C 为空（`top=0`）” 或 “车站 C 最前面的车厢（栈顶元素 `stack[top]`）不是当前目标 `a[i]`” 时，需要从 A 方向调度下一节车厢进入 C，即执行入栈：

- 用 `stack[++top] = c++` 实现入栈：先将 `top` 上移（栈顶位置更新），再把当前待入栈的车厢 `c` 存入栈，最后 `c` 自增（指向下一节待调度的车厢）。
- 关键判断 `if(c > n)`：若 `c` 超过总车厢数 `n`，说明 A 方向所有车厢已进入 C，但栈顶仍不匹配目标 —— 此时无法继续调度，直接输出 `Impossible` 并终止程序。

1. 出栈操作 —— 匹配成功，驶出到 B
	  当栈顶 `stack[top]` 等于目标 `a[i]` 时，说明车站 C 最前面的车厢正是需要驶出到 B 的车厢，执行出栈：
	1. 用 `--top` 实现出栈：将 `top` 下移（栈顶位置更新，相当于移除栈顶元素，模拟车厢从 C 驶入 B）。
2. 结果判定：所有目标匹配即成功

当外层循环遍历完所有目标（`i` 从 1 到 `n`），说明每一个需要从 B 驶出的车厢都通过栈的调度成功匹配 —— 此时输出 `Possible`，表示能得到指定顺序。

```cpp
#include <iostream>
using namespace std;

int n, top;            // n：车厢数量；top：栈顶指针
int a[1005];           // 存储目标出站序列（我们要判断是否合法）
int stack[1005];       // 模拟栈，代表火车轨道/站台

int main() {
    cin >> n;          // 输入车厢总数

    // 输入目标出站顺序（比如 3 1 2 这样的序列）
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    int c = 1;         // c 表示当前要入栈的车厢编号，从 1 开始

    // 依次判断目标序列的每一个数是否合法
    for (int i = 1; i <= n; i++) {

        // 当栈空 或者 栈顶不是当前需要的数字时
        // 就一直把新车厢压入栈中
        while (top == 0 || stack[top] != a[i]) {

            // 如果已经没有车厢可以入栈了，说明序列不合法
            if (c > n) {
                cout << "Impossible";
                return 0;
            }

            // 车厢 c 入栈，然后 c 自增，准备下一个车厢
            stack[++top] = c++;
        }

        // 走到这里说明：栈顶 == 目标数字 a[i]
        // 直接出栈，匹配成功
        --top;
    }

    // 所有目标都顺利匹配完成，说明出站序列合法
    cout << "Possible" << endl;

    return 0;
}
```

假设表达式中允许包含圆括号和方括号两种括号，其嵌套的顺序随意，如([]())或[([][])]等为正确的匹配，[(])或([]()或(()))均为错误的匹配 本题的任务是检验一个给定的表达式中的括号是否匹配正确 输入一个只包含圆括号和方括号的字符串，判断字符串中的括号是否匹配，匹配就输出“OK”，不匹配就输出“Wrong”

杨校老师课堂备战C++之数据结构中栈结构专题训练题讲解

金牌讲师

编程语言

算法

后端

本文讲解两种经典栈结构应用问题：括号匹配和火车车厢调度。括号匹配通过数组模拟栈实现左括号入栈、右括号匹配校验；火车调度问题利用栈的先进后出特性验证车厢出站顺序可行性。两种算法均采用栈结构解决匹配验证问题，适合数据结构学习者和算法竞赛选手参考。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

杨校老师课堂备战C++之数据结构中栈结构专题训练题讲解-腾讯云开发者社区-腾讯云

杨校老师课堂备战C++之数据结构中栈结构专题训练题讲解

杨校老师课堂备战C++之数据结构中栈结构专题训练题讲解

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐