数据结构实战

        栈的应用很广泛，在本节中我们将使用栈来解决一个括号匹配的问题。对于给定的一个运算表达式，校验其括号匹配是否正确，例如：

        这是一个正确的括号匹配表达式。我们抛开数值计算部分，只看括号匹配：

        下面我们使用栈来完成对给定表达式校验括号的问题。栈的设计和实现与上一节相同。写一个main函数来完成表达式括号匹配算法：

void free_char(char *ch)
{
	free(ch);
}

int main(int argc, char **args)
{
	char *str = (char *) malloc(200);
	do
	{
		printf("Please enter the expression(Enter \"exit\" to quit): ");
		scanf("%s", str);

		if (strcmp(str, "exit") == 0)
		{
			break;
		}

		//构建栈
		s_stack s;
		stack_init(&s, free_char);
		char *p = str;
		bool isValid = true;

		//遍历表达式
		while (*p != '\0')
		{
			//如果是左括号，入栈
			if (*p == '(' || *p == '[' || *p == '{')
			{
				char *ch = (char *) malloc(1);
				*ch = *p;
				stack_push(&s, ch);
			}
			//如果是右括号，出栈
			else if (*p == ')' || *p == ']' || *p == '}')
			{
				char *ch;
				if (s.ele_count == 0)
				{
					isValid = false;
					break;
				}

				stack_pop(&s, &ch);

				//左右括号匹配合法
				if ((*ch == '(' && *p == ')') || (*ch == '[' && *p == ']') || (*ch == '{' && *p == '}'))
				{
					free_char(ch);
				}
				//左右括号匹配非法
				else
				{
					free_char(ch);
					isValid = false;
					break;
				}
			}

			p++;

			if (*p == '\0' && s.ele_count > 0)
			{
				isValid = false;
				break;
			}
		}
		//销毁栈
		stack_destroy(&s);

		if (isValid)
		{
			printf("%s OK.\n", str);
		}
		else
		{
			printf("\"%s\" expression is invalid.\n", str);
		}
	}
	while (1);

	free(str);

	return 0;
}

        运行结果：

Please enter the expression(Enter "exit" to quit): {[(12+3)*5+23]/(3-1)+4}*(3+8)
{[(12+3)*5+23]/(3-1)+4}*(3+8) OK.
Please enter the expression(Enter "exit" to quit): {[(12+3)*5+23]/(3-1)+4}*(3+8)}       
"{[(12+3)*5+23]/(3-1)+4}*(3+8)}" expression is invalid.
Please enter the expression(Enter "exit" to quit): exit

        本例代码：

code path   chapter.02/e.g.2.2/

https       https://github.com/magicworldos/datastructure.git
git         git@github.com:magicworldos/datastructure.git
subverion   https://github.com/magicworldos/datastructure