试题请参见: https://oj.leetcode.com/problems/valid-parentheses/
题目概述
Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.
The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.
解题思路
数据结构典型的例题, 当我们读到左边的括号(包括'(‘, ‘[‘和'{‘)时, 压入堆栈. 当读取到右边的括号时, 取堆栈顶端的元素进行比对, 若不匹配, 则说明表达式中的括号也无法配对.
遇到的问题
[][的情况 当字符串读取结束后, 堆栈中元素可能不为空, 此时的括号一定无法完全匹配.
[]]的情况 当读取到第2个]时, 我们会调用stack.top()函数. 但此时堆栈为空, 因此会出现Segment Fault异常.
源代码class Solution {public:bool isValid(std::string s) {for ( auto itr = s.begin(); itr != s.end(); ++ itr ) {if ( *itr == ‘(‘ || *itr == ‘[‘ || *itr == ‘{‘ ) {st.push(*itr);} else if ( *itr == ‘)’ || *itr == ‘]’ || *itr == ‘}’ ) {if ( st.empty() ) {return false;}char topChar = st.top();if ( *itr == ‘)’ && topChar != ‘(‘ ) {return false;} else if ( *itr == ‘]’ && topChar != ‘[‘ ) {return false;} else if ( *itr == ‘}’ && topChar != ‘{‘ ) {return false;}st.pop();}}if ( st.empty() ) {return true;} else {return false;}}private:std::stack<char> st;};
，我想一个人旅行，背上简单的行囊，踏上行程，
