堆栈的实际使用

堆栈在现代应用程序中有很多用途。无论是在浏览器历史记录中，还是在流行的开发术语堆栈跟踪中，堆栈的使用无处不在。现在，我们将尝试使用堆栈来解决一个实际问题。

嵌套括号匹配

在求解数学表达式时，我们首先要考虑的是括号嵌套的正确性。如果括号嵌套不当，就可能无法计算，或者计算错误。让我们来看几个例子：

image 2023 11 07 18 44 38 280

从前面的表达式来看，只有第一个表达式是正确的，其他两个表达式都不正确，因为括号没有正确嵌套。为了识别括号是否嵌套，我们可以使用堆栈来实现求解。下面是实现的伪算法：

valid = true
s = empty stack
for (each character of the string) {
    if(character = ( or { or [ )
        s.push(character)
    else if (character = ) or } or ] ) {
        if(s is empty)
            valid = false
            last = s.pop()
        if(last is not opening parentheses of character)
            valid = false
    }
}
if(s is not empty)
valid = false
bash

如果我们看一下伪代码，它看起来非常简单。我们的目标是忽略字符串中的任何数字、操作数或空格，只考虑括号、大括号和小括号。如果它们是开括号，我们就将其推入堆栈。如果它们是闭合括号，我们将弹出堆栈。如果弹出的括号不是我们要匹配的开括号，那么它就是无效的。在循环结束时，如果字符串有效，堆栈应该为空。但如果堆栈不为空，那么就有多余的括号，所以字符串无效。现在，让我们把它转换成一个程序：

Unresolved include directive in modules/ROOT/pages/ch04/ch4-06.adoc - include::example$Chapter04/4.php[]
php

现在，让我们运行前面讨论过的三个例子：

Unresolved include directive in modules/ROOT/pages/ch04/ch4-06.adoc - include::example$Chapter04/4.php[]
php

这将产生以下输出结果，这正是我们想要的：

Expression is valid
Expression is not valid
Expression is not valid
bash