C++ 括号匹配问题：高效算法实现与解析

问题描述

假设表达式中允许包含圆括号和方括号两种括号，其嵌套的顺序随意，如'()' 或 '[[][]]' 等为正确的匹配，'[(])' 或 '(或(()))' 均为错误的匹配。

本题的任务是检验一个给定的表达式中的括号是否匹配正确。

输入描述

一行字符，只含有圆括号和方括号，个数小于255。

输出描述

匹配就输出一行文本“OK”，不匹配就输出一行文本“Wrong”。

样例

输入

[(])

输出

Wrong

代码实现

#include<iostream>
#include<stack>
using namespace std;

bool isMatched(string s) {
    stack<char> stk;
    for(int i=0; i<s.length(); i++) {
        if(s[i] == '(' || s[i] == '[') {
            stk.push(s[i]);
        } else if(s[i] == ')') {
            if(stk.empty() || stk.top() != '(') {
                return false;
            } else {
                stk.pop();
            }
        } else if(s[i] == ']') {
            if(stk.empty() || stk.top() != '[') {
                return false;
            } else {
                stk.pop();
            }
        }
    }
    return stk.empty();
}

int main() {
    string s;
    cin >> s;
    if(isMatched(s)) {
        cout << "OK" << endl;
    } else {
        cout << "Wrong" << endl;
    }
    return 0;
}

算法解析

1. 使用栈 (stack) 数据结构来存储未匹配的左括号。
2. 遍历字符串，遇到左括号就入栈，遇到右括号就出栈。
3. 出栈时，要判断栈是否为空，以及栈顶元素是否与当前的右括号匹配。
4. 遍历结束后，如果栈为空，则所有括号都匹配，输出“OK”；否则，存在不匹配的括号，输出“Wrong”。

总结

本文介绍了使用 C++ 代码解决括号匹配问题的方法，通过栈数据结构，可以高效地判断字符串中的括号是否匹配。

希望本文对您有所帮助。