括号匹配问题（c语言实现）

• • 一、前言
  • 二、例题

用栈实现括号匹配：

依次扫描所有字符，遇到左括号入栈，遇到右括号则弹出栈顶元素检查是否匹配。

匹配失败的情况：

• 左括号单身
• 右括号单身
• 左右括号不匹配

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

有效字符串需满足：

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

示例1:

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

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

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

提示：

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

代码：

#include
#define maxSize 10000

typedef struct
{
	char data[maxSize];
	int top;
}SqStack;


void initStack(SqStack& s)
{
	s.top = -1;
}

int getElem(SqStack s, char& ch)
{
	if (s.top == -1)//栈为空
	{
		return 0;
	}
	ch = s.data[s.top];
	return 1;
}

int isEmpty(SqStack s)
{
	if (s.top == -1)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

int Push(SqStack& s,char x)
{
	if (s.top == maxSize - 1)//判断栈满
	{
		return 0;
	}
	++s.top;
	s.data[s.top] = x;
	return 1;
}

int Pop(SqStack& s)
{
	if (s.top == -1)//判断栈空
	{
		return 0;
	}
	--s.top;
	return 1;
}
int main()
{
	SqStack st;
	initStack(st);
	char s[10000],ch;
	scanf("%s", s);
	int i = 0;
	while (s[i])
	{
		if (s[i] == ''' || s[i] == ''' || s[i] == '"' || s[i] == '"')
		{
			i++;
		}
		else
		{
			if (s[i] == '('||s[i]=='{'||s[i]=='[')
			{
				Push(st, s[i]);
			}
			else if (s[i] == ')')
			{
				getElem(st, ch);
				if (ch == '(')
				{
					Pop(st);
				}
				else
				{
					break;
				}
			}
			else if (s[i] == ']')
			{
				getElem(st, ch);
				if (ch == '[')
				{
					Pop(st);
				}
				else
				{
					break;
				}
			}
			else if (s[i] == '}')
			{
				getElem(st, ch);
				if (ch == '{')
				{
					Pop(st);
				}
				else
				{
					break;
				}
			}
		}
		i++;
	}
	if (isEmpty(st))
	{
		printf("true");
	}
	else
	{
		printf("false");
	}
	return 0;
}