欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

20.有效的括号

程序员文章站 2022-07-15 12:38:37
...
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:
    Open brackets must be closed by the same type of brackets.
    Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

Example 1:
Input: "()"
Output: true

Example 2:
Input: "()[]{}"
Output: true

Example 3:
Input: "(]"
Output: false

Example 4:
Input: "([)]"
Output: false

Example 5:
Input: "{[]}"
Output: true

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-parenthese


思路:
用栈stack模拟过程,分为两种情况:
(1)如果栈为空,下一个待进入栈的字符括号若为左括号('(','{','['),则将它push进栈中,否则表示字符串是无效的。
(2)如果栈不为空,下一个待进入栈的字符括号若与栈顶字符括号匹配则将栈顶字符括号pop出去,若为左括号则push进栈,若为右括号则表示字符串是无效的。

 

#include <iostream>
#include <string>
#include <map>
#include <stack>

using namespace std;

class Solution {
public:
    bool isValid(string s) {
    	if (s == "") return true;
        map<char, char> is_pair;
        is_pair['('] = ')';
        is_pair['{'] = '}';
        is_pair['['] = ']';
        stack<char> st;
        for (int i = 0; i < (int)s.length(); i++) {
        	if ((int)st.size() == 0 || s[i] != is_pair[st.top()]) {
        		if (is_pair.find(s[i]) == is_pair.end()) return false;
        		st.push(s[i]);
			} else {
				st.pop();
			}
		}
		if ((int)st.size() == 0) return true;
		else return false;
    }
};

int main() {
	while (true) {
		string str;
		cin >> str;
		Solution solve;
		cout << solve.isValid(str) << endl;
	}

	return 0;
} 

 

相关标签: LeetCode刷题记录