数据结构重读 – 括号匹配

检查括号匹配,形如如下的字符串:

[([][])] 认为是匹配的。

而[(][])这种认为是不匹配的。

算法很简单,就是栈:

(1)如果是左括号([{等,直接入栈(使得原有在栈中的所有未消解的期待括号的紧迫级别下降一位)。

(2)如果是右括号,比如],则栈顶要么是与它匹配的左括号如[,否则就是括号不匹配。

(3)如果所有字符串都处理完,栈是空的,则是匹配的,否则不匹配。

代码如下:

// 1 for succ, 0 for false
int kuohao(char* str, struct Stack* stack)
{
	int n = strlen(str);
	int i = 0;
	// Each char
	for(i=0;i<n;i++)
	{
		char c = str[i];
		char top;
		// If left kuohao, push
		if(c=='(' || c=='[' || c=='{')
		{
			stack_push(stack, c);
			continue;
		}
		// Switch for righ kuohao or err char
		stack_top(stack, &top);
		switch(c)
		{
			case ')':
				if(top=='(')
				{
					stack_pop(stack, &top);
				} else
				{
					return 0;
				}
				break;
			case ']' :
				if(top=='[')
				{
					stack_pop(stack, &top);
				} else
				{
					return 0;
				}
				break;
			case '}' :
				if(top=='{')
				{
					stack_pop(stack, &top);
				} else
				{
					return 0;
				}
				break;
			default:
				return 0;
				break;
		}
	}
	// Empty for succ
	if(stack_isempty(stack))
	{
		return 1;
	} else
	{
		return 0;
	}
}

Leave a Reply

Your email address will not be published.