栈的应用很广泛,在本节中我们将使用栈来解决一个括号匹配的问题。对于给定的一个运算表达式,校验其括号匹配是否正确,例如:
这是一个正确的括号匹配表达式。我们抛开数值计算部分,只看括号匹配:
下面我们使用栈来完成对给定表达式校验括号的问题。栈的设计和实现与上一节相同。写一个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
Copyright © 2015-2023 问渠网 辽ICP备15013245号