给定一个只包括 '(',')','{','}','[',']' 的字符串, 判断字符串是否有效.
有效字符串需满足:
左括号必须用相同类型的右括号闭合.
左括号必须以正确的顺序闭合.
注意空字符串可被认为是有效字符串.
这是一个典型的用栈的思想的题目, 在解题过程中, 我的思路是如下几步:
1. 首先判断字符串的长度是否为空
2. 如果不为空, 获取字符串的长度 (strlen() 函数)并开辟一个动态的内存空间
3. 逐个扫描字符串的元素, 如果为左边的括号就将这个括号压进栈中, 如果为右边的括号, 解酒将栈顶元素弹出并判断是否与扫描到的右边括号匹配.
4. 在扫描完所有元素时一定要释放内存空间;
- bool isValid(char* s) {
- if(s == NULL)
- return false;
- int top = 0,i;
- char *stack = (char *)malloc(sizeof(char)*(strlen(s)+1));
- for(i=0;s[i]!='\0';i++)
- {
- if(s[i]=='(' || s[i]=='[' || s[i]=='{')
- {
- stack[++top] = s[i];
- }
- else if((s[i]==')'&& stack[top]=='(') || (s[i]==']' && stack[top]=='[') || (s[i]=='}' && stack[top]=='{'))
- {
- top--;
- }
- else
- return false;
- }
- if(stack != NULL)
- {
- free(stack);
- stack = NULL;
- }
- if(top == 0)
- return true;
- return false;
- }
来源: http://www.bubuko.com/infodetail-2988699.html