刷题 栈1(C)

刷题-栈1 （C语言）

题目描述：

给定一个只包括 ‘('，')'，'{'，'}'，'['，']’ 的字符串，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

示例 1: 输入: “()” 输出: true

示例 2: 输入: “()[]{}” 输出: true

示例 3: 输入: “(]” 输出: false

示例 4: 输入: “([)]” 输出: false

示例 5: 输入: “{[]}” 输出: true

解题思想：

  • 根据字符串的长度建立一个顺序存储结构的栈
  • 逐一读取字符串中的字符，只要是左括号都压入栈内
  • 若遇到右括号则与栈顶元素相比较，若不匹配则返回false，若匹配，则出栈栈顶左括号，继续读取字符
  • 最后返回栈顶序号的取反值：若还有左括号在栈中即为false，若栈为空为true

代码：

bool isValid(char * s){
    int top = 0;
    int i;

    char* p = (char*)malloc(strlen(s) + 1);
    for(i = 0;i < strlen(s);i++)
    {
        if((s[i] == '(') || (s[i] == '[') || (s[i] == '{')){
             p[top++] = s[i];
        }
        else{
            if((--top) < 0)//top先减一，指向栈顶元素
                return false;
            if(s[i] == ')' && p[top] != '(')
                return false;
            if(s[i] == ']' && p[top] != '[')
                return false;
            if(s[i] == '}' && p[top] != '{')
                return false;
        }
           
    }
    free(p);
    return !top;
}
5 Jan 2020