数据结构-栈\队列：括号匹配

题目: 1229: 括号匹配
LeetCode同题： 20. 有效的括号

image.png

用栈实现的思路是正确的，默认输入的字符串长度在100以内
在LeetCode上提交运行时将 char* str 改为 string，修改maxsize即可

使用C++标准库协助实现如下

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

using namespace std;

bool bracketCheck(string str) {
    stack<char> stack;
    int len = str.size(); // 使用变量存储可以减少每次对函数的调用
    if (len == 0) return false;
    int i = 0;
    while (i < len) {
        if ('(' == str[i] || '[' == str[i] || '{' == str[i]) {
            // 左括号直接入栈
            stack.push(str[i]);
        } else {
            if (stack.empty()) {
                // 栈空，匹配失败
                return false;
            }
            // 判括号是否匹配
            if (str[i] == ')' && stack.top() != '(') return false;
            if (str[i] == ']' && stack.top() != '[') return false;
            if (str[i] == '}' && stack.top() != '{') return false;
            stack.pop();
        }
        i++;
    }
    return stack.empty(); // 检索完成后，若栈为空，说明匹配成功
}

int main() {
    string str;
    while (cin >> str) {
        // 匹配括号
        bracketCheck(str) ? printf("yes\n") : printf("no\n");
    }
    return 0;
}

手动实现栈 代码如下

//
// Created by zhixiang.xiao on 2020/9/10.
//

/**
 * 题目: 括号匹配 http://www.pipioj.online/problem.php?id=1229
 */

#include <stdio.h>

#define MaxSizeBSqStack 50  // 栈的最大容量

// 静态数组做栈的结构
typedef struct {
    char data[MaxSizeBSqStack];
    int top; // 栈顶指针
} BSqStack;

// 初始化栈
void initBSqStack(BSqStack &S) {
    S.top = -1; // 初始时设置栈顶为 -1
}

// 判满
bool isBSqStackFull(BSqStack S) {
    return S.top == MaxSizeBSqStack;
}

// 判空
bool isBSqStackEmpty(BSqStack S) {
    return -1 == S.top;
}

// 入栈
bool push2BSqStack(BSqStack &S, char elem) {
    if (isBSqStackFull(S)) return false; // 栈满
    S.data[++S.top] = elem;
    return true;
}
// 出栈
bool popBSqStack(BSqStack &S,char &val){
    if(isBSqStackEmpty(S)) return false; // 栈空
    val = S.data[S.top--];
    return true;
}

/**
 *
 * @param str : 括号字符串
 * @return : 是否匹配成功
 */
bool bracketCheck(char *str){
    if (NULL == str || '\0' == str[0]){  // 字符串为空
        return false;
    }
    BSqStack stack;
    initBSqStack(stack);
    int i = 0;
    char val;
    while ('\0' != str[i]){
        if ('(' == str[i] || '[' == str[i] || '{' == str[i]){
            // 左括号直接入栈
            push2BSqStack(stack,str[i]);
        } else {
            if (isBSqStackEmpty(stack)){
                // 栈空，匹配失败
                return false;
            }
            popBSqStack(stack,val); // 栈顶元素
            // 判括号是否匹配
            if (str[i] == ')' && val != '(') return false;
            if (str[i] == ']' && val != '[') return false;
            if (str[i] == '}' && val != '{') return false;
        }
        i++;
    }
    return isBSqStackEmpty(stack); // 检索完成后，若栈为空，说明匹配成功
}

int main(){
    char str[100];

    while (gets(str)) {
//    gets(str); // 合法的括号串
        // 匹配括号
        bracketCheck(str) ? printf("yes\n") : printf("no\n");
    }
    return 0;
}

运行结果

image.png

参考文章：
std::stack - cppreference.com
std::map - cppreference.com