leetcode20：有效的括号

题目链接

leetcode

题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s，判断字符串是否有效。
有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

C++ 代码

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

/*
    栈是一种先进后出的数据结构，处理括号问题尤其有用。
	遇到左括号入栈，遇到右括号去栈中找最近的左括号，是否匹配。

    时间复杂度：O(n)
        其中 n 是字符串的长度。
        遍历字符串一次，对于每个字符，操作的时间复杂度是 O(1)。
    空间复杂度：O(n)
        在最坏的情况下，字符串只包含右括号，栈将包含所有 n 个字符。
*/
class Solution {
public:
    bool isValid(string s) {
        stack<int> stk;
        for (const char& c : s) {
            if (c == '(' || c == '{' || c == '[') {
                stk.push(c);
            } else if (c == ')' || c== '}' || c == ']') {
                // 最近的左括号不匹配
                if (stk.empty() || stk.top() != getLeft(c)) {
                    return false;
                }
                stk.pop();
            }
        }

        // 所有的左括号是否都匹配
        return stk.empty();
    }

    char getLeft(char c) {
        if (c == ')') return '(';
        else if (c == '}') return '{';
        else if (c == ']') return '[';
        return ' ';
    }
};

int main() {
    Solution solution;
    vector<string> s_cases = {
        "()",
        "()[]{}",
        "(]",
        "([])"
    };

    for (const string& s : s_cases) {
        bool result = solution.isValid(s);

        cout << "Input: \"" << s << "\"\n";
        cout << "Output: " << (result ? "true" : "false") << "\n";
    }

    return 0;
}