括号匹配c数据结构

2018-11-30 20:15:54 huanhuan59 阅读数 475

1.在编写代码的时候,经常会用到两种括号:圆括号 “()” 和大括号 “{}” 。不管使用哪种括号,程序编译没有问题的其中一个重要因素就是所使用的括号是否能够匹配上.
在编写程序时,括号可以嵌套,即: “({()})” 这种形式,但 “({)” 或者 “({}” 都不符合要求。
括号匹配项目要求:给出任意搭配的括号,判断是否匹配。

2.设计思路

编写程序判断括号匹配问题的时候,使用结构会很容易:

  • 如果碰到的是左圆括号或者左大括号,直接压栈;
  • 如果碰到的是右圆括号或者右大括号,就直接和栈顶元素配对:如果匹配,栈顶元素弹栈;反之,括号不匹配;
  • 代码:
    #include <stdio.h>
    #include <string.h>
    int top = -1;//初始状态的空栈,或者说栈顶元素所在位置
    void push(char *a, int elem) {//入栈操作
    	a[++top] = elem;
    }
    void pop(char *a) {//出栈操作
    	if (top == -1) {
    		return;//空栈返回
    	}
    	top--;
    }
    char visit(char *a) {//
    	//调取栈顶元素,不等于出栈,如果栈为空,为使程序不发生错误,返回空字符
    	if (top != -1) {
    		return a[top];
    	}
    	else
    	{
    		return ' ';
    	}
    }
    int main() {
    	char a[80];//定义了一个数组,长度80
    	char bracket[100];
    	printf("请输入括号序列:");
    	scanf("%s", bracket);
    	getchar();
    	int  length = (int)strlen(bracket);
    	for (int i = 0; i < length; i++) {
    		//如果是左括号,直接压栈
    		if (bracket[i] == '(' || bracket[i] == '{') {
    			push(a, bracket[i]);
    		}
    		else
    		{
    			//右边括号的话要判断与栈顶元素是否匹配,若匹配则出栈运行,反之退出
    			if (bracket[i] == ')') {
    				if (visit(a) == '(') {
    					pop(a);
    				}
    				else
    				{
    					printf("括号不匹配");
    					return 0;
    				}
    			}
    			else
    			{
    				if (visit(a) == '{') {
    					pop(a);
    				}
    				else
    				{
    					printf("括号不匹配");
    					return 0;
    				}
    			}
    		}
    	}
    	//如果所有括号匹配完成,栈内为空,说明所有括号全部匹配成功
    	if (top != -1) {
    		printf("括号不匹配");
    	}
    	else {
    		printf("括号匹配");
    	}
    
    }

    运行:

2015-12-24 12:23:33 qq_26816591 阅读数 2951
//括号匹配:
#include<stdio.h>
#include<stdlib.h>
#define Stack_size 100
#define Stackincreament 10
typedef struct{
	char *base;
	int top;
	int stacksize;
}sqstack;
void initstack(sqstack &la)
{
	la.base=(char*)malloc(Stack_size*sizeof(char));
	la.stacksize=Stack_size;
	if(!la.base)
		exit(0);
	la.top=0;
}
void push(sqstack &L,char e)
{
	if(L.top>=L.stacksize)
	{
		L.base=(char*)realloc(L.base,(Stack_size+Stackincreament)*sizeof(char));	
		if(!L.base)
		   exit(0);
		L.stacksize+=Stackincreament;
	}
	L.base[L.top++]=e;
}
void pop(sqstack &l,char &e)
{
	if(l.top==0)
		return;
	e=l.base[--l.top];
	
	
}
int allbraket(char *str)
{

	sqstack s;
	char *p,ch;
	p=str;
	initstack(s);
	while(*p!='\0')
	{
		if(*p=='{'||*p=='['||*p=='(')
			push(s,*p);	
		else if(*p=='}'||*p==']'||*p==')')
		{
			if(s.top==0)
				return 0;
			else
			{	
				pop(s,ch);
				if(*p==')'&&ch!='(')
					return 0;
				if(*p=='}'&&ch!='{')
					return 0;
				if(*p==']'&&ch!='[')
					return 0;
			}
			
		}
		p++;
	}
	if(s.top==0)
		return 1;
	return 0;
	
}

int main()
{
	char str[20];
	gets(str);	
	if(allbraket(str))
		printf("括号匹配\n");
	else
		printf("括号不匹配\n");
	printf("\n");
	return 0;
}

2018-03-02 20:55:21 a1135004584 阅读数 3220

括号匹配的检验:

    eg: [([][][)]]    不匹配

        [([][])] 匹配

思路:  

0x0.首先建立两个栈,并对其初始化     

0x1.对表达式进行遍历,将相邻两个不能匹配的入栈到栈A,然后检测栈空间A是否为偶数,如果是表明有存在的可能,如果不是则提示不匹配。

0x2.检测栈空间A是否为偶数,如果是表明有存在的可能,如果不是则提示不匹配遍历栈A,将不匹配的入栈到栈B,如果匹配则判断是否是最后两个元素,如果是表明匹配

0x3.判断出栈前的A和栈B长度是否相等,如果相等表明不匹配。

0x4.栈A和栈B互换,重复步骤0x2,直到都为空.


运行截图:


代码:

Stack.h

#ifndef _STACK_H_
#define _STACK_H_

#include <stdbool.h>
#define STACK_INIT_SIZE 100 //栈控件初始化大小
#define STACK_INCREMENT 10 //栈控件增量

typedef struct{
    void * base;//栈底
    void * top;//栈顶
    int stackSize;//当前已经分配的存储空间
    int elementLength;
}SqStack;

typedef enum{
    FAILED,SUCCESS
}Status;

Status initStack(SqStack * pStack,int elength);

void destroyStack(SqStack * pStack);
void clearStack(SqStack * pStack);//将栈置空
bool stackIsEmpty(SqStack * pStack);
int stackLength(const SqStack * pStack);
void * getTop(SqStack * pStack);
void push(SqStack * pStack,void *data);//压栈
void pop(SqStack * pStack,void *data);//出栈,若不空删除栈顶元素并将其值返回

void * get(SqStack * pStack,int i);//获取栈的第i个位置的元素

/**
 * 输出栈中每个元素,如果direction为正则从头到尾输出,反之从尾到头输出.
 * @param pStack
 * @param pfun
 * @param direction
 */
void stackTraverse(SqStack * pStack,void(*pfun)(void *),int direction);

#endif


Stack.c

#include <malloc.h>
#include <memory.h>
#include <assert.h>
#include "Stack.h"

Status initStack(SqStack * pStack,int elength)
{

    pStack->base = malloc((size_t) (elength * STACK_INIT_SIZE));
    if(!pStack->base)//如果分配内存失败
        return FAILED;

    pStack->elementLength = elength;
    pStack->top = pStack->base;
    pStack->stackSize = STACK_INIT_SIZE;

    return SUCCESS;
}

void destroyStack(SqStack * pStack)
{
    if(pStack)
    {
        free(pStack->base);
        pStack->base = NULL;
        pStack->top = NULL;
        pStack->stackSize = 0;
    }

}

void clearStack(SqStack * pStack)//将栈置空
{
    if(pStack)
        pStack->top = pStack->base;
}

bool stackIsEmpty(SqStack * pStack)
{
    if(pStack)
    {
        if(pStack->top == pStack->base)
            return true;
        else
            return false;
    }

    return false;
}

/**
 * 返回栈当前长度
 * 用栈顶减去栈底除以单个元素大小即可.
 * @param pStack
 * @return
 */
int stackLength(const SqStack * pStack)
{
    return (int) (pStack->top - pStack->base)/pStack->elementLength;
}

void * getTop(SqStack * pStack)
{
    if(pStack->top == pStack->base)
        return NULL;
    else
        return pStack->top;
}

void push(SqStack * pStack,void *data)//压栈
{

    if((pStack->top - pStack->base)/pStack->elementLength >= pStack->stackSize)
    {
        pStack->base =
                realloc(pStack->base,
                        (size_t) ((pStack->stackSize + STACK_INCREMENT)*pStack->elementLength));

        assert(pStack->base != NULL);
        pStack->top = pStack->base+pStack->stackSize*pStack->elementLength;
        pStack->stackSize += STACK_INCREMENT;
    }
    memcpy(pStack->top, data, (size_t) pStack->elementLength);

    pStack->top = pStack->top+pStack->elementLength;
}

void pop(SqStack * pStack,void *data)//出栈,若不空删除栈顶元素并将其值返回
{
    if(pStack->top != pStack->base)
    {
        pStack->top -= pStack->elementLength;

        if(data)
            memcpy(data,pStack->top,(size_t)pStack->elementLength);
    }
}


void * get(SqStack * pStack,int i)//获取栈的第i个位置的元素
{
    void * pn = NULL;

    if(stackLength(pStack) != 0)
        pn = &pStack->base[i];

    return pn;
}


/**
 *
 * @param pStack
 * @param pfun
 * @param direction 遍历方向
 * @param isHex 是否是16进制
 */
void stackTraverse(SqStack * pStack,void(*pfun)(void *),int direction)
{
    void * pd = NULL;
    if(direction > 0)
    {
        pd = pStack->base;

        while(pd < pStack->top)
        {
            pfun(pd);
            pd += pStack->elementLength;
        }
    }else{
        pd = pStack->top;

        while(pd > pStack->base)
        {
            pd -= pStack->elementLength;
            pfun(pd);
        }
    }

}

main5.c

#include <stdio.h>
#include <stdlib.h>
#include "Stack.h"

bool signEqual(char * c1,char * c2);

/**
 * 括号匹配检验
 * @return
 */

int main(void) {
    SqStack stack,stack2,staTemp;
    initStack(&stack, sizeof(char));
    initStack(&stack2, sizeof(char));
    printf("请输入需要检测的字符串,#结尾:");
    char c, temp;

    scanf("%c", &c);
    //[([][][)]]
    //[][][
    //检测括号是否匹配.

    while (c != '#')
    {
        if(c == '(' || c == '[' || c==')' || c==']')
        {
            scanf("%c",&temp);

            if(signEqual(&c,&temp))//如果匹配
            {
                scanf("%c",&c);
            }else{
                push(&stack,&c);
                c = temp;
            }
        }else if(c !='#'){
            printf("表达式中只允许包含[]()两种括号!\n");
            exit(1);
        }
    }

    int len,len2;
    while(!(stackIsEmpty(&stack) && stackIsEmpty(&stack2)))
    {

        len = stackLength(&stack);

        if(len%2 == 0)//为偶数対表明存在正确匹配的可能
        {
            pop(&stack,&c);
            do
            {
                pop(&stack,&temp);
                if(signEqual(&c,&temp))
                {
                    if(len == 2)
                    {
                        printf("表达式括号匹配!\n");
                        exit(1);
                    }
                    pop(&stack,&c);
                }else{//不匹配
                    if(len == 2)
                    {
                        printf("表达式括号不匹配!\n");
                        exit(1);
                    }
                    push(&stack2,&c);
                    c = temp;
                }
            }while(!stackIsEmpty(&stack));//如果栈不空

            push(&stack2,&c);//将剩下的一个入栈
        }else{
            printf("表达式括号不匹配!\n");
            exit(1);
        }

        len2 = stackLength(&stack2);
        if(len == len2){
            printf("表达式括号不匹配!\n");
            exit(1);
        }

        staTemp = stack;//交换顺序
        stack = stack2;
        stack2 = staTemp;
    }

    return 0;
}




/**
 * 判断符号1和符号二是否匹配
 * @param c1
 * @param c2
 * @return
 */
bool signEqual(char * c1,char * c2)
{
    if(*c1 == '[')
    {
        if(*c2 == ']')
            return true;
        else
            return false;
    }else if(*c1 == '(')
    {
        if(*c2 == ')')
            return true;
        else
            return false;
    }else if(*c1 == ']')
    {
        if(*c2 == '[')
            return true;
        else
            return false;
    }else if(*c1 == ')')
    {
        if(*c2 == '(')
            return true;
        else
            return false;
    }
        return false;
}
2017-04-21 18:13:38 qq_29721419 阅读数 5065

数据结构——栈实现括号匹配

真正学习之后,才发现那些所谓的大婶不过是多用功了些。不知道以前为什么不亲自动手做做,原来这么简单。敲打
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
/**栈的链式存储**/
typedef struct Data{
	char c;
};
typedef struct Stack{
	Data data;
	Stack *top;	//指向栈顶元素
};
/**初始化空栈**/
void InitStack(Stack *S){
	S->top = NULL;
}
/**判断是否为空栈**/
int StackEmpty(Stack S){
	//为空返回1否则返回0
	if(S.top==NULL) return 1;
	else return 0;
}
/**返回栈顶元素**/
void GetTop(Stack S,Data *d){
	if(StackEmpty(S)==1)
		printf("It's an empty stack!");
	else{
		d->c = S.top->data.c;
	}
}
/**向栈顶插入新元素 入栈**/
void PushStack(Stack *S,Data d){
	Stack* p = (Stack *)malloc(sizeof(Stack));
	p->data.c = d.c;
	p->top = S->top;
	S->top = p;
}
/**从栈顶删除元素 出栈**/
void PopStack(Stack *S,Data *d){
	if(StackEmpty(*S)==1){
		printf("It's an empty stack!\n");
	}else{
		Stack *p = S->top;
		S->top = p->top;
		d->c = p->data.c;
	}
}
/**清空栈**/
void ClearStack(Stack *S){
	if(StackEmpty(*S)==1){
		printf("It's already an empty stack!\n");
	}else{
		S->top = NULL;
	}
}
/**打印栈内信息**/
void PrintStack(Stack S){
	if(StackEmpty(S)==1){
		printf("It's an empty stack!\n");
	}else{
		printf("name----age\n");
		while(S.top!=NULL){
			printf("%s\n",S.top->data.c);
			S.top = S.top->top;
		}
	}
}
/**检查右括号与栈顶元素是否匹配**/
int Match(Data r,Data s){
	//匹配成功返回1
	if(r.c==')'&&s.c=='('){
		return 1;
	}else if(r.c=='}'&&s.c=='{'){
		return 1;
	}else if(r.c==']'&&s.c=='['){
		return 1;
	}else{
		return 0;
	}
}
/**括号匹配**/
void CheckMatch(char *m,Stack *S){
	Data r,s;
	while(*m){
		switch (*m){
		case '(':
		case '{':
		case '[':
			s.c = *m;
			PushStack(S,s);
			*m++;
			break;
		case ')':
		case '}':
		case ']':
			if(StackEmpty(*S)){
				printf("Location %s can't match!\n",*m);
				return;
			}
			GetTop(*S,&s);
			r.c = *m;
			if(Match(r,s)){
				PopStack(S,&s);
				*m++;
			}else{
				printf("Location %c can't match!\n",*m);
				return;
			}
		default:
			*m++;
		}
	}
	if(StackEmpty(*S)){
		printf("Match successfully!\n");
	}else{
		printf("Can't match!Lack of right bracket!\n");
	}
}
void main(){
	char d[12];
	Stack S;
	char *p;
	printf("Input your expression:");
	gets(d);
	p = d;	//指向表达式
	InitStack(&S);
	CheckMatch(p,&S);
	system("pause");
}
2015-09-13 20:50:58 u012965373 阅读数 20188
#include <stdio.h>
#include <stdlib.h>
#define STACKINCREAMENT 10
#define STACK_INIT_SIZE 100
#define OVERFLOW -2
#define OK 1
#define ERROR 0
typedef int status;
typedef char SElemtype;
typedef struct
{
	SElemtype *base;
	SElemtype *top;
	status stacksize;
}sqstack;

//初始化栈
status Init(sqstack *s)
{
	s->base = (SElemtype *)malloc(STACK_INIT_SIZE * sizeof(SElemtype));
	if(!s->base) 
			exit(OVERFLOW);
	s->top = s->base;
	s->stacksize = STACK_INIT_SIZE ;
	return OK;
}

//获取栈顶元素
status Gettop(sqstack *s, SElemtype e)
{
	if(s->top == s->base) 
			return ERROR;
	e = *(s->top-1);
	return OK;
}

//压栈
status push(sqstack *s, SElemtype e)
{
	if(s->top - s->base >= s->stacksize)
	{
      s->base = (SElemtype *)realloc(s->base, (s->stacksize + STACKINCREAMENT) * sizeof(SElemtype));
	  if(!s->base)
			  exit(OVERFLOW);
      s->top = s->base + s->stacksize;
	  s->stacksize += STACKINCREAMENT;
	}
	*s->top++ = e;
	return OK;
}

//出栈
status pop(sqstack *s, SElemtype *e)
{
		if(s->top == s->base) 
				return ERROR;
		*e=*--s->top;
		return OK;
}

//判断是否为空栈
status stackempty(sqstack *s)
{
		if(s->top==s->base)
			return OK;
		return ERROR;
}

//清空栈
status clearstack(sqstack *s)
{
		if(s->top == s->base) 
				return ERROR;
		s->top = s->base;
		return OK;
}

//括号匹配算法
status Parenthesis_match(sqstack *s,char *str)
{
		int i=0, flag=0;
		SElemtype e;
		while(str[i] != '\0')
		{
			switch(str[i])
			{
				case '(':
						push(s,str[i]);
						break;
				case '[':
						push(s,str[i]);
						break;
				case ')':
						{
						  pop(s,&e);
						  if(e != '(') 
								  flag=1;
						}
						break;
				case ']':
						{
						  pop(s,&e);
						  if(e!='[')
								  flag=1;
						}
						break;
				default:
						break;
			}
			if(flag)
					break;
			i++;
	}

   if(!flag && stackempty(s))
   		printf("括号匹配成功!\n");
   else
   		printf("括号匹配失败!\n");
   return OK;
}

int main()
{
	char str[100], enter;
	sqstack s;
	Init(&s);
	printf("请输入字符串:\n");
	scanf("%s",str);
	scanf("%c",&enter);
	Parenthesis_match(&s,str);
    return 0;
}