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

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 /",这个字符串包含了空格分隔的标记:394+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

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