栈的应用
![](/images/stack-yy.png)
栈的应用
苏丙榅在上一个章节中为大家详细讲解了栈的特点和实现,关于栈的现实应用有很多,下面再来给说几个比较常见的案例:括号匹配问题
、中缀表达式转后缀表达式
、后缀表达式的计算
。
1. 括号匹配问题
括号在使用的时候都是成对出现的,分为左右两部分。很多时候我们都需要验证给定的字符串中的括号是否正确匹配,通常包括以下三种类型:
- 小括号 -
()
- 大括号 -
{}
- 中括号 -
[]
如果使用栈来处理这个问题,具体的操作步骤如下:
- 初始化栈:创建一个空栈,用于
存放左括号
。 - 遍历字符串:逐个字符扫描字符串。
- 如果遇到左括号(
(
、{
、[
),将其压入栈中。 - 如果遇到右括号(
)
、}
、]
),检查栈是否为空:- 如果栈为空,说明没有匹配的左括号,匹配失败。
- 如果栈不为空,从栈顶弹出一个左括号,并检查是否与当前的右括号匹配。如果不匹配,匹配失败。
- 如果遇到左括号(
- 检查栈:遍历结束后,如果栈不为空,说明有未匹配的左括号,匹配失败;否则,匹配成功。
根据上文的详细描述,我们就可以写出对应的C++代码了:
1 |
|
- isMatching 函数:这个辅助函数用于判断两个括号是否匹配。
- bracketDetect 函数:括号匹配函数。它使用栈来跟踪未匹配的左括号。
- 遍历字符串,如果遇到左括号,将其压入栈中。
- 如果遇到右括号,检查栈是否为空。如果为空,则匹配失败;否则,弹出栈顶元素并检查是否匹配。
- 遍历结束后,如果栈为空,则括号完全匹配;否则,存在未匹配的左括号。
- main 函数:测试用例,验证不同字符串的括号匹配情况。
这种方法利用栈的后进先出(LIFO)特性,高效地解决了括号匹配问题。
2. 中缀转后缀表达式
2.1 概念
中缀表达式
中缀表达式是指
操作符位于操作数之间
的表达式。它是我们日常书写和阅读数学表达式的方式。例如:A + B
A + B * C
后缀表达式
后缀表达式(也称为
逆波兰表示法
)是指操作符位于操作数之后
的表达式。在后缀表达式中,不需要使用括号来表示操作的优先级。例如:A B +
A B C * +
计算机在进行计算的时候,习惯使用后缀表达式,而我们给计算机输入的都是中缀表达式,所以这二者之间肯定是可以转换的,下面我们来一起看一下转换的具体流程。
2.2 中缀转后缀
在进行中缀表达式转后缀表达式的时候,转换过程需要使用栈来临时保存操作符
,并按照以下规则执行:
- 初始化:准备一个操作符栈和一个用于输出的列表(
比如: 字符串对象
)。 - 从左到右扫描中缀表达式:
- 如果是操作数(数字或变量),直接添加到输出列表。
- 如果是左括号
(
,压入栈。 - 如果是右括号
)
,弹出栈顶元素并添加到输出列表,直到遇到左括号(
,然后丢弃这对括号。 - 如果是操作符:
- 弹出栈顶元素并添加到输出列表,直到栈顶元素的优先级低于当前操作符或栈为空。
- 将当前操作符压入栈。
- 处理完所有输入后:将栈中剩余的操作符依次弹出并添加到输出列表。
根据上面的描述,我们可以写成如下的C++代码:
1 |
|
执行程序,终端打印的结果为:
1 | 中缀表达式: A + B * (C - D) |
getPrecedence 函数:返回操作符的优先级,用于决定操作符的弹出顺序。
isOperator 函数:判断字符是否为操作符。
infixToPostfix 函数:将中缀表达式转换为后缀表达式。
- 使用
for
循环遍历中缀表达式中的每个字符。 - 遇到操作数时,直接添加到后缀表达式
postfix
中。 - 遇到左括号
(
时,将其压入操作符栈。 - 遇到右括号
)
时,弹出操作符栈中的元素直到遇到左括号(
。 - 遇到操作符时,根据优先级弹出栈中的操作符,并将当前操作符压入栈。
- 最后,将操作符栈中剩余的操作符依次弹出并添加到后缀表达式
postfix
中。
- 使用
std::isspace(c)
:C++ 标准库函数用于判断字符
c
是否为空白字符。空白字符包括空格 (' '
)、制表符 ('\t'
)、换行符 (‘\n’
)、回车符 (‘\r’
) 等。在中缀表达式转换为后缀表达式的代码实现中,该函数的作用是检查当前字符
c
是否为空白字符。如果是空白字符,则直接跳过该字符,不对其进行处理,以确保只处理有效的操作数、操作符和括号。
std::isdigit(c)
和std::isalpha(c)
: C++ 标准库中的函数std::isdigit(c)
:用于检查字符c
是否是数字字符。返回 true 表示字符是 ‘0’ 到 ‘9’ 之间的数字字符,否则返回 false。std::isalpha(c)
:用于检查字符c
是否是字母字符。返回 true 表示字符是 ‘a’ 到 ‘z’ 或 ‘A’ 到 ‘Z’ 之间的字母字符,否则返回 false。
main 函数:测试中缀表达式到后缀表达式的转换。
该实现保证了在遵循操作符优先级和括号匹配的情况下,正确地将中缀表达式转换为后缀表达式。
3. 后缀表达式的计算
3.1 计算后缀表达式
计算机在计算表达式时,并不直接使用中缀表达式,而是更倾向于使用后缀表达式(逆波兰表达式)。这是因为后缀表达式具有以下优点:
- 无需括号:后缀表达式不需要括号来指示运算顺序,操作符的位置确定了运算的顺序,简化了解析和计算过程。
- 减少优先级判断:在后缀表达式中,操作符的优先级被完全嵌入到操作符的顺序中,不需要额外的优先级规则来解释。
- 直接计算:计算机可以通过一次遍历后缀表达式完成计算,而中缀表达式需要额外的步骤来解析优先级和括号。
因此,很多计算机系统和编程语言(尤其是栈式计算机)通常会先将中缀表达式转换为后缀表达式,然后基于后缀表达式进行计算。这种方式更加高效和直观,减少了运算时的复杂性和误解。
计算后缀表达式的一种常见方法是使用栈(stack),详细步骤如下:
- 从左到右扫描后缀表达式。
- 遇到操作数时,将其压入栈中。
- 遇到操作符时,弹出栈顶的两个操作数,进行相应的运算,并将结果压入栈中。
- 重复上述步骤,直到表达式扫描完毕。
- 栈顶元素即为表达式的结果。
通过描述我们就可以写成相应的C++代码了:
1 |
|
isOperator
函数:判断一个字符串是否为操作符(+、-、*、/)。performOperation
函数:根据给定的操作符,对两个操作数执行相应的运算。evaluatePostfix
函数:这是核心函数,负责计算后缀表达式。使用std::stack
存储操作数和中间结果,使用std::istringstream
逐个读取表达式中的元素(操作数或操作符)。- 当遇到操作符时,弹出栈顶的两个操作数,计算结果并将其压回栈中。
- 当遇到操作数时,将其转换为整数并压入栈中。
main
函数:定义一个后缀表达式,并调用evaluatePostfix
函数计算其结果,然后输出结果。throw std::invalid_argument("Invalid operator");
这一行代码的作用是当遇到无效的操作符时,抛出一个异常,说明代码中出现了一个无效的操作符。while (iss >> token)
每次循环读取一个完整的标记(token)。- 标记(token)通常指的是以空格或其他分隔符分隔的
字符串
。 - 从
std::istringstream
对象中提取数据时,默认的分隔符是空格
假设中缀表达式字符串是
"39 4 + 2 * 7 /"
,这个字符串包含了空格分隔的标记:39
,4
,+
,2
,*
,7
和/
。循环的具体过程如下:- 第一次循环:
token
被赋值为"39"
。 - 第二次循环:
token
被赋值为"4"
。 - 第三次循环:
token
被赋值为"+"
。 - 第四次循环:
token
被赋值为"2"
。 - 第五次循环:
token
被赋值为"*"
。 - 第六次循环:
token
被赋值为"7"
。 - 第七次循环:
token
被赋值为"/"
。
每个标记都会按照上述步骤依次被读取并处理。
- 标记(token)通常指的是以空格或其他分隔符分隔的
3.2. 异常处理
在 C++ 中,异常处理机制用于捕获和处理运行时错误。通过使用 throw
关键字,你可以在程序中任何地方抛出一个异常,然后在另一个地方捕获并处理它。这种机制有助于提高代码的健壮性和可维护性。
std::invalid_argument
是 C++ 标准库中定义的一种异常类型,位于 <stdexcept>
头文件中。它通常用于函数参数无效的情况。例如,当传递给函数的参数不符合预期时,可以抛出这个异常。
在 performOperation
函数中,如果传递的操作符不是 +
、-
、*
或 /
之一,说明这个操作符无效,不在预期范围内。此时,程序会抛出 std::invalid_argument
异常,并附带一个错误消息 "Invalid operator"
。这样做的目的是通知调用者或开发人员,有一个未预料到的操作符传递给了函数。
示例
假设你传递了一个无效的操作符 $
给 performOperation
函数:
1 | performOperation("$", 3, 4); |
此时,performOperation
函数会检测到操作符 $
不是有效的操作符,然后执行以下代码:
1 | throw std::invalid_argument("Invalid operator"); |
这个异常会立即中断函数的执行,并将控制权交给调用堆栈中上层的异常处理代码(如果存在)。如果没有捕获这个异常的代码,程序将会终止,并输出异常信息。
捕获异常
你可以在调用 performOperation
的地方捕获这个异常,并处理错误。例如:
1 | try |
在这个例子中,当 performOperation
抛出 std::invalid_argument
异常时,catch
块会捕获它,并输出错误信息:
1 | Error: Invalid operator |
通过这种方式,你可以在程序中优雅地处理错误,而不是让程序意外崩溃。