括弧匹配检验

题目描述

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

现在的问题是，要求检验一个给定表达式中的括弧是否正确匹配？

输入一个只包含圆括号和方括号的字符串，判断字符串中的括号是否匹配，匹配就输出 “OK” ，不匹配就输出“Wrong”。输入一个字符串：［（［］［］）］，输出：OK。

输入

输入仅一行字符（字符个数小于255）。

输出

匹配就输出 “OK” ，不匹配就输出“Wrong”。

样例

输入数据 1

[(])

输出数据 1

Wrong

原题链接

这个问题可以使用栈来实现括号匹配的检验。具体的步骤如下：

1. 遍历输入的字符串，对于每一个字符：
   • 如果是左括号（即'('或'['），将其入栈；
   • 如果是右括号，且栈为空，则说明不匹配，输出"Wrong"；
   • 如果是右括号，且栈顶元素与当前字符匹配（即栈顶是'('且当前字符是')'，或者栈顶是'['且当前字符是']'），则出栈；
   • 其他情况，说明不匹配，直接输出"Wrong"。
2. 最后检查栈是否为空，若为空则输出"OK"，否则输出"Wrong"。

以下是C++代码：

#include<bits/stdc++.h>

using namespace std;

bool isValid(string s) {
    stack<char> st;

    for (char c : s) {
        if (c == '(' || c == '[') {
            st.push(c);
        } else {
            if (st.empty()) {
                return false;
            }

            char top = st.top();
            if ((top == '(' && c == ')') || (top == '[' && c == ']')) {
                st.pop();
            } else {
                return false;
            }
        }
    }

    return st.empty();
}

int main() {
    string input;
    cin >> input;

    if (isValid(input)) {
        cout << "OK" << endl;
    } else {
        cout << "Wrong" << endl;
    }

    return 0;
}

后言

你觉得需要后言吗