P4818 括弧匹配检验（入门）

解题思路

1. 匹配的规律。 括号要"后出现的左括号先被匹配"，比如 ( [ ] ) 是正确的：先出现 ( 再出现 [，但 [ 先被 ] 匹配。这个"后进先出"的特点正好是栈的看家本领。可以把左括号想象成一摞盘子，最后放上去的盘子最先拿走。
2. 扫描字符串。 一个字符一个字符地看：
   • 遇到左括号 ( 或 [，把它压入栈；
   • 遇到右括号 ) 或 ]，先检查栈是不是空的：如果是空的，说明前面根本没有左括号来配它，直接判 Wrong；
   • 再检查栈顶是不是配对的左括号：) 必须配 (，] 必须配 [，如果栈顶是别的括号，也判 Wrong；
   • 配对成功，就把栈顶的左括号弹出。
3. 扫描结束还要检查。 如果整个字符串扫描完，栈里还留着没被弹出的左括号，说明有些左括号始终没找到右括号，输出 Wrong；只有栈恰好为空，才说明每一对括号都正确匹配，输出 OK。
4. 看例子。 输入 [(])：遇到 ] 时栈顶是 (，不配对，所以输出 Wrong。输入 ([][])，从头到尾都能配对且最后栈空，输出 OK。

参考代码

// 括弧匹配检验：用栈判断圆括号()和方括号[]是否匹配，后出现的左括号必须最先配到右括号
#include <iostream>
using namespace std;

int main() {
    char str[300];     // 输入的括号字符串
    char stack[300];   // 左括号栈
    int top = 0;
    cin >> str;
    for (int i = 0; str[i] != '\0'; i++) {
        char ch = str[i];
        if (ch == '(' || ch == '[') {   // 左括号入栈
            stack[top++] = ch;
        } else if (ch == ')') {
            if (top == 0 || stack[top - 1] != '(') {   // 栈空或栈顶不是左圆括号则错误
                cout << "Wrong" << endl;
                return 0;
            }
            top--;
        } else if (ch == ']') {
            if (top == 0 || stack[top - 1] != '[') {   // 栈空或栈顶不是左方括号则错误
                cout << "Wrong" << endl;
                return 0;
            }
            top--;
        }
    }
    if (top > 0) cout << "Wrong" << endl;   // 还有左括号没匹配上
    else cout << "OK" << endl;
    return 0;
}

复杂度分析

每个字符最多被压入栈一次、弹出一次，所以时间复杂度是 O(len)，len 是输入字符串的长度（小于 255）。空间上用一个长度 300 的数组当栈，是 O(len)。算法简单又高效。