面试经典150题 P20 有效的括号

---

时间轴

时间轴

2025-11-18

init

栈

---

题目：

P20 有效的括号

https://leetcode.cn/problems/valid-parentheses/description/?envType=study-plan-v2&envId=top-interview-150

栈的经典题目了，注意最后要判断栈是否为空，非空则是非法。代码：

#include <string>
#include <stack>

using std::stack;
using std::string;

class Solution {
    public:
	bool isValid(string s)
	{
		stack<char> st;
		char curr;

		for (char &ch : s) {
			if (ch == '(' || ch == '[' || ch == '{') {
				st.push(ch);
			} else if (!st.empty() && ch == ')') {
				curr = st.top();
				st.pop();
				if (curr != '(') return false;
			} else if (!st.empty() && ch == ']') {
				curr = st.top();
				st.pop();
				if (curr != '[') return false;
			} else if (!st.empty() && ch == '}') {
				curr = st.top();
				st.pop();
				if (curr != '{') return false;
			} else {
				return false;
			}
		}
		return st.empty();
	}
};

leetcode hot 100 rewrite

#include <string>
#include <stack>

using std::string;
using std::stack;

class Solution {
    public:
        bool isValid(string s)
        {
                // 1 <= s.length <= 104
                // s 仅由括号 '()[]{}' 组成
                stack<char> stk;
                char curr;

                for (char ch : s) {
                        if (ch == '(' || ch == '[' || ch == '{') {
                                stk.push(ch);
                        } else if (!stk.empty() && ch == ')') {
                                if (stk.top() != '(')
                                        return false;
                                stk.pop();

                        } else if (!stk.empty() && ch == ']') {
                                if (stk.top() != '[')
                                        return false;
                                stk.pop();
                        } else if (!stk.empty() && ch == '}') {
                                if (stk.top() != '{')
                                        return false;
                                stk.pop();
                        } else {
                                return false;
                        }
                }

                return stk.empty();
        }
};