平武建站

20.有效的括号-C语言-创新互联

题目来源：力扣

专注于为中小企业提供成都网站设计、成都网站制作服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业铁西免费做网站提供优质的服务。我们立足成都，凝聚了一批互联网行业人才，有力地推动了1000多家企业的稳健成长，帮助中小企业通过网站建设实现规模扩充和转变。

题目描述：

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

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

提示：

  • 1<= s.length<= 104
  • s仅由括号 '()[]{}'组成

思路：

根据s当前位置字符来判断操作，若s为左括号，入栈，若s为右括号，取栈顶元素并且出栈，然后用栈顶元素和s比较，若匹配，则说明当前括号对应，程序继续执行，否则错误

代码：

typedef int STDataType;

typedef struct Stack {
	STDataType* a;
	int top;
	int capacity;
}ST;
void StackInit(ST* ps);//初始化
void StackDestory(ST* ps);//销毁
void StackPush(ST* ps,STDataType x);//入栈
void StackPop(ST* ps);//出栈
STDataType StackTop(ST* ps);//返回栈顶元素
void StackSize(ST* ps);//计算数据个数
bool StackEmpty(ST* ps);//判断是否为空
void StackInit(ST* ps)//初始化
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL) {
		printf("malloc fail\n");
		exit(-1);
	}
	ps->capacity = 4;
	ps->top = 0;
}
void StackDestory(ST* ps)//销毁
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}
void StackPush(ST* ps, STDataType x)//入栈
{
	assert(ps);
	if (ps->top == ps->capacity) {//满了扩容
		STDataType* tmp= (STDataType*)realloc(ps->a,ps->capacity*2*sizeof(STDataType));
		if (tmp == NULL) {
			printf("realloc fail\n");
			exit(-1);
		}
		else {
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void StackPop(ST* ps)//出栈
{
	assert(ps);
	assert(ps->top>0);
	ps->top--;
}
STDataType StackTop(ST* ps)//返回栈顶元素
{
	assert(ps);
	assert(ps->top >0);
	return ps->a[ps->top - 1];
}
void StackSize(ST* ps)//计算数据个数
{
	assert(ps);
	return ps->top;
}
bool StackEmpty(ST* ps)//判断是否为空
{
	assert(ps);
	return ps->top == 0;
}
bool isValid(char * s){
      ST st;
      char top;
      StackInit(&st);
      while(*s != '\0'){
          switch(*s){
            case '(':
            case '{':
            case '[':
                 StackPush(&st,*s);
                 s++;
                 break;
            case ')':
            case '}':
            case ']':
            if(StackEmpty(&st)){
                StackDestory(&st);
                return false;
            }
               top = StackTop(&st);
               StackPop(&st);
               if((*s==')' && top != '(') ||
               (*s==']' && top != '[') ||
               (*s=='}' && top != '{'))
               {
                   StackDestory(&st);
                   return false;
               }else{
                   s++;
               }
               break;
               default:
               break;
         }
       }
     bool ret =StackEmpty(&st);
      StackDestory(&st);
      return ret;
}

注意：1.返回之前要释放内存，否则会有内存泄漏情况（这是好的习惯，与题无关）

2.如果只输入左括号，我们就无法取栈顶元素然后比较，所以结尾要加上判空，如果不为空，说明栈内还有左括号，没有匹配完成，返回false

3.如果只输入右括号，会导致程序出错，所以在取栈顶元素前要判断栈是否为空，为空则说明栈内无对应左括号，返回flase

4.使用完一次s后要记得s++

运行结果：

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


当前文章：20.有效的括号-C语言-创新互联
文章网址：http://pwwzsj.com/article/dihjjd.html

其他资讯