栈的应用

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

1. 括号匹配问题

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

  • 小括号 - ()
  • 大括号 - {}
  • 中括号 - []

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

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

根据上文的详细描述，我们就可以写出对应的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;
}
  1. isMatching 函数：这个辅助函数用于判断两个括号是否匹配。
  2. bracketDetect 函数：括号匹配函数。它使用栈来跟踪未匹配的左括号。
    • 遍历字符串，如果遇到左括号，将其压入栈中。
    • 如果遇到右括号，检查栈是否为空。如果为空，则匹配失败；否则，弹出栈顶元素并检查是否匹配。
    • 遍历结束后，如果栈为空，则括号完全匹配；否则，存在未匹配的左括号。
  3. main 函数：测试用例，验证不同字符串的括号匹配情况。

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

2. 中缀转后缀表达式

2.1 概念

  • 中缀表达式

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

    • A + B

    • A + B * C

  • 后缀表达式

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

    • A B +

    • A B C * +

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

2.2 中缀转后缀

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

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

根据上面的描述，我们可以写成如下的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-*+

  1. getPrecedence 函数：返回操作符的优先级，用于决定操作符的弹出顺序。

  2. isOperator 函数：判断字符是否为操作符。

  3. infixToPostfix 函数：将中缀表达式转换为后缀表达式。

    • 使用 for 循环遍历中缀表达式中的每个字符。
    • 遇到操作数时，直接添加到后缀表达式 postfix 中。
    • 遇到左括号 ( 时，将其压入操作符栈。
    • 遇到右括号 ) 时，弹出操作符栈中的元素直到遇到左括号 (。
    • 遇到操作符时，根据优先级弹出栈中的操作符，并将当前操作符压入栈。
    • 最后，将操作符栈中剩余的操作符依次弹出并添加到后缀表达式 postfix 中。

  4. std::isspace(c) ：C++ 标准库函数

    • 用于判断字符 c 是否为空白字符。空白字符包括空格 (' ' )、制表符 ('\t')、换行符 (‘\n’)、回车符 (‘\r’) 等。

    • 在中缀表达式转换为后缀表达式的代码实现中，该函数的作用是检查当前字符 c 是否为空白字符。如果是空白字符，则直接跳过该字符，不对其进行处理，以确保只处理有效的操作数、操作符和括号。

  5. 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。

  6. main 函数：测试中缀表达式到后缀表达式的转换。

该实现保证了在遵循操作符优先级和括号匹配的情况下，正确地将中缀表达式转换为后缀表达式。

3. 后缀表达式的计算

3.1 计算后缀表达式

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

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

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

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

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

通过描述我们就可以写成相应的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;
}

  1. isOperator 函数：判断一个字符串是否为操作符（+、-、*、/）。

  2. performOperation 函数：根据给定的操作符，对两个操作数执行相应的运算。

  3. evaluatePostfix 函数：这是核心函数，负责计算后缀表达式。使用 std::stack存储操作数和中间结果，使用std::istringstream逐个读取表达式中的元素（操作数或操作符）。

    • 当遇到操作符时，弹出栈顶的两个操作数，计算结果并将其压回栈中。
    • 当遇到操作数时，将其转换为整数并压入栈中。

  4. main 函数：定义一个后缀表达式，并调用 evaluatePostfix 函数计算其结果，然后输出结果。

  5. throw std::invalid_argument("Invalid operator"); 这一行代码的作用是当遇到无效的操作符时，抛出一个异常，说明代码中出现了一个无效的操作符。

  6. 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. 异常处理

在 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

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