栈的应用-工具盒子

在上一个章节中为大家详细讲解了栈的特点和实现，关于栈的现实应用有很多，下面再来给说几个比较常见的案例：括号匹配问题、中缀表达式转后缀表达式、后缀表达式的计算。

括号匹配问题 {#1-括号匹配问题} =====================

括号在使用的时候都是成对出现的，分为左右两部分。很多时候我们都需要验证给定的字符串中的括号是否正确匹配，通常包括以下三种类型：

小括号 - ()

大括号 - {}

中括号 - []

如果使用栈来处理这个问题，具体的操作步骤如下：

初始化栈 ：创建一个空栈，用于存放左括号。
遍历字符串 ：逐个字符扫描字符串。
- 如果遇到左括号（(、{、[），将其压入栈中。
- 如果遇到右括号（)、}、]），检查栈是否为空：
  - 如果栈为空，说明没有匹配的左括号，匹配失败。
  - 如果栈不为空，从栈顶弹出一个左括号，并检查是否与当前的右括号匹配。如果不匹配，匹配失败。
检查栈：遍历结束后，如果栈不为空，说明有未匹配的左括号，匹配失败；否则，匹配成功。

根据上文的详细描述，我们就可以写出对应的C++代码了：

|------------------------------------------------------------------------------------------------------------------------------------|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | #include <iostream> #include <stack> using namespace std; bool isMatching(char start, char end) { return (start == '(' && end == ')') || (start == '[' && end == ']') || (start == '{' && end == '}'); } bool bracketDetect(string str) { stack<char> st; for (char bracket : str) { if (bracket == '(' || bracket == '{' || bracket == '[') { // 压栈 st.push(bracket); } else if (bracket == ')' || bracket == '}' || bracket == ']') { if (st.empty() || !isMatching(st.top(), bracket)) { return false; } st.pop(); } } return st.empty(); } int main() { string str1("[12[abc{helo}xxx]))"); string str2("(([12[abc{helo}xxx]=-=]))"); bool flag = bracketDetect(str1); cout << str1 << " 字符串中的括号是否匹配呢? " << flag << endl; flag = bracketDetect(str2); cout << str2 << " 字符串中的括号是否匹配呢? " << flag << endl; return 0; } |

isMatching 函数：这个辅助函数用于判断两个括号是否匹配。
bracketDetect 函数 ：括号匹配函数。它使用栈来跟踪未匹配的左括号。
- 遍历字符串，如果遇到左括号，将其压入栈中。
- 如果遇到右括号，检查栈是否为空。如果为空，则匹配失败；否则，弹出栈顶元素并检查是否匹配。
- 遍历结束后，如果栈为空，则括号完全匹配；否则，存在未匹配的左括号。
main 函数：测试用例，验证不同字符串的括号匹配情况。

这种方法利用栈的后进先出（LIFO）特性，高效地解决了括号匹配问题。

中缀转后缀表达式 {#2-中缀转后缀表达式} =========================

2.1 概念 {#2-1-概念}

中缀表达式

中缀表达式是指操作符位于操作数之间的表达式。它是我们日常书写和阅读数学表达式的方式。例如：
- A + B
- A + B * C
后缀表达式

后缀表达式（也称为逆波兰表示法）是指操作符位于操作数之后的表达式。在后缀表达式中，不需要使用括号来表示操作的优先级。例如：
- A B +
- A B C * +

计算机在进行计算的时候，习惯使用后缀表达式，而我们给计算机输入的都是中缀表达式，所以这二者之间肯定是可以转换的，下面我们来一起看一下转换的具体流程。

2.2 中缀转后缀 {#2-2-中缀转后缀}

在进行中缀表达式转后缀表达式的时候，转换过程需要使用栈来临时保存操作符，并按照以下规则执行：

初始化 ：准备一个操作符栈和一个用于输出的列表（比如: 字符串对象）。
从左到右扫描中缀表达式 ：
- 如果是操作数（数字或变量），直接添加到输出列表。
- 如果是左括号 (，压入栈。
- 如果是右括号 )，弹出栈顶元素并添加到输出列表，直到遇到左括号 (，然后丢弃这对括号。
- 如果是操作符：
  - 弹出栈顶元素并添加到输出列表，直到栈顶元素的优先级低于当前操作符或栈为空。
  - 将当前操作符压入栈。
处理完所有输入后：将栈中剩余的操作符依次弹出并添加到输出列表。

根据上面的描述，我们可以写成如下的C++代码：

|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 | #include <iostream> #include <stack> #include <string> #include <vector> #include <cctype> int getPrecedence(char op) { switch (op) { case '+': case '-': return 1; case '*': case '/': return 2; case '^': return 3; default: return 0; } } bool isOperator(char c) { return c == '+' || c == '-' || c == '*' || c == '/' || c == '^'; } std::string infixToPostfix(const std::string& infix) { std::stack<char> operators; std::string postfix; for (char c : infix) { if (std::isspace(c)) { continue; } if (std::isdigit(c) || std::isalpha(c)) { postfix += c; } else if (c == '(') { operators.push(c); } else if (c == ')') { while (!operators.empty() && operators.top() != '(') { postfix += operators.top(); operators.pop(); } operators.pop(); } else if (isOperator(c)) { while (!operators.empty() && getPrecedence(operators.top()) >= getPrecedence(c)) { postfix += operators.top(); operators.pop(); } operators.push(c); } } while (!operators.empty()) { postfix += operators.top(); operators.pop(); } return postfix; } int main() { std::string infix = "A + B * (C - D)"; std::string postfix = infixToPostfix(infix); std::cout << "中缀表达式: " << infix << std::endl; std::cout << "后缀表达式: " << postfix << std::endl; return 0; } |

执行程序，终端打印的结果为：

|-------------|-----------------------------------------------| | 1 2 | 中缀表达式: A + B * (C - D) 后缀表达式: ABCD-*+ |

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 计算后缀表达式 {#3-1-计算后缀表达式}

计算机在计算表达式时，并不直接使用中缀表达式，而是更倾向于使用后缀表达式（逆波兰表达式）。这是因为后缀表达式具有以下优点：

无需括号：后缀表达式不需要括号来指示运算顺序，操作符的位置确定了运算的顺序，简化了解析和计算过程。
减少优先级判断：在后缀表达式中，操作符的优先级被完全嵌入到操作符的顺序中，不需要额外的优先级规则来解释。
直接计算：计算机可以通过一次遍历后缀表达式完成计算，而中缀表达式需要额外的步骤来解析优先级和括号。

因此，很多计算机系统和编程语言（尤其是栈式计算机）通常会先将中缀表达式转换为后缀表达式，然后基于后缀表达式进行计算。这种方式更加高效和直观，减少了运算时的复杂性和误解。

计算后缀表达式的一种常见方法是使用栈（stack），详细步骤如下：

从左到右扫描后缀表达式。
遇到操作数时，将其压入栈中。
遇到操作符时，弹出栈顶的两个操作数，进行相应的运算，并将结果压入栈中。
重复上述步骤，直到表达式扫描完毕。
栈顶元素即为表达式的结果。

通过描述我们就可以写成相应的C++代码了：

|------------------------------------------------------------------------------------------------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #include <iostream> #include <stack> #include <string> #include <sstream> using namespace std; bool isOperator(const string& token) { return token == "+" || token == "-" || token == "*" || token == "/"; } int performOperation(const string& operation, int operand1, int operand2) { if (operation == "+") return operand1 + operand2; if (operation == "-") return operand1 - operand2; if (operation == "*") return operand1 * operand2; if (operation == "/") return operand1 / operand2; throw std::invalid_argument("Invalid operator"); } int evaluatePostfix(const string& expression) { stack<int> s; istringstream iss(expression); string token; while (iss >> token) { if (isOperator(token)) { int operand2 = s.top(); s.pop(); int operand1 = s.top(); s.pop(); int result = performOperation(token, operand1, operand2); s.push(result); } else { s.push(stoi(token)); } } return s.top(); } int main() { string expression = "3 4 + 2 * 7 /"; int result = evaluatePostfix(expression); cout << "后缀表达式的计算结果是: " << result << endl; return 0; } |

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 和 /。循环的具体过程如下：
1. 第一次循环：token 被赋值为 "39"。
2. 第二次循环：token 被赋值为 "4"。
3. 第三次循环：token 被赋值为 "+"。
4. 第四次循环：token 被赋值为 "2"。
5. 第五次循环：token 被赋值为 "*"。
6. 第六次循环：token 被赋值为 "7"。
7. 第七次循环：token 被赋值为 "/"。
每个标记都会按照上述步骤依次被读取并处理。

3.2. 异常处理 {#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 2 3 4 5 6 7 8 | try { int result = performOperation("$", 3, 4); } catch (const std::invalid_argument &e) { std::cerr << "Error: " << e.what() << std::endl; } |

在这个例子中，当 performOperation 抛出 std::invalid_argument 异常时，catch 块会捕获它，并输出错误信息：

|-----------|---------------------------------| | 1 | Error: Invalid operator |

通过这种方式，你可以在程序中优雅地处理错误，而不是让程序意外崩溃。