PIPI:1036: 括号匹配(括号位序)

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

image.png

解题思路1: 为了保证顺序,使用两个栈来保存信息 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

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。