数据结构-栈\队列：1036: 括号匹配（括号位序）

题目：1036: 括号匹配
描述：PIPI给你一个合法的括号序列，希望跟你按左括号下标递增顺序给出每对括号在序列中的下标。（下标从1开始）
输入: 第一行包括一个只包含'(',')'的字符串，保证输入的括号匹配序列合法，长度不超过100000
输出: 按左括号下标递增顺序给出每对括号在序列中的下标。

image.png

解题思路: 为了保证顺序，使用两个栈来保存信息 bStack: 保存当前读取的括号位置； pStack: 保存括号对位序的栈

1. 为了保证顺序，从字符串尾往头读取；
2. 读取到右括号，直接入bStack;
3. 读取到左括号，将当前左括号的位置和 bStack 栈顶(即相应右括号位置)存入 pStack 中
4. 完成后将 pStack 栈中位置信息对依次输出即可

• [注]： 因是从尾往头按右括号位序依次将括号对位序存入pStack中，可保证是按左括号正序输出
• [注]： 默认输入为正确的输入，未做错误处理

代码实现

/**
 * 题目：括号匹配（括号位序）: http://pipioj.online/problem.php?id=1036
 */

#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

// 保存位序标号的节点
typedef struct {
    int left, right;
} PosNode;

// 依次打印括号对位序
void showBracketPosition(stack<PosNode> stack) {
    PosNode node;
    while (!stack.empty()) {
        node = stack.top();
        printf("%d %d\n", node.left, node.right);
        stack.pop(); // 打印完一组即移除
    }
}
/**
 * 计算一组正确包含左右()对的下标
 * 为了保证顺序，使用两个栈来保存信息 bStack: 保存当前读取的括号位置； pStack: 保存括号对位序的栈
 *      实现思路：
 *          1. 为了保证顺序，从字符串尾往头读取；
 *          2. 读取到右括号，直接入bStack;
 *          3. 读取到左括号，将当前左括号的位置和 bStack 栈顶(即相应右括号位置)存入 pStack 中
 *          4. 完成后将 pStack 栈中位置信息对依次输出即可
 *          [注]： 因是从尾往头按右括号位序依次将括号对位序存入pStack中，可保证是按左括号正序输出
 *          [注]： 默认输入为正确的输入，未做错误处理
 * @param str ：输入字符串
 * @return
 *
 */
bool getBracketPosition(string str) {
    int len = str.length();
    if (len == 0) return false;
    int i = len - 1;
    stack<int> bStack; // 存放括号位置的栈
    stack<PosNode> pStack; // 存放匹配括号的位置信息栈
    char RBrackt = ')';
    PosNode node;
    while (i >= 0) {
        if (RBrackt == str[i]) {
            // 右括号位置直接入栈，
            // 注意：此处直接保存字符串中下标，匹配时与右括号位置一同+1计算
            bStack.push(i);
        } else {
            node.right = bStack.top() + 1; // 右括号为栈顶信息
            node.left = i + 1;   // 左括号为当前读取位置
            pStack.push(node); // 位置信息入栈
            bStack.pop(); // 移除已匹配成功栈顶
        }
        i--;
    }
    showBracketPosition(pStack);
}

int main() {
    string str;
    while (cin >> str) { // 循环读入字符串
        getBracketPosition(str);
    }
}

运行结果

image.png